想起上次的ABC346没打，刚才虚拟参赛打了A~D，E题思路有，但是实现方式没选好导致WA了，没能在赛时做出来。写下题解记录一下~
C - Σ
用求和公式先把\(1\sim k\)的和求出来：\(\frac{k(k+1)}{2}\)，然后对于\(A\)数组中的元素依次减去就行（注意相同元素不能减\(2\)次）
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[200010];
unordered_map<int,bool> m;
signed main(){
cin>>n>>k;
int ans=(k+1)*k/2;
for(int i=1;i<=n;i++){
cin>>a[i];
if(!m[a[i]]){
m[a[i]]=1;
if(a[i]<=k) ans-=a[i];
}
}
cout<<ans;
return 0;
}
D - Gomamayo Sequence
这个题就是让我们把字符串变成一个01交替，但是中间有且仅有一个00或者11的字符串。
所以我们可以枚举在哪里重复，需要注意的是一个位置有两种情况，比如：
1010101001010
0101010110101
从重复的位置分割，可以形成0101+1010或1010+0101结构的字符串，这样我们只需要知道前缀和后缀需要多少次变化成0101或1010就行。可以通过预处理来维护前缀的代价和后缀的代价，各需要两个数组，分别维护变成\(0101…\)和\(1010…\)的代价。这样\(O(n)\)枚举，\(O(1)\)查询，总时间复杂度\(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c[200010];
int f[4][200010];
//0:0101...前缀 1:1010...前缀
//2:0101...后缀 3:1010...后缀
string s;
signed main(){
cin>>n>>s;
s=' '+s;
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=1;i<=n;i++){
char temp='0'+i%2,ltemp='0'+(n-i+1)%2;
f[0][i]=f[0][i-1]+(s[i]==temp)*c[i];
f[1][i]=f[1][i-1]+(s[i]!=temp)*c[i];
f[2][n-i+1]=f[2][n-i+2]+(s[n-i+1]==ltemp)*c[n-i+1];
f[3][n-i+1]=f[3][n-i+2]+(s[n-i+1]!=ltemp)*c[n-i+1];
}
int ans=LLONG_MAX;
for(int i=2;i<=n;i++){
ans=min(ans,f[0][i-1]+f[3][i]);
ans=min(ans,f[1][i-1]+f[2][i]);
}
cout<<ans;
return 0;
}
E - Paint
首先我们对原数组进行一个去重，也就是\(t\)和\(a\)都相同的操作，以最后面的为准。这样每行每列都最多有\(1\)次操作。
倒序遍历，记录下填充了多少行，多少列，每次累加需要减去，比如当前填充某一行，此后填充了\(cntv\)列，那么这个颜色实际上只填了\(w-cntv\)个格子，列同理。
用\(vis\)数组+倒序遍历可以省掉去重这一步骤。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,w,m;
int t[200010],a[200010],x[200010];
bool vx[200010],vy[200010];
int ans[200010];
//0=op1 1=op2
signed main(){
cin>>h>>w>>m;
for(int i=1;i<=m;i++) cin>>t[i]>>a[i]>>x[i];
int cnth=0,cntv=0;//多少行和多少列涂了颜色
for(int i=m;i>=1;i--){
if(t[i]==1&&!vx[a[i]]){//涂的行
vx[a[i]]=1;
ans[x[i]]+=w-cntv;
cnth++;
}
if(t[i]==2&&!vy[a[i]]){//涂的列
vy[a[i]]=1;
ans[x[i]]+=h-cnth;
cntv++;
}
}
int cntans=0;
ans[0]=h*w;
for(int i=1;i<=200000;i++) ans[0]-=ans[i];
for(int i=0;i<=200000;i++) cntans+=bool(ans[i]);
cout<<cntans<<endl;
for(int i=0;i<=200000;i++){
if(ans[i]){
cout<<i<<" "<<ans[i]<<endl;
}
}
return 0;
}