ABC398 D~F

D - Bonfire

注意到对于一个第 \(t\) 秒产出的云会进行 \([t+1, N]\) 秒的所有操作，所以我们不妨维护一个操作坐标的前缀和 \(S_t\)。如果第 \(t\) 秒人被云覆盖了的话，那么一定存在第 \(x\) 秒产出的云使得 \(S_t - S_x = (R, C)\)。直接维护一下 \(S_t - (R,C)\) 是否出现过即可。

map<PII, bool> h;
int n, r, c;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

int main() {
    cin >> n >> r >> c;
    if (r == 0 && c == 0) {
        rep(i, 1, n) printf("1");
        return 0;
    }
    int x = 0, y = 0;
    h[{0, 0}] = true;
    rep(i, 1, n) {
        char op; int k;
        scanf(" %c", &op);
        if (op == 'N') k = 0;
        else if (op == 'W') k = 1;
        else if (op == 'S') k = 2;
        else k = 3;
        x = x + dx[k], y = y + dy[k];
        if (h.count({x - r, y - c})) printf("1");
        else printf("0");
        h[{x, y}] = true;
    }
    return 0;
}

F - ABCBA

这 \(F\) 真人机题吧，过的人比 \(E\) 多一万倍。

容易发现我们肯定要保留原字符串的最长回文后缀，然后把剩下的部分倒过来接在后面，比如 EAEEA 就可以变化成 EAEEAE。这样一定是最优的。

设原字符串为 \(S\)，它翻转过来为 \(T\)，我们可以用 T+#+S 这样的方式将其连接起来，然后做一遍 KMP。此时 \(next_{|T|+|S|+1}\) 就是最长回文后缀的长度。

const int N = 2000010;
int n, ne[N];
char s[N], t[N];

int main() {
    scanf("%s", s + 1); n = strlen(s + 1);
    rep(i, 1, n) t[n - i + 1] = s[i];
    t[n + 1] = '#';
    rep(i, n + 2, 2 * n + 1) t[i] = s[i - n - 1];
    n = 2 * n + 1;
    for (int i = 2, j = 0; i <= n; i ++) {
        while (j && t[j + 1] != t[i]) j = ne[j];
        if (t[i] == t[j + 1]) j ++;
        ne[i] = j;
    }
    int ans = ne[n];
    n = (n - 1) / 2;
    rep(i, 1, n) cout << s[i];
    fro(i, n - ans, 1) cout << s[i];
    return 0;
}

E - Tree Game

为什么输出边的时候编号小的要在前啊！

没有奇环可以转化为在加边的过程中保证图是二分图。而最初给出的树一定是二分图，所以我们不妨最这棵树二分图染色，确定出二分图的左部点和右部点，统计一下还可以添加的边数 \(S\)。如果 \(S\) 是奇数就先手，否则后手。然后不断地取还能加的边即可。

\(N \leq 100\)，所以我代码乱搞也能过。

const int N = 200010, M = 1000010;
int n, m;
int h[N], e[M], ne[M], idx;
int c[N];
bool vis[N];
map<PII, bool> H, st;
vector<int> g1, g2;
vector<PII> Edges;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int col) {
    c[u] = col, vis[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) {
            if (!dfs(v, 3 - col)) return false; 
        } else if (c[v] != 3 - col) return false;
    }
    return true;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    rep(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        add(x, y); add(y, x);
        H[{x, y}] = H[{y, x}] = true;   
    }
    rep(i, 1, n)
        if (!vis[i]) dfs(i, 1); 
    rep(i, 1, n) 
        if (c[i] == 1) g1.push_back(i);
        else g2.push_back(i);
    for (auto u : g1) for (auto v : g2)
        if (!H.count({u, v})) {
            Edges.push_back({min(u, v), max(u, v)});
            st[{u, v}] = st[{v, u}] = true;
        }
    if (Edges.size() & 1) cout << "First" << endl;
    else cout << "Second" << endl;
    if (Edges.size() & 1) {
        cout << Edges.back().first << ' ' << Edges.back().second << endl;
        st[Edges.back()] = st[{Edges.back().second, Edges.back().first}] = false;
    }
    int x, y;
    while (cin >> x >> y) {
        if (x == -1 && y == -1) return 0;
        st[{x, y}] = st[{y, x}] = false;
        for (auto &[u, v] : Edges) 
            if (st[{u, v}]) {
                cout << u << ' ' << v << endl;
                st[{u, v}] = st[{v, u}] = false;
                break;
            }
    }
    return 0;
}