9.22 %你赛

比赛数据

分数 $\color{#90FF00}304/400$。
各题分数（赛时/总分）：
T1 $\color{#00FF00}100/100$
T2 $\color{#00FF00}100/100$
T3 $\color{#50F000}99/100$ ??!?
T4 $\color{#F03000}5/100$
排名 $\color{#F0D050}1/6$（排除参与出题的人）（高于预期）。

前 $3$ 题全™是细节题。

T1 link $\color{#F0F000}(2.50)$

纯粹的分类讨论DP。
我好奇我怎么做到调这东西调近 $\text{1h}$ 的，
而且如果是OI赛制的话没大样例肯定挂分了。

从低位向高位DP，统计每一位为最高位时对答案有多少贡献。
每一位有5种情况：

• $a_i+b_i=c_i$，可作为合法区间的最高位，后一位不需要向前进位，自己不向前进位。
• $a_i+b_i+1=c_i$，可作为合法区间的最高位，后一位需要向前进位，自己不向前进位。
• $a_i+b_i=c_i+10$，不可作为合法区间的最高位，后一位不需要向前进位，自己向前进位。
• $a_i+b_i+1=c_i+10$，不可作为合法区间的最高位，后一位需要向前进位，自己向前进位。
• 其他所有情况，绝对不会出现在任何合法区间内，讨论相关进位情况无意义。

时间复杂度 $O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,t,u;
ll w,dp[1000007],c[1000007],ans;
int main(){
	cin>>s>>t>>u;
	for(int i=s.size()-1;i>=0;i--){
		w=s[i]+t[i]-u[i]-'0';
		if(w==0){
			if(c[i+1]==0) dp[i]=dp[i+1]+1;
			else dp[i]=1;
            ans+=dp[i];
			c[i]=0;
		}
		else if(w==-1){
			if(c[i+1]==1) dp[i]=dp[i+1]+1;
			else dp[i]=0;
            ans+=dp[i];
			c[i]=0;
		}
		else if(w==10){
			if(c[i+1]==0) dp[i]=dp[i+1];
			else dp[i]=0;
			c[i]=1;
		}
		else if(w==9){
			if(c[i+1]==1){
				dp[i]=dp[i+1];
				c[i]=1;
			}
			else dp[i]=c[i]=0;
		}
		else{
			dp[i]=0;
			c[i]=-1;
		}
	}
	cout<<ans;
	return 0;
}

T2 link $\color{#00E0A0}(4.00)$

细节很多的贪心题。

第 $1$ 个坑点是 $1 \leq a_{i,j} \leq 10^{12}$，记得开 long long！
第 $2$ 个坑点是数据范围给的 $1 \leq k \leq n \times m \leq 3 \times 10^5$，并没有对 $n,m$ 规定单独上限！
所以要用 vector 存煎饼大小。

这里记满足 $a_{i,j} \geq a_{i,j+1}$ 对所有 $j$ 成立的堆 $i$ 为大顶堆，
满足 $a_{i,j} \leq a_{i,j+1}$ 对所有 $j$ 成立的堆 $i$ 为小顶堆。
注意不要和优先队列那个堆搞混了。

设 $x_i$ 为在大顶堆中选 $i$ 个煎饼的最优大小和，$y_i$ 为在小顶堆中选 $i$ 个煎饼的最优大小和。
求 $x_i$ 是 trivial 的，只要把大顶堆中前 $i$ 大的煎饼大小求和就行了，因为最大的一定在某堆的顶上。
为求 $y_i$，再定义选了 $m$ 个煎饼的为整堆，没选完 $m$ 个的为散堆。
关键结论：最多选 $1$ 个散堆，否则不优。
证明：反证法，假设选了 $\geq 2$ 个散堆，设其中两个为 $x,y$，
则如果舍弃 $a$ 中一个换 $b$ 中多选一个更优，则再舍弃一个同样更优，直到 $a$ 不选或 $b$ 选完；
如果舍弃 $a$ 中一个换 $b$ 中多选一个不优，则舍弃 $b$ 中一个换 $a$ 中多选一个必更优，$a,b$ 互换同上。

第 $3$ 个坑点是计算 $y_i$ 时要分类讨论！
有的人（包括我）赛时交了 $\color{#88FF00}88/100$ 分的代码，
就是因为求 $y_i$ 贪心地选择前 $\left\lfloor\frac{i}{m}\right\rfloor$ 大的整块后再贪心地选择最大的散块。
这是错的，可以被如下输入hack:

4 4 10
5 6 6 6
1 1 1 15
1 1 1 18
1 1 1 1

究其原因，是漏了在将前 $\left\lfloor\frac{i}{m}\right\rfloor$ 大的整块之一替换为其部分后再选第 $\left\lfloor\frac{i}{m}\right\rfloor+1$ 大的整块这一可能。
再讨论这种情况就可以 $\color{#00FF00}100/100$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,l,r,f[300007],g[300007],ct,dt;
ll x,w[300007],y[300007],z[300007],ss,mx;
vector<ll>v[300007];
vector<ll>s[300007];
set<pair<ll,ll>>st[300007];
set<pair<ll,ll>>tt[300007];
bool cmpa(int x,int y){
	return s[x][m-1]>s[y][m-1];
}
bool cmpb(ll x,ll y){
	return x>y;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			cin>>x;
			v[i].push_back(x);
			s[i].push_back(x);
			if(j>0) s[i][j]+=s[i][j-1];
			if(j>0&&x>v[i][j-1]) f[i]=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]){
			dt++;
			g[dt]=i;
			for(int j=0;j<m;j++){
				st[j+1].insert(make_pair(s[i][j],i));
			}
		}
		else{
			for(int j=0;j<m;j++){
				ct++;
				w[ct]=v[i][j];
			}
		}
	}
	sort(g+1,g+dt+1,cmpa);
	for(int i=1;i<=dt*m;i++){
		if(i%m!=0){
			auto ita=st[i%m].end();
			ita--;
			y[i]=max(y[i],ss+(*ita).first);
			if(i<m) continue;
			auto itb=st[m].end();
			itb--;
			auto itc=tt[i%m].begin();
			y[i]=max(y[i],ss+(*itb).first-(*itc).first);
		}
		else{
			auto itb=st[m].end();
			itb--;
			int p=(*itb).second;
			ss+=(*itb).first;
			y[i]=max(y[i],ss);
			for(int j=1;j<m;j++){
				tt[j].insert(make_pair(s[p][m-1]-s[p][j-1],p));
				st[j].erase(make_pair(s[p][j-1],p));
			}
			st[m].erase(itb);
		}
	}
	sort(w+1,w+ct+1,cmpb);
	for(int i=1;i<=ct;i++) z[i]=z[i-1]+w[i];
	l=max(k-ct,0);
	r=min(k,ct);
	while(l<=n*m-ct&&r>=0){
		if(y[l]+z[r]>mx) mx=y[l]+z[r];
		l++;
		r--;
	}
	cout<<mx;
	return 0;
}

T3 link $\color{#00C8F0}(4.75)$

论 $\color{#50F000}99/100$ 是怎么做到的。
据说原比赛捆绑测试所有测试点，所以 $99=0$。

注意：

• 多组数据，记得清空
• 图不保证连通（赛时差点因此 $\color{#F0C800}-8$）
• 合并灰点的邻点时要只合并其他灰点和颜色相同的点，否则会像我一样 $\color{#F0E000}-1$。

T4 link $\color{#CCCCCC}(-)$

Benny 出的神秘东西。
根据看题解经验，我连题解都难看懂的题，并且没有太偏的知识点，至少是中上紫。
等我有两倍队线实力再补吧。（@2026.9.22）
$\verb!flag!$

总结与反思

这次的做题策略除了T4只打了最低的暴力分外十分优秀，基本没把本来能拿的分丢掉。

IOI赛制下就应该反复提交+手造数据查错。
就算是OI赛制，也该手造数据差错。
这样可以查出很多细节错误。

彩蛋

$$\large \color{#fd0}\verb!1 !\color{#f4b}\verb!2 !\color{#0da}\verb!3 !\color{#d4f}\verb!4!$$