Educational Codeforces Round 25 题解

A. Binary Protocol

水题，模拟统计出连续的0隔开的每段1的个数即可。

#include <bits/stdc++.h>
using namespace std;
char s[110];
int n;
int main()
{
    while(~scanf("%d", &n)){
        scanf("%s", s);
        int len = strlen(s);
        int t = 0;
        s[len] = '0';
        for(int i=0; i<=len; i++){
            if(s[i] == '0'){
                printf("%d", t);
                t = 0;
            }
            else{
                t++;
            }
        }
        printf("\n");
    }
}

B. Five-In-a-Row

把每个.位置用’X’替换之后去check即可，注意替换之后要换回来。

#include <bits/stdc++.h>
using namespace std;
char maze[12][12];
bool check(int x, int y){
    maze[x][y]='X';
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            if(maze[i][j]=='O'||maze[i][j]=='.') continue;
            int t1 = 0, t2 = 0, t3 = 0, t4 = 0;
            for(int k=j; k<10; k++){
                if(maze[i][k] == 'X') t1++;
                else break;
            }
            for(int k=i; k<10; k++){
                if(maze[k][j] == 'X') t2++;
                else break;
            }
            for(int k=0; i+k<10&&j+k<10; k++){
                if(maze[i+k][j+k]=='X') t3++;
                else break;
            }
            for(int k=0; i-k>=0&&j+k<10; k++){
                if(maze[i-k][j+k]=='X') t4++;
                else break;
            }
            if(t1>=5||t2>=5||t3>=5||t4>=5){
                maze[x][y] = '.';
                return 1;
            }
        }
    }
    maze[x][y] = '.';
    return 0;
}
int main()
{
    for(int i=0; i<10; i++){
        scanf("%s", maze[i]);
    }
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            if(maze[i][j]=='.'){
                if(check(i,j)){
                    puts("YES");
                    return 0;
                }
            }
        }
    }
    puts("NO");
    return 0;
}

C. Multi-judge Solving

题意：在codeforces上有n个不同难度的题目需要你去解决，现在你在其他OJ上已经解决的最大难度的题目为k，你要解决一个难度为s的问题的前提条件是你当前解决的所有问题的最大难度d要大于等于s，现在cf上这些题目你需要全部去解决，现在问你要通过其他OJ解决几道问题才行

解法：当前的a[i]个问题中，如果这个问题难度a[i]*2小于k，那么k = max(k,a[i])，因为我们可以解决这个问题并且更新k值，否则的话我们就一直递增这个k去找a[i]，这时候ans加加

#include <bits/stdc++.h>
using namespace std;
int n, k, mx, a[1010];

int main()
{
    while(~scanf("%d %d", &n,&k)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        sort(a+1, a+n+1);
        mx = k;
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(mx>=(a[i]+1)/2){
                mx = max(mx, a[i]);
            }
            else{
                while(2*mx < a[i]){
                    ans++;
                    mx*=2;
                }
                mx = max(mx, a[i]);
            }
        }
        printf("%d\n", ans);
    }
}

D. Suitable Replacement

题意：给了一个带有?的原串，又给了一个文本串，问把这些问号怎么替换可以使得文本串在原串的出现次数最多？

解法：贪心，把所有的?存下来，然后一个个的去补全一个完整的文本串肯定是最优的，还要注意处理最后剩下的一段。

#include <bits/stdc++.h>
using namespace std;
char s[1000010], t[1000010];
int cnt[30];
vector <int> v;
int main()
{
    scanf("%s", s);
    scanf("%s", t);
    for(int i=0; s[i]; i++){
        if(s[i] == '?') v.push_back(i);
        else cnt[s[i]-'a']++;
    }
    int l = 0, st = 0, sz = v.size(), len = strlen(t);
    while(1){
        if(!cnt[t[st]-'a']){
            if(l<sz){
                s[v[l]] = t[st];
                l++;
            }
            else{
                break;
            }
        }
        else{
            cnt[t[st]-'a']--;
        }
        st++;
        if(st == len) st = 0;
    }
    for(int i=l; i<sz; i++) s[v[i]] = 'a';
    printf("%s\n", s);
    return 0;
}

E. Minimal Labels

题意：1.对于原来编号u,v的两点，若存在一条从u指向v的边，那么重新编号后，u的编号要小于v的编号。2.重新编号后，新的编号恰好构成一个1~N的排列。从1到N，依次输出该节点的新编号。如果有多种编号方案，输出字典序最小的方案。

