Codeforces Round 893 (Div. 2) A–E2

我，上紫；爱来自中国🥰

A. Buttons

题意

有 $a+b+c$ 个按钮，其中 $a$ 个按钮只能小 A 按，$b$ 个按钮只能小 B 按，$c$ 个按钮小 A 小 B 都能按。
小 A 先手，当一个人没有按钮可按时，他就输了。

请问双方都按照最优策略行动情况下，谁会获胜？

解法

最优策略显然是先按 $c$ 然后再按自己的。
所以若 $c$ 是奇数，我们给 $b$ 减 $1$。

然后问题就转化成只有按钮 $a$ 和 $b$，小 A 先手。显然当 $a>b$ 时小 A 获胜，否则小 B 获胜。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int a=read(),b=read(),c=read();
    if(c%2==1)b--;

    // 现在 A 先手
    if(a>b)puts("First");
    else puts("Second");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. The Walkway

题意

小 P 正在从 $1$ 走到 $n$。有 $m$ 个卖饼干的在 $s_1,s_2,\ldots,s_m$，以及常数 $d$。

当小 P 走上一格时，只要三个条件中满足了任意一个，她就会吃一块饼干：

• 这是第 $1$ 格；
• 这一格上有人在卖饼干；
• 在前 $d-1$ 个格中（不包括这一格），小 P 都没有吃过饼干。

现在你可以移除恰好一个卖饼干的人，请求出小 P 最少会吃几块饼干，以及有几种移除的方案能够达到这个最小值。

解法

显然是 $O(m)$ 模拟删除每一个人的情况。
细节较多，见代码以及注释。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read(),m=read(),d=read();
    vector<int> sellers;
    sellers.push_back(1); // 在 1 的地方一定会吃饼干
    bool have1 = 0;
    for(int i=0;i<m;i++){
        int a=read();
        if(a!=1)sellers.push_back(a);
        else have1=1; // 那么如果 1 有人买饼干就先忽略
    }

    // res 是没有移除人时候的饼干数量
    int res = sellers.size(); 
    sellers.push_back(n+1);
    for(int i=0;i<sellers.size()-1;i++){
        res += (sellers[i+1]-sellers[i]-1)/d; 
    }

    int ans,cnt;
    if(have1)ans=res,cnt=1; // 如果 1 有人卖，也就相当于可以不移除，ans就变成res
    else ans=INT_MAX; // 要不然ans还是INF

    for(int i=1;i<sellers.size()-1;i++){
        int k = res; // 计算删除第 i 个人之后的答案
        k --; // 第 i 个人所在的格的饼干减掉
        k -= (sellers[i]-sellers[i-1]-1)/d; // 减掉前一个区间
        k -= (sellers[i+1]-sellers[i]-1)/d; // 减掉后一个区间
        k += (sellers[i+1]-sellers[i-1]-1)/d; // 加上合并后的大区间
        if(k<ans){ // 如果答案更新了
            ans = k;
            cnt=1; // 那么cnt就是1个
        }
        else if(k==ans)cnt++; // 如果有多个等于答案的，那么增加数量
    }


    printf("%d %d\n",ans,cnt);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Yet Another Permutation Problem

题意

给定 $n$，求出一个排列，使得 $n$ 对相邻数（第一个和最后一个视为相邻）的最大公约数不同数量最大。

【加强版】洛谷P9345 夕阳西下几时回

解法

首先我们知道答案的上界为 $\left\lfloor\dfrac{n}{2}\right\rfloor$，这是因为对于两个不同的数，想要获得最大公约数为 $d$，则两个数至少为 $d,2d$，显然对大于 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 的数是不可能的。

然后这个上界总是能取到，只要采用如下构造方式：

• 对于 $i=1\sim\left\lfloor\dfrac{n}{2}\right\rfloor$，将 $i$ 和 $2i$ 安排相邻即可。

