Codeforces Round 1005 div2 (A-D)题解

在这里插入图片描述

A-Brogramming Contest

给定你一个01串，每次你只能将s或者t后缀字符串移到另一个字符串的后面，初始t为空，输入s的长度以及s，问你最少多少次操作可以让s字符串全为0,t中字符串全为1。

这个其实很简单，我第一反应是想到了蜘蛛纸牌的那个移动过程，所以就得到从第一个1开始连续的1和连续的0有多少块就行。之所以是第一个1是因为如果没有1就不需要移动。

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;

void init() {
   

}

int a[N];
int pre[N];

void solve() {
   
    init();

    int n;
    cin>>n;
    string s;
    cin>>s;

    char sign='1';
    int res=0;

    int begin=-1;
    for(int i=0;i<n;i++) {
   
        if(s[i]=='1') {
   
            begin=i;
            break;
        }
    }
    if(begin==-1) {
   
        cout<<0<<"\n";
        return ;
    }

    res =1;
    for(int i=begin;i<n;i++) {
   
        if(s[i]!=sign) {
   
            res ++ ;
            sign = s[i];
        }
    }
    cout<<res<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}

B-Variety is Discouraged

给定一个数组，你的分数就是这个数组的长度减去数组里数字种类数，你可以减去一个连续的子数组，问你能够获得分数最高的情况下长度最短的时候减去的数组l r是什么，如果不能减去就输出0

这个刚开始我看走眼了没看到要让长度最少，心想着直接输出0就结束了，然后wa1，~~所以说要好汉看题~~

总之这道题还是很简单的，因为你每次减去一个数字，长度肯定会减少但是种类数不一定减少，所以说你的操作不会让分数增加，那我们就要尽可能保持分数不变。分数不变就是要减去的子数组中的每个数在数组里数量只有一个。所以我们要做的就是找到最长的所有元素都只有一个的连续子数组

双指针维护一下就好了，代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;
void init() {
   

}

int a[N];
int b[N];
int pre[N];

void solve() {
   
    init();

    int n;
    cin>>n;
    map<int,int>mp;
    int zhi=0;
    for(int i=1;i<=n;i++) {
   
        cin>>a[i];
        if(!mp[a[i]]) {
   
            b[++zhi]=a[i];
        }
        mp[a[i]]++;
    }

    //cout<<zhi<<"\n";
    int l=1,r=1;
    int nowres=0;
    int resl=-1,resr=-1;
    while(r<=n) {
   
        if(mp[a[l]]!=1) {
   
            l++;
            r=l;
            continue;
        }

        while(r+1<=n && mp[a[r+1]]==1) r++;
        if(r-l+1 >= nowres) {
   
            nowres = r-l+1;
            resl=l;
            resr=r;
        }

        l=r+1;
        r=l;
    }

    if(!nowres) cout<<0<<"\n";
    else cout<<resl<<" "<<resr<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}

C-Remove the Ends

给你一个长度为n的数组，每次你都可以任意选择一个位置，然后获得| $a_i$ |个硬币，如果 $a_i$ 是正数的话前面的数字包括它本身会被删除，负数就是后面包括它本身会被删除，问你最多能够那道多少硬币。

第一眼看上去的话这道题会像是DP，但是我们就不好写它的状态，递推以及结果得到方式。所以我们先去寻找一些规律。

经过观察可以发现，对于连续一段的正数，只要我取的合理，那么这段的正数是作为一个整体拿的，负数同理，所以我们可以先将连续的正数以及连续的负数合为一个整体放在数组里 。

既然我们已经将连续的正数以及连续的负数合成整体了，那么在数组里就是正负数交替出现的情况，然后我们尝试模拟一下就可以发现，假设新数组里我要拿走第i个数而这个数是正数的话，为了最优的情况，i前面的正数是都要取完的，负数的话就是i后面的负数都要取完。在取完之后正数可以在继续取后面的正数，也可以直接取后面的全部负数。
所以我们直接遍历第i个位置，如果是正数我们就只取前i个数字里的正数以及后面的所有负数，如果是负数我们就只取i以及后面的所有负数以及i前面的所有正数，在这些情况里取最大值就能得到结果

还有一点就是我们要前面的所有正数以及后面的所有负数，所以我们要计算前缀正数和以及后缀负数绝对值。代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;
void init() {
   

}

int a[N];
int b[N];

