定位：给中低段位一点压力，给中高段位一点信心！
A
发现只是单向变换 \((0\to 1)\)，用两个变量维护位置最小值和最大值即可。
#define int long long
int n,q,maxn,minn=1e18+1,x;
signed main(){
n=read(),q=read();
while(q--){
x=read();
maxn=max(maxn,x);
minn=min(minn,x);
print(maxn-minn+1),puts("");
}
return 0;
}
B
不知道有没有人想麻烦，本质是均摊分析。
我们模拟进位过程即可，复杂度为 \(O(n+\log n+q)\)。
理由：每操作一次最多只会增加一个 \(1\)，所以模拟进位消 \(1\) 的总次数是 \(n+q\) 级别的。
空间要开到 \(n+\log n\)，要不然会被卡
const int N=1e6+30;
int n,q,k,ans;
bool a[N];
char c;
int main(){
n=read();
for(int i=0;i<n;++i)cin>>c,a[n-i-1]=c-'0';
q=read();
while(q--){
k=read(),ans=1;
while(a[k])a[k++]=0,ans++;
a[k]=1,print(ans),puts("");
}
n+=log2(n)+1;
while(!a[n])n--;
for(int i=n;i>=0;--i)putchar(a[i]?'1':'0');
return 0;
}
C
题意即每次使 \(a\) 和 \(b\) 中数分别匹配，求所有匹配方式中 \(\max(a_i+b_i)\) 的最小值，其中 \((a_i,b_i)\) 是第 \(i\) 组匹配。
发现最优匹配是按大小正序 \(a\) 和倒序 \(b\) 匹配，证明可以考虑反证法或归纳法。
值域较小，考虑从值域入手。开一个值域大小的桶，用两个指针双向（一个从 \(1\to 100\)，另一个从 \(100\to 1\)）维护，每次至少有一个指针会移动，单次回答复杂度 \(O(V)\)，总复杂度 \(O(nV)\)。
const int N=1e5+5,V=105;
int n,a[N],b[N],ta[V],tb[V],tmpa[V],tmpb[V];
int qry(){
for(int i=1;i<=100;++i)tmpa[i]=ta[i],tmpb[i]=tb[i];
int l=1,r=100,maxn=0,tmp;
while(!tmpa[l])l++;
while(!tmpb[r])r--;
while(l<=100&&r>=1){
tmp=min(tmpa[l],tmpb[r]);
tmpa[l]-=tmp,tmpb[r]-=tmp;
maxn=max(maxn,l+r);
while(!tmpa[l])l++;
while(!tmpb[r])r--;
}
return maxn;
}
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i]=read(),b[i]=read();
ta[a[i]]++,tb[b[i]]++;
print(qry()),puts("");
}
return 0;
}
D
显然最小字典序字符串可以先用一次删除末尾操作，再用一些复制操作完成。
我们先想一个算法，再打补丁。
第一个字符一定存在，我们记 \(a_0\) 为第一个字符。
最主要的问题是删到哪？
删掉以从前往后第一个大于 \(a_0\) 的字符为首的后缀。
反例：dbda，若显然 dbdbdb... 劣于 dbdadb...。
我们考虑在 \(a_i\) 与 \(a_0\) 相同时比较它们的下一位，直至一个不相同的。
比较过程：令 \(a_{j\ \bmod\ i}\) 为 \(a_0\) 的比较指针，\(a_k\) 为 \(a_i\) 的比较指针。
注意，\(a_0\sim a_i\) 全都小于等于 \(a_0\)。
- 若 \(a_{j\ \bmod\ i}<a_k\)，则删去以 \(i\) 为首的后缀；
- 若 \(a_{j\ \bmod\ i}>a_k\)，则令 \(i\gets k\)（因为 \(a_0\sim a_k\) 都小于等于 \(a_0\)），继续向后；
- 若 \(k\) 到末尾还相同，则 \(a_0\sim a_{i-1}\) 是一个循环节，删去以 \(i\) 为首的后缀即可（WA on test 2 可以参考）。
还有一些细节，可以看看代码：
const int N=5e3+5;
int n,m;
string a;
int main(){
cin>>n>>m>>a;
int pos=n;
for(int i=1;i<n;++i){
if(a[0]<a[i]){pos=i;break;}
if(a[0]>a[i])continue;
bool f=0;
for(int j=0,k=i;k<n;++j,++k){
if(a[j%i]<a[k]){f=1;break;}
else if(a[j%i]>a[k]){i=k;break;}
else if(k==n-1){f=1;break;}
}
if(f){pos=i;break;}
}
for(int i=0;i<m;++i)cout<<a[i%pos];
return 0;
}