Codeforces Round #784 (Div. 4)比赛总结

写在前面

这回刚忙完UML大家一起打cf，才有紧张感，确实那时候有点紧张，打了几个嗝，然后这回是第一次打div4（之前那场太久远了），目标就是冲着AK去的，并且也需要手速。出题当然还算可以，ak了，但是有些题目实在是做得慢hhh。
不过最近水平确实越来越有突破了，最近补了ABC的F，还有div3AK，这回现场AKdiv4，感觉越来越好起来了，虽然是ak，但是时间也没有落下，还是跟上了大部队（脱老师，易老师，龙老师），可惜龙龙最后的F爆int挂了，最后榜单出来了我还往前走了几十名。希望自己下次再接再厉，多多补题！

比赛链接：https://codeforces.com/contest/1669

A - Division?

简单，ifelse即可

B - Triple

题意：找出任意一个出现次数大于等于3的数，否则输出-1
思路：直接拿map存，然后看value是否大于等于3，有的话输出并return

C - Odd/Even Increments

题意：给你一个长度为$n$的序列，问你是否能对全部奇数位或偶数位的+1操作使得所有数最后同奇偶。

换句话说：问你序列中奇数位奇偶性是否相同，偶数位的奇偶性是否相同，如果二者对于自己部分都相同的话，肯定能通过+1变成全部同奇偶