解法：1.题目中给出边< x,y >,那么存边时存< y,x >，并记录入度。2.执行Topsort标准操作，压入大根堆中而不是栈中。此时从N到1，依次给取出的堆顶元素进行编号。当然还有一种对应的小根堆的做法，为什么这种做法错了呢？
举个栗子：3 1 3 1 小根堆输出的是3 1 2而正确答案是2 3 1，官方题解也给出了证明。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+7;
int n, m, lable[maxn], du[maxn];
vector <int> G[maxn];
priority_queue <int> q;

int main()
{
    while(~scanf("%d%d", &n,&m)){
        for(int i=1; i<=m; i++){
            int u, v;
            scanf("%d %d", &u,&v);
            G[v].push_back(u);
            du[u]++;
        }
        for(int i=1; i<=n; i++) if(du[i]==0) q.push(i);
        int ans = n;
        while(!q.empty()){
            int x = q.top(); q.pop();
            lable[x] = ans--;
            for(auto i : G[x]){
                du[i]--;
                if(du[i] == 0){
                    q.push(i);
                }
            }
        }
        for(int i=1; i<=n; i++){
            printf("%d ", lable[i]);
        }
        printf("\n");
    }
    return 0;
}

F. String Compression
题意：给了一个字符串，然后我们可以执行折叠操作，比如aaaa可以变成4a，其中前面的数字用10进制表示，然后要问这个字符串可能变成的字符串的最短长度。

解法：KMP+DP。首先要懂一个东西，就是如何利用KMP的nxt数组求出字符串的周期。(周期就是len-nxt[len])，证明在白书上有，非常简单，不再赘述。这里讲讲这道题的做法，DP[i]表示到i字符能够择出的最短长度。那么可以转移到什么地方呢？我们通过枚举的方式，计算枚举的串是否为周期串进行转移即可。看代码吧，写的非常清楚。

复杂度O(n*n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 8005;
int n,fail[maxn][maxn], num[maxn], dp[maxn];
char s[maxn];
void Getmin(int &x, int y){
    if(y<x) x=y;
}
void getFail(){
    for(int st=0; st<n; st++){
        int len=n-st, j=-1;
        fail[st][0]=-1;
        for(int i=1; i<len; i++){
            while(j>=0&&s[st+j+1]!=s[st+i]) j=fail[st][j];
            if(s[st+j+1]==s[st+i]) j++;
            fail[st][i]=j;
        }
    }
}
int main()
{
    scanf("%s", s);
    n = strlen(s);
    for(int i=1; i<=n; i++) num[i]=num[i/10]+1;
    memset(dp, 0x3f, sizeof(dp));
    getFail();
    //dp[0]=0;
    for(int st=0; st<n; st++){
        for(int len=1; st+len<=n; len++){
            Getmin(dp[st+len-1],dp[st-1]+len+1);
            int loop=len-1-fail[st][len-1];
            if(len%loop==0){
                Getmin(dp[st+len-1], dp[st-1]+loop+num[len/loop]);
            }
        }
    }
    printf("%d\n", dp[n-1]);
    return 0;
}

G. Tree Queries

题意：给出一颗树，两种操作一种是把某一个点涂成黑色，另外一个是计算这个点到所有黑点的路径上的最小的点的标号。

解法：参见官方题解。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, q, last, x, minn, f[maxn];
vector <int> G[maxn];
void dfs(int x, int val){
    f[x] = val;
    for(auto v : G[x]){
        if(!f[v]) dfs(v, min(val, v));
    }
}
int main()
{
    while(~scanf("%d %d", &n,&q))
    {
        for(int i=0; i<maxn; i++) G[i].clear();
        for(int i=1; i<n; i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int op;
        scanf("%d %d", &op,&x);
        last = 0;
        x = (x+last)%n+1;
        minn = x;
        dfs(x, x);
        q--;
        while(q--){
            scanf("%d %d", &op,&x);
            x = (x+last)%n+1;
            if(op == 1){
                minn = min(minn, f[x]);
            }
            else{
                last = min(minn, f[x]);
                printf("%d\n", last);
            }
        }
    }
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, q, last, x, minn, f[maxn];
vector <int> G[maxn];
void dfs(int x, int val){
    f[x] = val;
    for(auto v : G[x]){
        if(!f[v]) dfs(v, min(val, v));
    }
}
int main()
{
    while(~scanf("%d %d", &n,&q))
    {
        for(int i=0; i<maxn; i++) G[i].clear();
        for(int i=1; i<n; i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int op;
        scanf("%d %d", &op,&x);
        last = 0;
        x = (x+last)%n+1;
        minn = x;
        dfs(x, x);
        q--;
        while(q--){
            scanf("%d %d", &op,&x);
            x = (x+last)%n+1;
            if(op == 1){
                minn = min(minn, f[x]);
            }
            else{
                last = min(minn, f[x]);
                printf("%d\n", last);
            }
        }
    }
}