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

A. Protect Sheep

签到

B. Primal Sport 模拟

题意有点难懂啊，但理解了，观察（理解）一下就好了

C. Producing Snow 模拟

题意

给n天，每天都有一堆新的v[i]体积的雪，每天每堆雪的消融量t[i]，一堆雪体积为0时便不在消融，问n天每天的消融量

分析

突破口是每天的消融量都与前面的雪还剩多少有关，所以只要找到每天的雪在那天全部消融完即可，对t[i]求前缀和sum[i]，是单调函数，二分找到临界点即可，再对临界点求个前缀和即可

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

const int maxn = 100000 + 5;
int n;
int v[maxn], t[maxn];
ll sum[maxn];
ll answer[maxn];
ll k[maxn];

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &v[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d", &t[i]);
        sum[i]=sum[i-1]+t[i];
    }
    for(int i=1;i<=n;i++){
        int p=lower_bound(sum+1, sum+n+1, v[i]+sum[i-1])-sum;
        answer[i]+=1;
        ll num=sum[p]-sum[i-1];
        k[p]-=(num-v[i]);
        answer[p+1]-=1;
    }
    for(int i=1;i<=n;i++){
        answer[i]+=answer[i-1];
        printf("%lld ", answer[i]*t[i]+k[i]);
    }
    return 0;
}

View Code

D. Perfect Security 字典树

经典字典树上贪心题

E. Picking Strings 模拟

题意

给两个字符串T、S，现给出一些变化方式，给出q个询问，每个询问a，b，c，d，问T的子串T[a,b]能否变成子串S[c,d]

变化方式:

A->BC B->AC C->AB AAA->空

分析

根据给出变化，可以推出

1、B<->C

2、B前面的A 可以全部消除

3、A可以变成偶数个B

4、一个B可以额外增加偶数个B（前提有B）

所以我们直接根据T[a,b]和S[c,d]的后缀A的数量进行分类讨论，再对T[a,b]和S[c,d]中的B的数量进行讨论即可

#include <iostream>
#include <cstdio>
#include <cstring>
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]-sumS[b]+sumS[a-1]-sumT[c-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; 
}

View Code