Education CodeForces Round 25 题解

Education CodeForces Round 25 题解

Contest 825 Dashboard

A. Binary Protocol

题意

给出一个01串，这个串由十进制串encode得到，方法是每一位数字映射成为相同数量的1，数字之间用0隔开。

思路

水。

代码

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

int main(){
    int n, cur = 0, cnt = 0;
    char s[100], ans[100];
    scanf("%d%s", &n, s);
    for (int i = 0; i < n; ++i)
        s[i]-'0'? ++cnt : (ans[cur++] = cnt + '0', cnt = 0);
    ans[cur++] = cnt + '0';
    ans[cur] = '\0';
    puts(ans);
    return 0;
}

B. Five-In-a-Row

题意

给出一个五子棋盘，判断其中'X'是否是必胜态。

思路

模拟。

代码

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

char maps[15][15];
int dir[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
bool flag = 0;

void judge(int x, int y) {
    maps[x][y] = 'X';
    for (int i = 0, cnt = 0; i < 10; ++i) {
        maps[x][i] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, cnt = 0; i < 10; ++i) {
        maps[i][y] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j){
        int u = i, v = y - x + j;
        if (y < 0 || y > 9) continue;
        maps[u][v] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j) {
        int u = i, v = y + x - j;
        if (y > 9 || y < 0) continue;
        maps[u][v] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    maps[x][y] = '.';
}

void check(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int u = x + dir[i][0], v = y + dir[i][1];
        if (u < 0 || v < 0 || u > 9 || v > 9) continue;
        if (maps[u][v] == '.') judge(u, v);
        if (flag) return;
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    for (int i = 0; i < 10; ++i) scanf("%s", maps[i]);
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j) {
            if (maps[i][j] == 'X') check(i, j);
            if (flag) goto a; // 闲的蛋疼
        }
a:
    puts(flag ? "YES" : "NO");
    return 0;
}

C. Multi-judge Solving

题意

如果Makes做过难度为i的题目，他就可以做出i*2的题目。
一开始Makes做过的最高难度题是k，他要刷完他列表中所有的题，问中间需要多少道题作为跳板。

思路

贪心。把k放进数组中，然后排个序，upper_bound得到比k之后的一道题，判断是否能做出它，如果可以的话就继续upper_bound，否则判断一下需要多少道题作为跳板。

代码

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

int main(){
    int n, k, num[1007], ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) 
        scanf("%d", num+i);
    num[0] = k;
    sort(num, num+n+1);
    for (int now = k, nxt = upper_bound(num, num+n+1, now<<1) - num, cur = 1; nxt <= n; nxt = upper_bound(num, num+n+1, now<<1) - num) {
        now = num[nxt-1], cur = nxt-1;
        nxt = upper_bound(num, num+n+1, now<<1) - num;
        while (nxt == cur+1 && nxt != n+1) {
            ++ans, now <<= 1;
            nxt = upper_bound(num, num+n+1, now<<1) - num;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D. Suitable Replacement

题意

给出一个主串s和一个模式串t，主串中有若干'?'，需要把这些'?'填补起来。填补之后的字符串要求任意顺序中可以找到最多的模式串t。

思路

本来想的是模拟+贪心，但是想想代码量会很大。

看了dalao的代码之后换一种思路：首先统计主串中有除了'?'之外的字符数量。然后遍历主串，每遇到一个'?'就找当前'?'数量相对应的t串的位置，如果这个位置是字符是主串中含有的，就将主串这个字符的数量--，并且重新遍历这个'?'，直到遍历到一个主串中已经不含有的字符，就将t串这个字符填进去。

代码

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

const int maxn = 1e6+7;

int main(){
    int hash[26] = {}, cur = 0, len_t;
    char s[maxn], t[maxn];
    scanf("%s%s", s, t);
    len_t = strlen(t);
    for (int i = 0; s[i]; ++i) ++hash[s[i]-'a'];
    for (int i = 0; s[i]; ++i) if (s[i] == '?') {
        ++cur, cur %= len_t;
        hash[t[cur]-'a'] > 0 ? (--hash[t[cur]-'a'], --i) : s[i] = t[cur];
    }
    puts(s);
    return 0;
}

E. Minimal Labels

题意

给出一张有向无环图，按照这张图的拓扑序给这张图的每一个节点标号，要求标号的排列是可能排列中字典序最小的。

思路

一开始想的是正常跑拓扑序，然后用优先队列来给最小的标号，但奚政巨hack了这种方法。主要问题还在于题意没有读清楚。我以为是标号对于的点的编号排列字典序最小。

既然正着不行，就反着来。反向建图，依然是优先队列，只是在拓扑序的过程中给最大的点标上最大的号。这样贪心就可以得到最佳匹配。

代码

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

const int maxn = 1e5+7;

struct Edge {
    int to, nxt, dis;
}edge[maxn];

int head[maxn], tot;
int degree[maxn] = {}, v[maxn], n;

priority_queue<int> q;

void init() {
    tot = 0;
    memset(head, -1, sizeof head);
    memset(degree, 0, sizeof degree);
}

void addnode(int u, int v) {
    ++degree[v];
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}

void topo_sort(int n) {
    int cur = n;
    for (int i = 1; i <= n; ++i)
        if (!degree[i]) q.push(i);
    while (!q.empty()) {
        int u = q.top(); q.pop();
        v[u] = cur--;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].to;
            --degree[v];
            if (!degree[v]) q.push(v);
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    init();
    int m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) v[i] = i;
    for (int i = 0, u, v; i < m; ++i) {
        scanf("%d%d", &v, &u);
        addnode(u, v);
    }
    topo_sort(n);
    for (int i = 1; i < n; ++i)
        printf("%d ", v[i]);
    printf("%d\n", v[n]);
    return 0;
}