Codeforces Round 893 Div.2 A~E2
有 \(a+b+c\) 个球。
其中的 \(a\) 个只能被先手取，\(b\) 个只能被后手取，\(c\) 个双方都可以取。双方轮流取球，每次取走一个，无法取球者输。
\(T\) 组询问，每次给定 \(a,b,c\) 问哪一方必胜。
考虑到只需要关心谁先不能取即可。
显然能取必定是先取那 \(c\) 个。直接令 \(a'=a+\lceil \frac{c}{2}\rceil,b'=b+\lfloor\frac{c}{2}\rfloor\)。比谁大谁小即可。
你背着一个有无穷多饼干的书包去逛街。
街上从左到右一共有 \(n\) 个摊位和 \(m\) 个商人，第 \(i\) 个商人在第 \(s_i\) 个摊位卖饼干。
你从最左边开始，向右依次走过第 \(1,2,\dots,n-1,n\) 个摊位，从一个摊位走到和它相邻的摊位需要 \(1\) 分钟。
每当走过第 \(i\) 个摊位时，你会依照这样的条件吃饼干：
- 如果这个摊位上有一个商人，则从商人那里购买一个饼干并立即吃掉。
- 否则如果你还没有吃过饼干，则从书包里拿出一个饼干并立即吃掉。
- 否则如果你前一次吃饼干到现在已经过了 \(d\) 分钟，也就是你在第 \(\max(i-d+1,1)\sim i-1\) 个摊位都没有吃饼干，则从书包里拿出一个饼干并立即吃掉。
注意这些条件不会同时满足，亦即你在同一个摊位不会吃掉超过 \(1\) 个饼干。
如今人员拥挤，管理部门需要移除恰好一个商人。
你想知道怎样移除一个商人使你能吃到的饼干最少。
请输出移除一个商人后你能吃到的最少饼干数量，以及有多少种移除方案使你能吃的饼干最少。
\(2\le d\le n\le 10^9\)，\(2\le m\le n\)，\(1\le s_i\le n\)，\(s_i\) 单调递增，\(\sum m\le 10^5\)。
注意到原则： 简化边界判断
为了满足在第一个位置吃东西，可以建立 \(s_0=1-d\)，顺带为了方便最后一个位置判断，建立 \(s_{m+1}=n+1\)。
然后设 \(w_i=\lfloor\frac{s_i-s_{i-1}-1}{d}\rfloor\)，这是两个位置之间的贡献。
则在不删人的情况下， \(ans=m+\sum_{i=1}^{m+1}w_i\)。
那么考虑删掉 \(i\)，则 \(\Delta w_i=w_{i-1}+w_{i}+1-\lfloor\frac{s_{i+1}-s_{i-1}-1}{d}\rfloor\)。
显然，\(\Delta w_i\le 1\)。所以满足条件的个数为： \(\sum_{i=1}^m \Delta w_i,ans'=ans-1\)。
注意若这个个数为0，则满足条件的个数为 \(m,ans'=ans\)
signed main(){
int t=read();
while(t--){
int m,d;k=0;n=read(),m=read(),d=read();s[++k]=-d+1;
for(int i=1;i<=m;i++)s[++k]=read();int tag=0,ans=0;
if(d==1){
cout<<n<<" "<<m<<"\n";continue;
}
s[++k]=n+1;
for(int i=1;i<k;i++)w[i]=(s[i+1]-s[i]-1)/d,ans+=w[i];ans+=m;
for(int i=2;i<k;i++){
if((s[i+1]-s[i-1]-1)/d<w[i]+w[i-1]+1)++tag;
}
if(tag)cout<<ans-1ll<<" "<<tag<<"\n";
else cout<<ans<<" "<<m<<"\n";
}
}
要求构造一个 \(n\) 的排列，编号为 \(0\sim n-1\)，使得 \(\sum \gcd(a_i,a_{(i+1)\bmod n})\) 最大。
n=5: 1 2 4 3 5
n=7: 1 2 3 6 4 5 7
n=10: 1 2 3 4 8 5 10 6 9 7
观察样例，不难发现令 \(b_i=\gcd(a_i,a_{(i+1)\bmod n})\)，则最大时 \(b\) 中会出现 \(2\sim \lfloor \frac{n}{2}\rfloor\) 各一个，其余全是1.
那么我们倍增去构造这些值即可。这是必定可以构造出来的。(想一想，为什么)
void get(int x){
if(v[x]||x>n)return ;
b[++num]=x,v[x]=1;
get(x<<1);
}
//main
cin>>n;num=0;
for(int i=1;i<=n;i++){
get(i);
}
for(int i=1;i<=n;i++)if(!v[i])b[++num]=i;
for(int i=1;i<=n;i++)v[i]=0;
for(int i=1;i<=n;i++)cout<<b[i]<<" ";
cout<<"\n";
给出一个01串，可以进行不超过 \(k\) 次将一个位取反的操作。
设 \(l_0\) 为更改后最长的0段长度，设 \(l_1\) 为更改后最长的1段长度。
对于每一个 \(a\in[1,n]\)，求 \(al_0+l_1\) 的最大值。
\(n\le 3000\)
简单问题。其实拆一下变成 \(l_0+l_1+(a-1)l_0\)。我们不妨枚举 \(l_0\) 的长度，然后求当前状态下 \(l_1\) 的最大值即可。
不妨设 \(f_x\) 表示在最长0段长 \(x\) 时，最长1段的最大长度。
则 \(ans_a=\max xa+f_x\)。
考虑求出 \(f\)，怎么搞。其实也是容易的。我们可以枚举 \(x\)，再枚举这个0段的区间左右端点 \(l,r(r-l+1=x)\)。
可以计算出在 \([l,r]\) 内需要更改的次数 \(c\)，然后问题化为：在 \([1,l-1],[r+1,n]\) 中，使用不超过 \(k-c\) 次修改，使得1段最长的长度。
这两边是不同的两个同类子问题，可以通过动态规划求得答案。
设 \(pre_{i,j}\) 表示在 \([1,i]\) 中，最多修改 \(j\) 次，最长1段长度，设 \(suf_{i,j}\) 表示在 \([i,n]\) 中，最多修改 \(j\) 次，最长1段长度。
则分为两种情况：最长 \(1\) 段的末尾是否是 \(i\)。
对于不是 \(i\) 的情况，有 \(pre_{i,j}=pre_{i-1,j},suf_{i,j}=suf_{i+1,j}\)。
对于是 \(i\) 的情况，可以向前/后扫一遍，设扫到 \(j\)，扫到 \(c\) 个0，则 \(pre_{i,c}=suf_{i,c}=|i-j|+1\)。
两种情况取较大值即可。
最后本要做一个后缀最小值，但做不做无所谓了，等价的。
cin>>n>>m;
for(int i=1;i<=n;i++){
char x;cin>>x;a[i]=x-'0';
}
for(int i=0;i<=n;i++)f[i]=ans[i]=-inf;
for(int i=0;i<=n+1;i++)for(int j=0;j<=n;j++)pre[i][j]=suf[i][j]=0;
for(int i=1;i<=n;i++){
int c=0;
for(int j=0;j<=n;j++)pre[i][j]=pre[i-1][j];
for(int j=i;j;--j){
c+=(!a[j]);
pre[i][c]=max(pre[i][c],i-j+1);
}
}
f[0]=pre[n][m];
for(int i=n;i;--i){
int c=0;
for(int j=0;j<=n;j++)suf[i][j]=suf[i+1][j];
for(int j=i;j<=n;j++){
c+=(!a[j]);
suf[i][c]=max(suf[i][c],j-i+1);
}
}
for(int i=1;i<=n;i++){
int c=0;
for(int j=i;j<=n;j++){
c+=a[j];if(c>m)break;
f[j-i+1]=max(f[j-i+1],max(pre[i-1][m-c],suf[j+1][m-c]));
}
}
for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)ans[i]=max(ans[i],i*j+f[j]);
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<"\n";
维护一个初始为空的序列，支持以下操作：
- \(\texttt{+ }x\)：在序列末端插入 \(x\)；
- \(\texttt{- }k\)：在序列末端删除 \(k\) 个数（\(k\) 不超过当前序列长度）；
- \(\texttt{?}\)：查询序列中不同的数字个数；
- \(\texttt{!}\)：撤回前一个 \(\texttt +/\texttt -\) 操作。
\(q\) 次操作，强制在线，\(1\le q,x\le 10^6\)，询问操作不超过 \(10^5\)。
#include<iostream>
#include<cstdio>
using namespace std;
int cnt;
struct node {
int lc, rc;
}t[21000005];
void update(int &s,int L,int R,int pos,int dis) {
s=++cnt;int mid=L+R>>1;
t[s]=t[pos];
if (L==dis&&R==dis)return;
if (dis>=L&&dis<=mid)update(t[s].lc,L,mid,t[pos].lc,dis);
else update(t[s].rc,mid+1,R,t[pos].rc,dis);
}
int find(int pos,int L,int R, int dis) {
int s=pos;
if(!s)return 0;
if(L==R)return 1;int mid=L+R>>1;
if(dis<=mid)return find(t[s].lc,L,mid, dis);
else return find(t[s].rc,mid+1,R, dis);
}
int id,lst[1050000],len,c;
int f[1000005][20],s[1050000],ver[1050000];
void add(int x,int pos){
lst[pos]=pos-1;
ver[pos]=ver[pos-1];
s[pos]=s[pos-1];f[pos][0]=pos-1;
for(int i=1;i<20;i++)f[pos][i]=f[f[pos][i-1]][i-1];
if(find(ver[pos],1,1e6,x))return ;
update(ver[pos],1,1e6,ver[pos],x);
s[pos]++;
}
void del(int k,int pos){
lst[pos]=pos-1;
int id=pos-1;
for(int i=0;i<20;i++)if((k>>i)&1)id=f[id][i];
ver[pos]=ver[id],s[pos]=s[id];
for(int i=0;i<20;++i)f[pos][i]=f[id][i];
}
void move(int pos){
int id=lst[pos-1];
lst[pos]=lst[id];ver[pos]=ver[id],s[pos]=s[id];
for(int i=0;i<20;i++)f[pos][i]=f[id][i];
}
int solve(int pos){
lst[pos]=lst[pos-1],ver[pos]=ver[pos-1],s[pos]=s[pos-1];
for(int i=0;i<20;i++)f[pos][i]=f[pos-1][i];
return s[pos];
}
char o;
int main() {
int t,pos=0;
ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin>>o;++pos;
if(o=='+'){
int k;cin>>k;
add(k,pos);
}
else if(o=='-'){
int k;cin>>k;
del(k,pos);
}
else if(o=='!'){
move(pos);
}
else {cout<<solve(pos)<<"\n";cout.flush();}
}
return 0;
}//codeforces