Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) 题解

比赛链接：http://codeforces.com/contest/948
A. Protect Sheep
题意：给了一个n*m的图，其中.代表空地，S代表羊，W代表狼,D代表狗，羊和狗都不能动，只有狼可以冻，现在狗有无限多个，如果通过给地图放狗可以保护所有的羊都不被吃，那就输出放狗之后的图，如果通过放狗还可以使狼吃羊，那么就输出No。
解法：我们只需要判断每一只羊的上下左右没有狼就好，如果都没有狼，那么一定可以保护，直接在所有的羊周围放狗即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n,m;
char maze[maxn][maxn];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool check(int x,int y){
    if(x>=0&&x<n&&y>=0&&y<m) return true;
    else return false;
}
int main(){
    scanf("%d%d",&n,&m);
    bool flag = true;
    for(int i=0; i<n; i++) scanf("%s", maze[i]);
    for(int i=0;i<n;i++){
        for(int j=0; j<m; j++){
            if(maze[i][j]=='S'){
                for(int k=0; k<4; k++){
                    int tx = i+dir[k][0];
                    int ty = j+dir[k][1];
                    if(check(tx,ty)&&maze[tx][ty]=='W'){
                        flag = false;
                    }
                }
            }
        }
    }
    if(flag){
        puts("Yes");
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
               if(maze[i][j]=='S'){
                for(int k=0;k<4;k++){
                    int tx=i+dir[k][0];
                    int ty=j+dir[k][1];
                    if(check(tx,ty)&&maze[tx][ty]=='.'){
                        maze[tx][ty]='D';
                    }
                }
               }
            }
        }
        for(int i=0;i<n;i++){
            printf("%s\n",maze[i]);
        }
    }else{
        puts("No");
    }
}