如代码所示：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e5+5;
bool in[N]; // 是否已经在 arr 里了
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++)in[i]=0;
    vector<int> arr;
    for(int i=1;i<=n/2;i++){
        if(i%2==0)continue;
        arr.pb(i);in[i]=1;
        arr.pb(i*2);in[i*2]=1;
        int k=i;
        while(k*4<=n){
            k*=2;
            arr.pb(k*2);
            in[k*2]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(!in[i])arr.pb(i); // 剩下还没放进去的全部丢到后面
    }

    for(int x:arr){
        printf("%d ",x);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Trees and Segments

题意

给定一个 $0-1$ 序列，长度为 $n$，你可以翻转不超过其中 $k$ 位。
设 $L_0$ 为最长连续 $0$ 长度（没有 $0$ 则 $L_0=0$），$L_1$ 为最长连续 $1$ 长度（没有 $1$ 则 $L_1=0$），
请对于 $a=1\sim n$，分别求出一种翻转方案，使得 $a\cdot L_0 + L_1$ 最大。
输出这 $n$ 个最大值。

$n\le 3000$。

解法

显然复杂度为 $O(n^2)$。

我们考虑枚举所有可能的 $L_0$ 的情况下，最大的 $L_1$ 是多少。
如何枚举呢？

对于每个 $L_0$ 的长度，我们枚举所有取到 $L_0$ 的区间的左端点。这个枚举是 $O(n^2)$ 的。通过预先计算一次前缀和，我们可以 $O(1)$ 求出如果要使这一段取到 $L_0$ 需要翻转几位。如果翻转的位数大于 $k$，那么舍去，否则我们就用剩下的次数在一个前缀和一个后缀中找出使用 $p$ 次翻转最长的 $1$ 的长度，而这个问题可以动态规划 $O(n^2)$ 解决。

求出之后只需要对每一个 $L_0$ 和 $a$ 分别枚举，就可以再 $O(n^2)$ 一次求出答案。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 3005;
char a[N];
int s[N];
int dp1[N][N],dp1mx[N][N];
int dp2[N][N],dp2mx[N][N];
int mxVal[N];
int ans[N];

void solve(int kase){
    int n=read(),k=read();
    scanf("%s",a+1);
    for(int i=1;i<=n;i++){
        a[i]-='0';
        s[i]=s[i-1]+a[i];
    }

    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            dp1[i][j]=dp1mx[i][j]=0;
            dp2[i][j]=dp2mx[i][j]=0;
        }
    }
    for(int i=0;i<=n+1;i++){
        mxVal[i]=ans[i]=INT_MIN;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(j==0){
                if(a[i]==1)dp1[i][j]=1+dp1[i-1][j];
                else dp1[i][j]=0;
            }
            else{
                dp1[i][j]=dp1[i][j-1];
                if(a[i]==1)dp1[i][j]=max(dp1[i][j],dp1[i-1][j]+1);
                else dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+1);
            }
            dp1mx[i][j]=max(dp1mx[i-1][j],dp1[i][j]);
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=0;j<=n;j++){
            if(j==0){
                if(a[i]==1)dp2[i][j]=1+dp2[i+1][j];
                else dp2[i][j]=0;
            }
            else{
                dp2[i][j]=dp2[i][j-1];
                if(a[i]==1)dp2[i][j]=max(dp2[i][j],dp2[i+1][j]+1);
                else dp2[i][j]=max(dp2[i][j],dp2[i+1][j-1]+1);
            }
            dp2mx[i][j]=max(dp2mx[i+1][j],dp2[i][j]);
        }
    }

    mxVal[0]=dp1mx[n][k];
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int needcnt = (s[i+len-1]-s[i-1]);
            if(needcnt>k)continue;
            int remain = k-needcnt;
            mxVal[len] = max({mxVal[len],dp1mx[i-1][remain],dp2mx[i+len][remain]});
        }
    }

    for(int len=0;len<=n;len++){
        for(int f=1;f<=n;f++){
            ans[f]=max(ans[f],f*len+mxVal[len]);
        }
    }

    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E2. Rollbacks (Hard Version)

题意

维护一个数据结构，支持：

• 末尾添加一个数；
• 删除末尾的 $k$ 个数；
• 查询序列中不同的数的个数；
• 撤销上一次修改操作；

强制在线。

解法

考虑用 $10^6$ 个 set 维护每个数现在出现的所有位置。
使用树状数组维护不同的数的个数，只有每个数第一次出现的位置是 $1$，其他是 $0$。

接下来考虑撤销操作。我们用一个数组存目前的序列，但是对于删除不会真的删除，而是直接把代表数组尾的指针前移即可。这样就保留了删除的信息，那么就可以进行进行撤销了。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e6+6;

int t[N];
int lowbit(int x){
    return x&(-x);
}
int query(int i){
    int res = 0;
    for(;i;i-=lowbit(i)){
        res += t[i];
    }
    return res;
}
void add(int i,int k){
    for(;i<N;i+=lowbit(i)){
        t[i]+=k;
    }
}

set<int> id[N];
int a[N],s[N];
int ptr=0;

void erase(int pos){
    if(a[pos]==-1)return;
    if(id[a[pos]].size()){
        add(*id[a[pos]].begin(),-1);
        id[a[pos]].erase(pos);
    }
    if(id[a[pos]].size()){
        add(*id[a[pos]].begin(),1);
    }
}
void insert(int pos){
    if(a[pos]==-1)return;
    if(id[a[pos]].size()){
        add(*id[a[pos]].begin(),-1);
    }
    id[a[pos]].insert(pos);
    if(id[a[pos]].size()){
        add(*id[a[pos]].begin(),1);
    }
}


int main(){
    memset(a,-1,sizeof(a));
    int q=read();
    stack<pii> changes;
    while(q--){
        char op[2];
        scanf("%s",op);
        if(op[0]=='+'){
            int x=read();
            int mem = a[ptr+1];
            erase(ptr+1);
            a[ptr+1]=x;
            insert(ptr+1);
            ptr++;
            changes.push({1,mem}); // 增加，原来是mem
        }
        else if(op[0]=='-'){
            int k=read();
            ptr -= k;
            changes.push({-1,k}); // 减少了 k 个数
        }
        else if(op[0]=='?'){
            printf("%d\n", query(ptr));
        }
        else{
            auto [u,v]=changes.top();changes.pop();
            if(u==1){
                erase(ptr);
                a[ptr]=v;
                insert(ptr);
                ptr--;
            }
            else if(u==-1){
                ptr+=v;
            }
        }
        fflush(stdout);
        // printf("ptr=%d\n",ptr);
    }
    return 0;
}