Codeforces Round 606 (Div. 2, based on Technocup 2020 Elimination Round 4)

15 December 2019 | duanyll | Tags: OI

感觉这场 Div.2 有点水啊, 为什么我这个 AFO 的选手都能过 5 道题…

A. Happy Birthday, Polycarp!

签到题, 不多说.

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        int n = read();
        int t = n;
        int dig = 0;
        while (t > 0) {
            dig++;
            t /= 10;
        }
        int ans = 9 * (dig - 1);
        int64 x = 0;
        for (int i = 1; i <= dig; i++) {
            x *= 10;
            x += 1;
        }
        for (int i = 1; i <= 9; i++) {
            if (x * i <= n) ans++;
        }
        cout << ans << endl;
    }
}

B. Make Them Odd

每次贪心处理当前最大的偶数, 优先队列模拟即可.

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        int n = read();
        priority_queue<int> q;
        for (int i = 1; i <= n; i++) {
            int x = read();
            if (!(x & 1)) q.push(x);
        }
        int ans = 0;
        int c = 0;
        while (!q.empty()) {
            int u = q.top();
            q.pop();
            if (u != c) {
                c = u;
                ans++;
            }
            if ((u >> 1) & 1) continue;
            q.push(u >> 1);
        }
        write(ans);
        putchar('\n');
    }
}

C. As Simple as One and Two

不难发现, 对于 one, 删掉 n 总是可行的; 对于 two, 删掉 w 总是可行的; 但是对于 twone 的情况, 最优解是删掉 o

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; i++) {
            vis[i] = false;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            if (s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o' &&
                s[i + 3] == 'n' && s[i + 4] == 'e') {
                vis[i + 2] = true;
                ans++;
            } else if (s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o') {
                vis[i + 1] = true;
                ans++;
            } else if (s[i] == 'o' && s[i + 1] == 'n' && s[i + 2] == 'e') {
                vis[i + 1] = true;
                ans++;
            }
        }
        write(ans);
        putchar('\n');
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                write(i);
                putchar(' ');
            }
        }
        putchar('\n');
    }
}

D. Let’s Play the Words?

00 和 11 的不用反转, 只用反转 01 或 10 使得两者数量只差 1 个就总是可行的; 对于能不能翻转直接用 unordered_set 维护. 注意同时包含 00 和 11 并且没有 01 或 10 是无解的, 特判输出(在这里挂了一次).

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        vector<pair<int, string>> s01, s10;
        int c00 = 0, c11 = 0;
        int n = read();
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            if (s.front() == '0') {
                if (s.back() == '0')
                    c00++;
                else
                    s01.push_back(make_pair(i, s));
            } else {
                if (s.back() == '0')
                    s10.push_back(make_pair(i, s));
                else
                    c11++;
            }
        }
        if (c00 > 0 && c11 > 0 && s01.size() + s10.size() == 0) {
            puts("-1");
            continue;
        }
        int d = abs((int)s01.size() - (int)s10.size()) / 2;
        if (s01.size() > s10.size()) swap(s01, s10);
        unordered_set<string> s;
        vector<int> ans;
        for (auto i : s01) {
            s.insert(i.second);
        }
        for (auto i : s10) {
            if (ans.size() >= d) break;
            string rev(i.second.rbegin(), i.second.rend());
            if (s.count(rev) == 0) {
                ans.push_back(i.first);
                s.insert(rev);
            } 
        }
        if (ans.size() < d) {
            puts("-1");
        } else {
            write(ans.size());
            putchar('\n');
            for (auto i : ans) {
                write(i);
                putchar(' ');
            }
            putchar('\n');
        }
    }
}

E. Two Fairs

从两个点分别做一次 DFS 就可以了, 满足要求的点对一定有一个只有 A 能 DFS 到, 另一个只有 B 能 DFS 到, 详情见代码.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;

const int MAXN = 200010;
const int INF = 0x3f3f3f3f;

class lfs {
   public:
    lfs(int N) {
        n = N;
        head = new int[n + 2];
        memset(head, -1, (sizeof n) * (n + 2));
        ecnt = 0;
    }
    void adde(int from, int to, int w) {
        edge cur;
        cur.to = to;
        cur.w = w;
        cur.next = head[from];
        head[from] = ecnt++;
        e.push_back(cur);
    }
    void addde(int a, int b, int w) {
        adde(a, b, w);
        adde(b, a, w);
    }

    int64 solve(int a, int b) {
        vis1 = new bool[n + 2];
        memset(vis1, false, (sizeof false) * (n + 2));
        vis2 = new bool[n + 2];
        memset(vis2, false, (sizeof false) * (n + 2));
        this->a = a;
        this->b = b;
        dfs(a, 0, vis1);
        dfs(b, 0, vis2);
        int64 cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= n; i++) {
            if (vis1[i] && !vis2[i]) cnt1++;
            else if (!vis1[i] && vis2[i]) cnt2++; 
        }
        return (cnt1 - 1) * (cnt2 - 1);
    }

    ~lfs() {
        delete[] head;
        delete[] vis1;
        delete[] vis2;
    }

   protected:
    struct edge {
        int to, next, w;
    };
    vector<edge> e;
    int* head;
    int ecnt;
    int n;
    int a, b;
    bool* vis1;
    bool* vis2;
    void dfs(int u, int fa, bool* vis) {
        vis[u] = true;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (v != fa && v != a && v != b) {
                if (!vis[v]) dfs(v, u, vis);
            }
        }
    }
};

可惜 15 号白天的两场 Div.2 都没时间打了, 不过下个星期六还有一次国人场.