B. Primal Sport
题意：假设当前的数是x[i],那么x[i+1]由质数p(p

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n, ans, f[maxn];
int main(){
    scanf("%d",&n);
    ans = n;
    for(int i=2; i<=n; i++){
        if(!f[i]){
            for(int j=2*i; j<=n; j+=i) f[j] = i;
        }
        f[i] = i-f[i]+1;
    }
    for(int i=f[n];i<=n;i++) ans = min(ans, f[i]);
    printf("%d\n", ans);
}

C. Producing Snow
题意：每天会有 ai 个雪球被创建 每天会有bi 个雪球会被融化掉 求每天的融化的 个数
解法：用multiset来搞。每个ai都会被插入multiset，然后根据融化bi的累加值来判断multiset的哪些元素会被全部删除，然后删除之后再更新累加值，说的比较乱，希望代码可以看懂。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
multiset <LL> s;
LL a[maxn], b[maxn];
int main(){
    LL n;
    scanf("%lld", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int j=1; j<=n; j++) scanf("%lld", &b[j]);
    LL d = 0;
    LL add = 0;
    int k = 0;
    for(int i=1; i<=n; i++){
        s.insert(a[i]+add);
        d+=b[i];
        LL re = 0;
        while(s.size()&&*s.begin()-d<=0){
            re += *s.begin()-add;
            s.erase(s.begin());
            k++;
        }
        re += 1LL*(i-k)*b[i];
        add = d;
        printf("%lld ", re);
    }
    printf("\n");
}

D. Perfect Security
题意：可以任意打乱序列b的顺序和a挨着异或，求答案序列的字典序最小值。
解法：很水的一眼题，插入字典树，然后贪心。

#include <bits/stdc++.h>
using  namespace std;
int ch[9000010][2], num[9000010][2], a[300010], b[300010], p[300010], n, k;
void add(int u){
    int now = 0;
    for(int i=30; i>=0; i--){
        int t = (u>>i)&1;
        if(!ch[now][t]) ch[now][t]=++k;
        num[now][t]++;
        now=ch[now][t];
    }
}
int query(int u){
    int now=0,ans=0;
    for(int i=30;i>=0;i--){
        int t=(u>>i)&1;
        if(ch[now][t]&&num[now][t]) --num[now][t],now=ch[now][t];
        else --num[now][t^1], now=ch[now][t^1], ans+=(1<<i);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++) scanf("%d", &b[i]), add(b[i]);
    for(int i=1;i<=n;i++) p[i] = query(a[i]);
    for(int i=1;i<=n;i++) printf("%d ", p[i]);
}

E:Picking String
题意：给出字符串S和T，1e5个询问，每次询问S的一段区间是否能转变成T的一段区间。 转变方式：A->BC，B->AC，C->AB。AAA可以消除。
解法：不会这题啊。。http://blog.csdn.net/weixin_37517391/article/details/79550785
B−>AC−>AAB−>AAAC−>C $B->AC->AAB->AAAC->C$
C−>AB−>AAC−>AAAB−>B $C->AB->AAC->AAAB->B$
A−>BC−>BB $A->BC->BB$
也就是说所有的C等价于B
由于B->AC也就是B->AB，而三个A可以消除，意思就是B前面可以有任意多个A，所以，B前面的紧贴着的A的数量我们可以忽略。
由于B->AB->BBB->ABBB->BBBBB，A->BB->ABB->BBBB也就是说，我们只要有一个A或者B就可以在这个基础上增加偶数个B。
那么问题就比较清楚了。但是T[c,d]串最后的A是一定要被S[a,b]最后的A抵消掉，因为没有操作可以生成A并且把A插入到S[a,b]的后面。
分为如下情况：
如果S[a,b]最后的A不足以抵消掉T[a,b]的A,那么输出0，否则记录S[a,b]后面的A与T[a,b]的后面的A的差值,记作delta2 $如果S[a,b]最后的A不足以抵消掉T[a,b]的A,那么输出0，否则记录S[a,b]后面的A与T[a,b]的后面的A的差值,记作delta2$
如果delta2等于0，那么只需要比较S[a,b]中的B的数量和T[c,d]中的B的数量，那么差值必定要为2的倍数，并且如果T[c,d]中B的数量不为0，那么S[a,b]中B的数量也必须不为0(无法从空串生成BB)。 $如果delta2等于0，那么只需要比较S[a,b]中的B的数量和T[c,d]中的B的数量，那么差值必定要为2的倍数，并且如果T[c,d]中B的数量不为0，那么S[a,b]中B的数量也必须不为0\left(无法从空串生成BB\right)。$
如果delta2>0那么如果S[a,b]中B的数量小于T[c,d]中B的数量，并且差值为偶数时候，S[a,b]多出来的A可以用来生成BB，并且多余的A作为B的前缀可以被消除掉。 $如果delta2>0那么如果S[a,b]中B的数量小于T[c,d]中B的数量，并且差值为偶数时候，S[a,b]多出来的A可以用来生成BB，并且多余的A作为B的前缀可以被消除掉。$
如果delta2>0那么如果S[a,b]中B的数量等于T[c,d]中B的数量，那么delta2一定要被3整除。这样可以通过消除来得到T $如果delta2>0那么如果S[a,b]中B的数量等于T[c,d]中B的数量，那么delta2一定要被3整除。这样可以通过消除来得到T$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
char S[maxn], T[maxn];
int q,a,b,c,d;
int sumS[maxn], sumT[maxn];
int lastS[maxn], lastT[maxn];

int main(){
    scanf("%s %s %d", S,T,&q);
    for(int i=0; S[i]; i++){
        sumS[i+1] = sumS[i]+(S[i]=='C'||S[i]=='B');
        lastS[i+1] = lastS[i];
        if(S[i]=='B'||S[i]=='C') lastS[i+1]=i+1;
    }
    for(int i=0; T[i]; i++){
        sumT[i+1] = sumT[i]+(T[i]=='C'||T[i]=='B');
        lastT[i+1] = lastT[i];
        if(T[i]=='B'||T[i]=='C') lastT[i+1]=i+1;
    }
    while(q--){
        scanf("%d%d%d%d", &a,&b,&c,&d);
        int delta = sumT[d] - sumT[c-1] - (sumS[b]-sumS[a-1]);
        int delta2 = b-max(a-1,lastS[b]) - (d-max(c-1,lastT[d]));
        if(delta<0||delta%2!=0||delta2<0||delta2==0&&!(sumS[b]-sumS[a-1])&&delta>0){
            putchar('0');
            continue;
        }
        if(delta2==0||delta>0||delta2%3==0){
            putchar('1');
        }else{
            putchar('0');
        }
    }
    return 0;
}