void solve() {
   
    init();

    int maxvalue=0;
    int pre1=0;
    int pre2=0;

    int sign=0;
    int n;
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    if(a[1]>0) sign=1;
    else sign=0;

    int nowsum=0;
    int zhi=0;
    for(int i=1;i<=n;i++) {
   
        if(sign==1 && a[i]<0) {
   
            b[++zhi] = nowsum;
            nowsum=a[i];
            sign=0;
        }
        else if(sign==0 && a[i]>0) {
   
            b[++zhi] = nowsum;
            nowsum=a[i];
            sign=1;
        }
        else {
   
            nowsum += a[i];
        }
    }

    if(nowsum!=0) b[++zhi] = nowsum;

    // for(int i=1;i<=zhi;i++) cout<<b[i]<<" ";
    // cout<<"\n";
    if(zhi==1) {
   
        cout<<abs(b[1])<<"\n";
        return ;
    }

    //计算正数的前缀和
    for(int i=1;i<=zhi;i++) {
   
        if(b[i]>0) {
   
            pre1+=b[i];
            b[i]=pre1;
        }
    }
    //计算负数的前缀和
    for(int i=zhi;i>=1;i--) {
   
        if(b[i]<0) {
   
            pre2+=b[i];
            b[i]=pre2;
        }
    }

    for(int i=1;i<=zhi;i++) {
   
        if(b[i]>0) {
   
            if(i==zhi) {
   
                maxvalue = max(maxvalue,b[i]);
            }
            else {
   
                maxvalue = max(maxvalue,b[i]+abs(b[i+1]));
            }
        }
        else {
   
            if(i==1) maxvalue = max(maxvalue,abs(b[1]));
            else maxvalue = max(maxvalue,abs(b[i]) + b[i-1]);
        }
    }
    cout<<maxvalue<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}

D-eating

给定一个n个长度的w数组以及q次询问，每次询问给定一个x，然后从w数组后面往前，如果x≥ $w_i$ ，那么就可以吞并这个数字，x变成x^ $w_i$ ,每次询问都要回答对于x能够吞并多少个数，每次询问的变化不会持续到下一次询问。

D的预处理是挺巧妙的，如果对于位运算不熟练的话还是挺难做的。我们肯定是不能够去直接暴力去寻找的，所以我们需要去找一些优化的方法。首先既然是异或，并且我们又不可能一个一个遍历，那我们应该是要用上异或前缀和。这是第一点

其次是我应该如何遍历。在最开始的时候我想的是二分的方法，但是如果是直接二分是肯定不可以的，毕竟二分的前提是要有序的。那么想想，我们这个是位运算，然后还不能一个一个数字的遍历，那我们要遍历的不就只有位了吗。

所以我们应该从位出发，然后是我要如何知道x是否大于等于 $w_i$ 。很明显，当我当前的最高位比 $w_i$ 高的时候肯定就肯定比他高，如果我当前最高位没有 $w_i$ 高那就肯定是比它小，如果刚好最高位相等的话，就需要判断一遍，如果比它大就进行一次异或，此时最高位变小。

这个时候就可以看得出来为什么我说如果位运算不熟练的话这道题就很难做的了。因为如果只看这些条件的话还是没有一个明确方案的。这里可以怎么样子做呢，就是一个数组last[i][dig]表示当你到第i个数字的时候，如果你当前最高位为dig的时候，那么 i 到 last[i][dig] 里的数字都肯定能够被你吞并。

这样子就相当于我遍历x的位，然后一个指针表示对于当前最高位而言我能够移动到哪个位置，如果遍历完所有的位或者没有可移动的位置了就结束。

代码如下，可以多体味一下这里的last数组：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;

void init() {
   

}

int a[N];
int last[300010][40];
int pre[N];

void solve() {
   
    init();

    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
   
        for(int j=0;j<=30;j++) last[i][j]=1;
    }

    for(int i=1;i<=n;i++) cin>>a[i],pre[i] = pre[i-1] ^ a[i];

    for(int i=1;i<=n;i++) {
   

        if(i>1)
            for(int j=30;j>=0;j--) last[i][j] = last[i-1][j];

        last[i][__lg(a[i])]=i;

        for(int j=29;j>=0;j--) last[i][j] = max(last[i][j],last[i][j+1]);
    }


    while(q--) {
   
        int x;
        cin>>x;

        int idx=n;
        while(idx>=1 && x>0) {
   
            int mxb = __lg(x);

            int nxt = last[idx][mxb];
            x ^= pre[idx] ^ pre[nxt];
            idx = nxt;

            if( a[nxt] > x) break;

            x ^= a[nxt];
            idx--;

        }
        cout<< n - idx<<" ";
    }
    cout<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}

总结：这场比赛其实自己状态下滑的还是挺严重的，B又是看错题又是多加了个去重，然后D自己位运算也不熟练，可能需要自己去特别训练位运算的题目