Educational Codeforces Round 25

这一场是暑期的第一场，做了4个题，被HACK两个，都是很粗心的错误，手生的问题。

【A】Binary Protocol

题意：给你一串字符串，只有0和1。用m个0将字符串分为m+1段，每段字符串中‘1’的个数代表一个数。

做法：在末尾补0.然后扫一遍。遇到1累加，遇到0输出累加值。

注意:

1001有两个连续的0，两个0之间有0个1，所以输出0，结果101.

1110末尾为0，0的后面有0个1，所以也要输出0，结果30.

代码:

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    int len;
    while(cin >> len >> s) {
        s = s + '0';
        int tp = 0;
        for(int i = 0; i < len+1; i++) {
            if(s[i] == '1') tp++;
            else {
                cout << tp;
                tp = 0;
            }
        }
        cout << endl;
    }
}

【B】Five-In-a-Row

题意: 五子棋，下一步是X，问能否胜利。

做法：完全暴力，枚举X的位置，然后check一下能否构成5个子。

PS：傻逼的忘了判断正斜线，被HACK了，五子棋白下了。

#include <bits/stdc++.h>
using namespace std;
char mp[20][20];
 
bool check(int x, int y){
     
    //列
    int tp = 1;
    for(int i = x + 1; i < 10; i++) {
        if(mp[i][y] == 'X') tp++;
        else break;
    }
    for(int i = x - 1; i >= 0; i--) {
        if(mp[i][y] == 'X') tp++;
        else break;
    }
    if(tp >= 5) return true;
     
    //行
    tp = 1;
    for(int j = y + 1; j < 10; j++) {
        if(mp[x][j] == 'X') tp++;
        else break;
    }
    for(int j = y - 1; j >= 0; j--) {
        if(mp[x][j] == 'X') tp++;
        else break;
    }
    if(tp >= 5) return true;
     
    //负斜线
    int a = x, b = y;
    tp = 1;
    while(x >=0 && y >= 0) {
        x--; y--;
        if(x >=0 && y >= 0 && mp[x][y] == 'X') tp++;
        else break;
    }
    x = a, y = b;
    while(x < 10 && y < 10) {
        x++; y++;
        if(x < 10 && y < 10 && mp[x][y] == 'X') tp++;
        else break;
    }
    if(tp >= 5) return true;
     
    //正斜线
    x = a, y = b;
    tp = 1;
    while(x >= 0 && y >= 0 && x < 10 && y < 10) {
        x--;
        y++;
        if(x >= 0 && y >= 0 && x < 10 && y < 10 && mp[x][y] == 'X') tp++;
        else break;
    }
    x = a, y = b;
    while(x >= 0 && y >= 0 && x < 10 && y < 10) {
        x++;
        y--;
        if(x >= 0 && y >= 0 && x < 10 && y < 10 && mp[x][y] == 'X') tp++;
        else break;
    }
    if(tp >= 5) return true;
 
    return false;
}
int main() {
    for(int i = 0; i < 10; i++) {
        scanf("%s", &mp[i]);
    }
//    枚举X的位置
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            if(mp[i][j] == '.') {
                mp[i][j] = 'X';
                if( check(i, j) ) {
                    puts("YES");
                    return 0;
                }
                mp[i][j] = '.';
            }
        }
    }
    puts("NO");
}

【C】Multi-judge Solving

题意：做题。每个题有难度等级。给定Makes目前做过最难题的等级D，只要题的难度A <= 2D，那么Makes就可以做。不然Makes就要从别的OJ做任意可做难度的题。问至少需要在别的OJ做多少题。

做法：贪心。按题目难度从小到大排序。如果当前题可以做，那么就更新D；不能做就去别的OJ做一道能做的最难的题，也就是2D的难度，更新D = 2D。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
int main() {
    int n;
    LL k;
    LL a[1010];
    scanf("%d%I64d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%I64d", &a[i]);
    sort(a, a + n);
    LL ans = 0;
    for(int i = 0; i < n; i++) {
        LL tp = a[i] + 1 >> 1;
        if(k >= tp) {
            k = max(k, a[i]);
        } else {
            while(k < tp) {
                k = 2 * k;
                ans ++;
            }
            k = max(k, a[i]);
        }
    }
    cout << ans << endl;
}

