Codeforces Round #442 (Div. 2) 题解

题目链接：http://codeforces.com/contest/877

A. Alex and broken contest

题意：问给定的串是否恰好只能匹配一个题上给出的人名。

解法：暴力匹配即可。

#include <bits/stdc++.h>
using namespace std;
string a[5]={"Danil","Olya","Slava","Ann","Nikita"};
int main(){
    string s;
    cin>>s;
    int cnt = 0;
    for(int i=0;i<s.size();i++){
        string t1="",t2="",t3="",t4="";
        for(int j=i;j<i+5&&j<s.size();j++) t1+=s[j];
        for(int j=i;j<i+4&&j<s.size();j++) t2+=s[j];
        for(int j=i;j<i+3&&j<s.size();j++) t3+=s[j];
        for(int j=i;j<i+6&&j<s.size();j++) t4+=s[j];
        if(t1==a[0]||t1==a[2]) cnt++;
        if(t2==a[1]) cnt++;
        if(t3==a[3]) cnt++;
        if(t4==a[4]) cnt++;
    }
    if(cnt==1) puts("YES");
    else puts("NO");
}

B. Nikita and string

题意：求满足aba这种结构(ab和ba还有全b都可以)的最长串，你可以删除一些字符。n小于等于5000.

解法：维护a和b字符个数的前缀和，那么枚举两个点，利用前缀和相当于做到O(1)删除。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
char s[maxn];
int A[maxn], B[maxn];
int main(){
    scanf("%s", s+1);
    int len = strlen(s+1);
    for(int i=1; i<=len; i++){
        A[i]=A[i-1]+(s[i]=='a');
        B[i]=B[i-1]+(s[i]=='b');
    }
    int ans = max(A[len], B[len]);
    for(int i=0; i<=len; i++){
        for(int j=i+1; j<=len; j++){
            ans = max(ans, A[i]+B[j]-B[i-1]+A[len]-A[j]);
        }
    }
    printf("%d\n", ans);
}

C. Slava and tanks

题意：有一行n列个格子，每个格子都存在一个或多个坦克，Slava会向格子内扔炸弹，当坦克第一次被炸时会随机向相邻的格子移动，第二次被炸将会损毁。问最少需要几次才能摧毁所有的坦克，并输出投入炸弹的顺序。

解法：我们可以先对偶数位的格子投放炸弹，此时被炸的坦克一定会移向奇数位的格子，之后对奇数位的格子投放炸弹，之前移过来的坦克已损毁，但初始位于奇数位的坦克会移向偶数位的格子，我们再对偶数位的格子投放炸弹。这时所有坦克无论在哪都必定损毁。

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

int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n", n+n/2);
    for(int i=2;i<=n;i+=2) printf("%d ", i);
    for(int i=1;i<=n;i+=2) printf("%d ", i);
    for(int i=2;i<=n;i+=2) printf("%d ", i);
    printf("\n");
}

D. Olya and Energy Drinks

题意：给出一张n*m的地图，给定起点和终点，一个人从起点出发，每一秒内能向一个方向走1~k中的任意步数，问从起点到终点最少需要花费的时间，如果不能到达，则输出-1。

解法：这道题跟简单的走迷宫唯一不一样的就是每一秒可以走多步，那么我们只要去枚举每个方向及在该方向上走的步数。需要注意的是，为了防止TLE，我们仍需要用vis数组来标记，但是之前的是标记该位置是否经过。现在需要保存该位置能否从四个方向到达的情况，这里我们用二进制来表示这个状态。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 1010;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char maze[maxn][maxm];
int n, m, k, x1, x2, y1, y2;
int vis[maxn][maxm];
int dis[maxn][maxn];
struct node{
    int x,y;
};
bool check(int x, int y){
    if(x>=1&&x<=n&&y>=1&&y<=m&&maze[x][y]!='#') return true;
    else return false;
}
int main(){
    scanf("%d %d %d", &n,&m,&k);
    for(int i=1; i<=n; i++) scanf("%s", maze[i]+1);
    scanf("%d %d %d %d", &x1,&y1,&x2,&y2);
    node now; now.x=x1,now.y=y1;
    queue <node> q;
    q.push(now);
    vis[x1][y1]=(1<<4)-1;
    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now.x==x2&&now.y==y2) return 0*printf("%d\n", dis[x2][y2]);
        for(int i=0; i<4; i++){
            for(int j=1; j<=k; j++){
                node nex;
                nex.x = now.x+dir[i][0]*j;
                nex.y = now.y+dir[i][1]*j;
                if(!check(nex.x,nex.y)||vis[nex.x][nex.y]&(1<<i)) break;
                bool ok = 0;
                if(!vis[nex.x][nex.y]) ok=1;
                vis[nex.x][nex.y]|=(1<<i);
                if(ok){
                    dis[nex.x][nex.y]=dis[now.x][now.y]+1;
                    q.push(nex);
                }
            }
        }
    }
    return 0*puts("-1");
}

E. Danil and a Part-time Job

