2025ICPC网络赛第二场复盘

D. Arcane Behemoths

每个子序列的值，显然是把子序列排序后每次去掉最大值，加到前面的每一项上，以此类推，直到只剩下一项
对每个子序列而言，依次取最大值加到其他所有项上，可以得到排序后从小到大第 $n$ 项对于该子序列的贡献系数为 $n==1 ? 1:2^{n-2}$ 。
对整个序列从小到大排序后，满足第 $i$ 项为子序列从小到大第 $n$ 项的子序列的个数可求，即取小于该项中的 $n-1$ 项，大于该项的每项任意选择取或不取，若共有5项，则从小到大每项对答案的所有贡献如下：
第5项：

$C_{4}^{0}\times2^0\times2^0+ C_{4}^{1}\times2^0\times2^0+ C_{4}^{2}\times2^1\times2^0+ C_{4}^{3}\times2^2\times2^0+ C_{4}^{4}\times2^3\times2^0$

第4项：

$C_{3}^{0}\times2^0\times2^1+ C_{3}^{1}\times2^0\times2^1+ C_{3}^{2}\times2^1\times2^1+ C_{3}^{3}\times2^2\times2^1$

第3项：

$C_{2}^{0}\times2^0\times2^2+ C_{2}^{1}\times2^0\times2^2+ C_{2}^{2}\times2^1\times2^2$

第2项：

$C_{1}^{0}\times2^0\times2^3+ C_{1}^{1}\times2^0\times2^3$

第1项：

$C_{0}^{0}\times2^0\times2^4$

例如： $C_{3}^{2}\times2^1\times2^1$ 的意思为整个序列从小到大第4项作子序列的第3项时， $C_{3}^{2}$ 表示从前面三项取两项，中间的 $2^1$ 代表第4项后面的1项取或不取有 $2^1$ 种可能，后面的 $2^1$ 代表作为子序列的第3项，它对子序列的值产生的贡献的次数。
以上是n=5的所有情况，我们发现若n=6，则答案为把以上每一项都乘2，然后加上第六项
每次新加的第n项的通式为：

$S_n=\sum_{i=0}^{n-1}C_{n-1}^{i}\times2^{max(0,i-1)}$

通过推导我们发现以下式子成立：

$S_n=3\times S_{n-1}-1$

以上，我们可以通过递推求出 $S_n$ 的每一项，最终对序列长度为 $n$ 的答案有：

$Ans_n=Ans_{n-1}\times2+S_n\times a_i$

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll mod=998244353;
ll a[200005];
ll s[200005];
ll ans[200005];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	s[1]=1;
	ans[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		s[i]=(s[i-1]*3%mod+mod-1)%mod;
		ans[i]=(ans[i-1]*2%mod+s[i]*a[i]%mod)%mod;
	}
	cout<<ans[n]<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

C. Jiaxun!

方法一：二分答案

最小值 $minn$ 必须满足能为 $minn$ 提供题目的 $F$ 之和 $ ⩾|t|×mid$

设 $sum=f[1]+f[2]+f[3]+f[4]+f[5]+f[6]+f[7]$

最小值 $minn$ 必须满足以下几个式子：

$f[1]+f[3]+f[5]+f[7]\geq minn$

$f[2]+f[3]+f[6]+f[7]\geq minn$

$f[4]+f[5]+f[6]+f[7]\geq minn$

$sum\geq minn\times 3$

$sum-f[4]\geq minn\times 2$

$sum-f[2]\geq minn\times 2$

$sum-f[1]\geq minn\times 2$

二分满足以上所有条件的 $minn$ 的最大值即可

#include <bits/stdc++.h>
using namespace std;
int s;
int f[8];
int ans;
int sum;
int check(int now)
{
	if(f[1]+f[3]+f[5]+f[7]<now) return 0;
	if(f[2]+f[3]+f[6]+f[7]<now) return 0;
	if(f[4]+f[5]+f[6]+f[7]<now) return 0;
	if(sum<now*3) return 0;
	if(sum-f[4]<now*2) return 0;
	if(sum-f[2]<now*2) return 0;
	if(sum-f[1]<now*2) return 0;
	return 1;
}
void solve()
{	
	cin>>s;
	sum=0;
	for(int i=1;i<=7;i++)
	{
		cin>>f[i];
		sum+=f[i];
	}
	int l=0,r=s;
	while(l<r)
	{
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

方法二：多个可能值取min

实际上，经过以上分析，可以得到最大的 $minn$ 必定在以下几项之中：

$minn=f[1]+f[3]+f[5]+f[7]$

$minn=f[2]+f[3]+f[6]+f[7]$

$minn=f[4]+f[5]+f[6]+f[7]$

$minn=sum\div 3$

$minn=(sum-f[4])\div 2$

$minn=(sum-f[2])\div 2$

$minn=(sum-f[1])\div 2$

因此我们可以直接省略二分，直接对以上几项取最小值即可

#include <bits/stdc++.h>
using namespace std;
int s;
int f[8];
int ans;
void solve()
{	
	cin>>s;
	for(int i=1;i<=7;i++)
		cin>>f[i];
	ans=min(min(min(f[1]+f[3]+f[5]+f[7],f[2]+f[3]+f[6]+f[7]),min(f[4]+f[5]+f[6]+f[7],s/3)),min(min((s-f[4])/2,(s-f[1])/2),(s-f[2])/2));
	cout<<ans<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}