思路：那就直接拿a[1],a[2]作为标兵，所有的数都跟对应的去比较是否同奇偶，最后如果都是相符合的，那么就可以

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    bool ok=true;
    for (int i=3;i<=n;i++)
    {
        if (i%2==0&&a[i]%2!=a[2]%2) ok=false;
        if (i%2==1&&a[i]%2!=a[1]%2) ok=false;
    }
    if (ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

D - Colorful Stamp（思维）

题意：给你$n$个，还有含'W''B''R'的字符串$s$，每次能让相邻的两个盖上"BR"或者反向的"RB"的印章，问你最后经过若干次是否能够变成字符串$s$

思路：推了几个，经过我打cf的经验，直接大胆猜测，只要在两个'W'之间一段字符串含有'R'和'B'即可，如果全是'BBB'或者'RRR'肯定不行，这里特殊判断一下，如果都没有的话也是可以的，说明没有盖章，就是这种情况：'WW'，两个白色里面无需盖章

所以我给字符串首尾都加上'W'，然后for循环去寻找'W'，实际上分成了若干段:"W...W...W..W.WW.....W"，然后用上面分析的去判断每段，时间复杂度$O(2n)$

代码:

inline void Case_Test()
{
    cin>>n>>s;
    s='W'+s+'W';
    n+=2;
    for (int i=1;i<n;i++)
    {
        if (s[i]=='W')
        {
            int p=i-1;
            bool fB=false,fW=false;
            while (p>=0&&s[p]!='W')
            {
                if (s[p]=='B') fB=true;
                else fW=true;
                p--;
            }//往前找
            if (!fB&&!fW) continue;//"WW"
            if (fB&&fW) continue;//符合条件
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

E - 2-Letter Strings

题意：给你若干个长度为2的字符串，问你有多少对满足条件，条件为两个字符串有且仅有一个位置的字母相同，如"ab"和"cb"，而"ab"和"ba"还有"ab"和"ab"都不算

思路：我的方法是用一个二维数组来存有多少个，a[1][0..25]表示第一位有多少个'a'...'z'（对应0...25），a[2][0..25]则是第二位。
然后每次读入就开始计算答案，算完之后把自己也更新进去，这样可以对下次进行贡献答案，这样的原因不用除以二，因为我保证了有序（{3,4}和{4,3}实际上是一样的，但是我保证每次对前面出现过的统计）
但是我们肯定会有重复的，比如之前出现了"ab"，你这会又来一个"ab"，你对于'a'就加了一次，'b'又加了一次，但是这肯定不行的，因为不满足要求，所以要减去你当前字符串出现的次数ans-=mp[s]

也可以换种思想，用a[0..25][0..25]来表示，每次出现的时候循环26次去找当前位的数

代码：

map<string,int> mp;
inline void Case_Test()
{
    cin>>n;
    mp.clear();ans=0;
    for (int i=0;i<26;i++) a[1][i]=a[2][i]=0;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        ans+=a[1][s[0]-'a']+a[2][s[1]-'a'];
        ans-=2*mp[s];//小容斥
        a[1][s[0]-'a']++;a[2][s[1]-'a']++;
        mp[s]++;
    }
    cout<<ans<<endl;
}

F - Eating Candies（双指针+贪心）

题意：给你一个长度为$n$的序列，A在左边往右边吃糖果，B从右边往左边开始吃糖果，不能吃同一个，问你相等的值的时候俩人最多吃多少个

思路：这种题做过好多次，直接双指针+贪心去做，我用sum1和sum2分别表示左右两个人的，如果sum1<sum2那说明A需要往右边再吃，才有可能等于sum2，同理sum1>sum2则需要B往左边再吃，那么相等的时候呢？这个时候暂时是我要的ans，然后随便一个继续吃即可，时间复杂度$O(n)$

也可以用后缀和，去二分，预处理前缀和，每次枚举左边的然后二分右边的判断相等的时候

代码：

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    int l=0,r=n+1,sum1=0,sum2=0;
    ans=0;
    while (l<r-1)
    {
        if (sum1<sum2) sum1+=a[++l];
        else sum2+=a[--r];
        if (sum1==sum2) ans=n-r+1+l;
    }
    cout<<ans<<endl;
}

G - Fall Down（模拟）

题意：给你一个$n\times m$的图，.代表空位,'*'代表石头，可以下落，'o'代表障碍物，不会动。石头下落碰到底部或者碰到障碍物就会停下，如果碰到石头则会堆积，问你最后是什么样的

思路：模拟，既然落地也算，那我最后n+1行也算石头，强行加上，然后去枚举，数据比较小，就是需要点时间写

代码：

char c[N][N];
inline void Case_Test()
{
    cin>>n>>m;
    rep(i,1,n) rep(j,1,m) 
    {
        vis[i][j]=0;
        cin>>c[i][j];
        if (c[i][j]=='o') vis[i][j]=1;
    }
    for (int i=1;i<=m;i++) vis[n+1][i]=1;
    for (int j=1;j<=m;j++)
    {
        for (int i=n;i>=1;i--)
        {
            if (c[i][j]=='*')
            {
                bool find=false;
                int pos=i;
                for (int k=i+1;k<=n+1;k++)
                {
                    if (vis[k][j])
                    {
                        pos=k-1;
                        find=true;
                        break;
                    }
                }
                vis[pos][j]=1;
                c[i][j]='.';
                c[pos][j]='*';
            }
        }
    }
    rep(i,1,n)
    {
        rep(j,1,m)
            cout<<c[i][j];
        cout<<endl;
    }
    cout<<endl;
}

H - Maximal AND（位运算）

题意：你有$n$个数字，$k$次操作，每次操作可以使得某个数字与$2^j(1\leq j \leq 30)$进行或运算(OR)，问最后$n$个数组进行与运算(AND)的最大值是多少

思路：我感觉一般这种简单的题就直接开$30$位数组来存，AND要想为$1$的话，就必须要那一位的所有都为$1$，这个时候才会贡献$2^j$，既然这样，那么我们就从最高位开始，因为你为了要求最大，肯定是要从最高位开始贪心，好比你有$n$次修改，你修改第$4$位和我修改第$30$位是不一样的，那么怎么看是否修改成功呢？

我们开一个$30$位的数组，然后对于每个数都拆分成二进制来看，如果当前为是0，说明需要用一次操作才能让它变为$1$，这个时候我们记录到数组里面。

最后统计答案的时候，我们从高位往下开始扫，如果$k$是比当前数组位要大的，根据贪心的思想我们是需要修改的，这样才是最大，那么这个时候ans+=(1<<j)并且记得k-=a[j]，因为这个时候减少了这么多次操作。

代码：

inline void Case_Test()
{
    cin>>n>>k;
    for (int i=0,p=1;i<=32;i++,p*=2) b[i]=p; 
    for (int i=0;i<=40;i++) a[i]=0;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        for (int j=0;j<=31;j++)
            if (x&(1<<j)) continue;
            else a[j]++;
    }
    ans=0;
    for (int i=30;i>=0;i--)
        if (k>=a[i]) 
            k-=a[i],ans+=b[i];
    cout<<ans<<endl;
}