题意：给你一棵根为1的树, 每个点的权值是0或1, get x表示求x子树的1的个数, pow x表示把x的子树1变0, 0变1
解法：DFS序加支持区间求和区间加的线段树即可，经典老题。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
vector <int> G[maxn];
int dfsclk, n, q, L[maxn], R[maxn], a[maxn], b[maxn], fa[maxn];
struct node{
    int l,r,sum,lazy;
}Tree[maxn*4];
void pushup(int rt){
    Tree[rt].sum=Tree[rt*2].sum+Tree[rt*2+1].sum;
}
void pushdown(int rt){
    if(Tree[rt].lazy){
        Tree[rt*2].lazy^=Tree[rt].lazy;
        Tree[rt*2+1].lazy^=Tree[rt].lazy;
        Tree[rt*2].sum=Tree[rt*2].r-Tree[rt*2].l+1-Tree[rt*2].sum;
        Tree[rt*2+1].sum=Tree[rt*2+1].r-Tree[rt*2+1].l+1-Tree[rt*2+1].sum;
        Tree[rt].lazy=0;
    }
}
void build(int l, int r, int rt){
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].lazy=0;
    if(l==r){
        Tree[rt].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l, mid, rt*2);
    build(mid+1, r, rt*2+1);
    pushup(rt);
}
void update(int L, int R, int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        Tree[rt].lazy^=1;
        Tree[rt].sum=Tree[rt].r-Tree[rt].l+1-Tree[rt].sum;
        return;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) update(L,R,rt*2);
    else if(L>mid) update(L,R,rt*2+1);
    else{
        update(L,mid,rt*2);
        update(mid+1,R,rt*2+1);
    }
    pushup(rt);
}
int query(int L, int R, int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].sum;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) return query(L,R,rt*2);
    else if(L>mid) return query(L,R,rt*2+1);
    else return query(L,mid,rt*2)+query(mid+1,R,rt*2+1);
}
void dfs(int u){
    L[u]=++dfsclk;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]) continue;
        dfs(v);
    }
    R[u]=dfsclk;
}

int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++){
        scanf("%d", &fa[i]);
        G[fa[i]].push_back(i);
    }
    dfs(1);
    for(int i=1; i<=n; i++){
        scanf("%d", &b[i]);
        a[L[i]] = b[i];
    }
    build(1,n,1);
    scanf("%d", &q);
    while(q--){
        string s;
        cin >> s;
        int id;
        scanf("%d", &id);
        if(s=="pow") update(L[id],R[id],1);
        else printf("%d\n", query(L[id],R[id],1));
    }
    return 0;
}

F. Ann and Books

题意：n本书的序列, 第i本书有a[i]若干道数学或者经济学题目, q个询问[li, ri], 要求输出[li, ri]中, 满足”数学题总数比经济学题总数多k道”的子区间数量

解法：首先对数据进行预处理要求数学题数-经济学题数 = k, 那么对经济学题目数取负数(a[i] = -a[i]), 然后求前缀和pre[i], 这样处理后, 子区间[a, b]满足”数学题总数比经济学题总数多k道” 就相当于 pre[b] - pre[a-1] == k 如果我们已经知道了区间[a, b]的答案ans, 并且已经统计好了区间[a-1, b]中所有pre[i]各个数字的个数cnt[pre[i]]。那么对于区间[a, b-1], [a, b+1], [a-1, b], [a+1, b]的答案, 我们可以根据[a, b]的答案O(1)求出, 具体看代码, 接下来就可以用莫队算法了，还要注意这里莫队的复杂度O(q*sqrt(n))，所以离散化必须O(1)，我们把需要离散化的值存到数组里直接取出来即可。具体细节看代码吧。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;
typedef long long LL;
int n, k, q, block;
int t[maxn], a[maxn];
LL pre[maxn];
int id[3][maxn];//id[0][i], id[1][i], id[2][i]分别表示pre[i], pre[i-k], pre[i-k]离散化后的值
struct node{
    int id,l,r;
}Q[maxn];
LL Ans[maxn];//记录答案
LL ans, cnt[maxn];//cnt[i]表示i出现了多少次
void update(int pos, int x, int add){
    if(add==1){
        ans+=cnt[x];
        cnt[pos]++;
    }
    else{
        cnt[pos]--;
        ans-=cnt[x];
    }
}
bool cmp(const node&x, const node&y){
    if((x.l-1)/block+1==(y.l-1)/block+1) return x.r<y.r;
    return x.l<y.l;
}

int main(){
    scanf("%d %d", &n,&k);
    for(int i=1; i<=n; i++) scanf("%d", &t[i]);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++){
        if(t[i]==1) pre[i] = pre[i-1]+a[i];
        else pre[i] = pre[i-1]-a[i];
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){\
        scanf("%d %d", &Q[i].l,&Q[i].r);
        Q[i].id = i;
    }
    block = sqrt(n);
    sort(Q+1, Q+q+1, cmp);
    int idx = 1;
    unordered_map <LL, int> mp;
    for(int i=0; i<=n; i++){
        mp[pre[i]] = idx++;
        mp[pre[i]-k] = idx++;
        mp[pre[i]+k] = idx++;
    }
    for(int i=0; i<=n; i++){
        id[0][i] = mp[pre[i]];
        id[1][i] = mp[pre[i]+k];
        id[2][i] = mp[pre[i]-k];
    }
    int l=1, r=0;
    cnt[mp[0]] = 1;
    ans = 0;
    for(int i=1; i<=q; i++){
        while(l<Q[i].l){
            update(id[0][l-1], id[1][l-1], -1);
            l++;
        }
        //区间从[l, r]变成[l+1, r], cnt统计的区间从[l-1, r]变成[l, r]
        //pre[l-1]删去, 原答案中包含pre[l-1]的都要减去, 也就是要减去满足pre[x] - pre[l-1] = k的x的个数
        //所以向update函数传入pre[x](pre[l-1]+k)和pre[l-1]的离散后的值, 更新答案, 其余三个循环与此类是
        while(l>Q[i].l){
            update(id[0][l-2], id[1][l-2], 1);
            l--;
        }
        while(r<Q[i].r){
            update(id[0][r+1], id[2][r+1], 1);
            r++;
        }
        while(r>Q[i].r){
            update(id[0][r], id[2][r], -1);
            r--;
        }
        Ans[Q[i].id] = ans;
    }
    for(int i=1; i<=q; i++) printf("%lld\n", Ans[i]);
}