【D】 Suitable Replacement

题意：给定2个字符串。A字符串的?可以是任意小写字母。让你补齐?，任意调整顺序，使得A字符串包含最多个B字符串。

做法：模拟构造。先计算第B字符串对每个字母的消耗量，例如aabbc，则consum['a'] = 2, consum['b'] = 2, consum['c'] = 1。

　　累计A字符串各个字符的个数。计算A字符串可以减去多少 “波“B字符串，不够用‘？‘来代替，直至’？‘不够用。输出构造结果，剩余的’？‘随便用一个字母补齐。

代码:

#include <bits/stdc++.h>
using namespace std;
int node[200]; //A字符串中各个字符的个数
int main() {
    string s, t;
    memset(node, 0, sizeof(node));
    cin >> s >> t;
    //判断是否存在?
    bool f = true;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '?') f = false;
    }
    if(f) {
        cout << s << endl;
        return 0;
    }
     
    map<char, int>mp; //B字符串各个字符的个数
    vector<char>vec; //存B字符串的N个字符
    for(int i = 0; i < t.size(); i++) {
        mp[t[i]]++;
        if(mp[t[i]] == 1) vec.push_back(t[i]);
    }
    int len = 0; //问号个数
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '?') len++;
        else if(mp[s[i]]) {
            node[s[i]]++;
        }
    }
    vector<char>ans;
    while(len > 0) {
        for(int i = 0; i < vec.size(); i++) {
            node[vec[i]] -= mp[vec[i]];
            if(node[vec[i]] < 0) {
                len += node[vec[i]];
                if(len < 0) break;
                int n = -node[vec[i]];
                while(n--) ans.push_back(vec[i]);
                node[vec[i]] = 0;
            }
        }
    }
 
    int idx = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '?') {
            if(idx < ans.size()) {
                s[i] = ans[idx];
                idx++;
            } else {
                s[i] = 'a';
            }
        }
    }
    cout << s << endl;
}

【E】Minimal Labels

题意：给定你一个不一定联通的无环有向图，让你构造一个序列ans[]。定义：u -> v，那么 ans[u] < ans[v]。并且要求构造出来的序列的字典序最小。

做法：因为无环，所以一定存在出度为0的点，且出度为0的点构造的值一定是最大的，不难看出，如果是连通图，那么结果是一定的。如果是非连通图，那就存在优先问题，为了让字典序最小，我们肯定是先给点小的点赋大值。

因此，用set来存出度为0的点，每次弹出一个最小的点，赋最大值，删除指向它的边，同时更新出度为0的点。

代码:

#include <bits/stdc++.h>
using namespace std;
vector<int>in[100010];
vector<int>out[100010];
int main () {
    int n, m, v, u;
    scanf("%d%d", &n, &m);
    set<int, greater<int> >st; //从小到大弹出
    for(int i = 1; i <= n; i++) st.insert(i);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &v, &u);
        in[u].push_back(v);
        out[v].push_back(u);
        st.erase(v);
    }
    int ans[100010];
    int idx = n;
    while(!st.empty()) {
        int cur = *st.begin();
        st.erase(st.begin());
        ans[cur] = idx--; //赋最大值
        //删除指向它的边，同时更新出度为0的点
        for(int i = 0; i < in[cur].size(); i++) {
            int x = in[cur][i];
            out[x].erase(find(out[x].begin(), out[x].end(), cur));
            if(out[x].empty()) st.insert(x);
        }
    }
    bool f = false;
    for(int i = 1; i <= n; i++) {
        if(f) putchar(' '); f = true;
        printf("%d", ans[i]);
    }
    puts("");
}