AtCoder Beginner Contest 244

A, B, C 比较简单就不写了。

D. Swap Hats

给定两个 "RGB" 这个字符串的排列 \(A,B\) ，每次操作可以交换两个位置。

问能否正好操作 \(10^{18}\) 把 \(A\) 变成 \(B\) 。

假设 R=1,G=2,B=3 ，我们可以通过逆序数奇/偶把所有排列分两类。

因为只有三个位置，可以发现转换关系的连边是个完全二分图。

所以根据 \(A\) 和 \(B\) 不同的位数 \(cnt\) 即可判定是哪种情况。

\(cnt=0\) 完全相同，一直交换某两位即可。
\(cnt=2\) 逆序数相同，但排列不同，不可能通过偶数次交换得到。
\(cnt=3\) 逆序数不同，因为是完全二分图，一定可以通过两次操作把 \(A\) 变成 \(B\) ，后面参考 \(cnt=0\) 操作即可。

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

char a[3], b[3];

inline char gc() {
    char c = getchar();
    while (!isalpha(c)) c = getchar();
    return c;
}

int main() {
    for (int i = 0; i < 3; ++i) a[i] = gc();
    for (int i = 0; i < 3; ++i) b[i] = gc();
    int cnt = 0;
    for (int i = 0; i < 3; ++i) cnt += (a[i] != b[i]);
    puts((cnt == 0 || cnt == 3) ? "Yes" : "No");
    return 0;
}

E. King Bombee

定义无向图 \(G=(V,E)\) 的一个长度为 \(K\) 的路径序列 \(\{A\}\) ：

由 \(K+1\) 个点编号 \(A_0,\dots,A_K\in V\) 构成，\(A_0\) 是起点，\(A_K\) 是终点，且 \(\forall 0\le i < K, (A_i, A_{i+1})\in E\)

给定无向图 \(G\ (|V|\le 2000,|E|\le 2000)\) 求有多少个长度为 \(K\ (K\le 2000)\) 的路径序列，满足：

起点为 \(S\) ，终点为 \(T\) ，且点 \(X\) 在序列中出现偶数次（可以为 \(0\) ) 。

感觉最近 ABC 每场都会有一道比较暴力的 DP，就看敢不敢写（

设 f[i][u][0/1] 表示当前考虑长度为 \(i\) 的路径，起点是 \(S\) ，终点是 \(u\) ，当前节点 \(X\) 在其中出现偶数/奇数次的方案数。

初始状态 f[0][S][S==X] = 1 ，答案 f[K][T][0] 。

转移暴力做就可以了，枚举下一步走哪里（ \(u\to v\) ）：f[i+1][v][k^(v == X)] += f[i][u][k] 。

这个题的核心在复杂度计算，外层枚举 \(i\) 是 \(\mathcal O(n)\) 的，内层枚举 \(u\) 是 \(\mathcal O(n)\) 的，枚举 \(v\) 复杂度怎么算？

把后两个的复杂度放到一起考虑，就是 \(\sum_{u=1}^n deg(u) = \mathcal O(m)\)

所以总复杂度是 \(\mathcal O(nm)\) 的。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 2007
#define mod 998244353
#define add(a, b) (a) = ((a) + (b)) % mod

vector<int> e[N];

int f[N][N][2];

int main() {
    int n = rd(), m = rd();
    int k = rd(), s = rd(), t = rd(), x = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v); e[v].push_back(u);
    }
    f[0][s][x == s] = 1;
    for (int i = 0; i < k; ++i)
        for (int u = 1; u <= n; ++u)
            for (int k = 0; k <= 1; ++k) {
                if (!f[i][u][k]) continue;
                for (auto v : e[u]) {
                    int tar = (k ^ (v == x));
                    add(f[i + 1][v][tar], f[i][u][k]);
                }
            }
    printf("%d\n", f[k][t][0]);
    return 0;
}

F. Shortest Good Path

题意比较复杂，我简单描述一下。

定义无向图 \(G=(V,E)\) 的一个长度为 \(K+1\) 的路径序列 \(\{A\}\) ：

由 \(K+1\) 个点编号 \(A_0,\dots,A_K\in V\) 构成，\(A_0\) 是起点，\(A_K\) 是终点，且 \(\forall 0\le i < K, (A_i, A_{i+1})\in E\)

定义路径序列 \(\{A\}\) 符合要求序列 \(S\ (|S| = n, S_i = 0/1)\) ，当且仅当：

若 \(S_u = 0\) ，则 \(u\) 在 \(\{A\}\) 中出现了偶数次（可以为 \(0\) ）

若 \(S_u = 1\) ，则 \(u\) 在 \(\{A\}\) 中出现了奇数次

那么对于所有的 \(S=0,\cdots,2^n-1\) ，都会存在一个路径序列满足 \(S\) 的要求。

记满足 \(S\) 要求的路径序列最短为 \(f(S)\) ，求 \(\sum_{S=0}^{2^n-1}f(S)\)

看到 ABC 出 \(n\le 17\) 就是状压或者超级暴力了。

考虑路径之间互相更新转移，那么状态之间需要区分的，除了当前每个点出现奇数/偶数次以外，还有最后一个点的编号。

定义符合序列 \(S\) 且最后一个点是 \(u\) 的状态集编号为 sta[S][u] 。

那么对于每一个 \(u\to v\) ，对所有的 \(S\) 连边 sta[S][u] -> sta[S ^ (1 << v)][v]

最后补上初始状态的连边 source -> sta[1 << u][u]

那么跑 BFS 就可以求出来每个状态所需的最小长度了（从 source 出发的距离）

那么 \(f(S) = \min_{u} dis[sta[S][u]]\) 即可，复杂度即状态数乘转移数 \(\mathcal O(n^2\ast 2^n)\)

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 17
#define M 5000007
#define pb push_back

int id[1 << N][N], cnt, dis[M];

vector<int> e[M];

queue<int> q;

int main() {
    int n = rd(), m = rd();
    int S = (1 << n) - 1;
    for (int s = 0; s <= S; ++s) 
        for (int u = 0; u < n; ++u)
            id[s][u] = ++cnt;

    for (int i = 1; i <= m; ++i) {
        int u = rd() - 1, v = rd() - 1;
        for (int s = 0; s <= S; ++s) {
            e[id[s][u]].pb(id[s ^ (1 << v)][v]);
            e[id[s][v]].pb(id[s ^ (1 << u)][u]);
        }
    }
    for (int i = 0; i < n; ++i) e[0].pb(id[1 << i][i]);
  
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : e[u]) 
            if (dis[v] > dis[u] + 1) {dis[v] = dis[u] + 1; q.push(v);}
    }
    ll ans = 0;
    for (int s = 1, tmp; s <= S; ++s) {
        tmp = 1e9;
        for (int u = 0; u < n; ++u) {
            tmp = min(tmp, dis[id[s][u]]);
        }
        ans += tmp;
    }
    printf("%lld\n", ans);
    return 0;
}

G. Construct Good Path

定义无向图 \(G=(V,E)\) 的一个长度为 \(K+1\) 的路径序列 \(\{A\}\) ：

由 \(K+1\) 个点编号 \(A_0,\dots,A_K\in V\) 构成，\(A_0\) 是起点，\(A_K\) 是终点，且 \(\forall 0\le i < K, (A_i, A_{i+1})\in E\)

定义路径序列 \(\{A\}\) 符合要求序列 \(S\ (|S| = n, S_i = 0/1)\) ，当且仅当：

若 \(S_u = 0\) ，则 \(u\) 在 \(\{A\}\) 中出现了偶数次（可以为 \(0\) ）

若 \(S_u = 1\) ，则 \(u\) 在 \(\{A\}\) 中出现了奇数次

给定连通无向图 \(G\) 和要求序列 \(S\) ，构造一个长度不超过 \(4\ast |V|\) 的序列符合 \(S\)

图只有连通的性质，那么可以考虑树怎么解决，其他情况找一棵生成树就可以了。

设 \(A_u\) 为 \(u\) 子树的合法序列：满足 \(u\) 子树内，除了 \(u\) 以外其他点都符合要求的一个序列。

强制叶子 \(v\) 对应的 \(A_v=(v)\) 。
其他情况如果令 \(A_u=(u)+A_{son1}+(u)+A_{son2}+\cdots+(u)\) ，那么只有 \(son\) 这些节点会不合法。

那么对于每个导致不合法的 \(son\) ，给序列最后接上一个 \((son,u)\) 就可以保证 \(son\) 合法。

用数学归纳法做正确性证明：\(|A_u|\le 4 \astsize_u-3\) ，其中 \(size_u\) 为\(u\) 子树大小。

对于叶子，\(|A_u|=1=4\ast1-3\)
假设对于一个点 \(u\)，所有儿子节点 \(son\)都符合，那么这个点的序列：
必须添加 \(cntson + 1\) 个 \((u)\) ，还有所有的 \(A_{son}\)，其余的每个补充会增加两个点。
\[\begin{array}{ll}|A_u| & \le \sum_{son} A_{son} + cntson + 1 + 2 \ast cntson\\\\\ & \le \sum_{son} (4 \ast size_{son} - 3) + 3\ast cntson +1\\\\\ & = 4 \ast \sum_{son} size_{son} - 3\ast cntson + 3\ast cntson+ 1\\\\\ & = 4 \ast (size_u - 1) + 1\\\\\ & = 4 \ast size_u - 3\end{array}\]

这样就证明了，最后根的序列大小不超过 \(4N - 3\) 。

最后序列中如果根节点奇偶性不对，那么随便找一个根节点的儿子 \(son\) ，补一个 \((son,u,son)\) 即可修正。

这样子序列长度的上限刚好是 \(4N\) ，复杂度 \(\mathcal{O}(n)\)。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool gn() {
    char c = getchar();
    for (; !isdigit(c); c = getchar());
    return c - '0';
}

#define N 100007
#define pb push_back

vector<int> e[N], res;

bool vis[N], s[N];

void add(int x) {
    s[x] ^= 1; res.pb(x);
}

void dfs(int u) {
    vis[u] = 1; add(u);
    for (auto v : e[u])
        if (!vis[v]) { //当前点没在树里出现过
            dfs(v); add(u);
            if (s[v]) {add(v); add(u);}
        }
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
    }
    for (int i = 1; i <= n; ++i) s[i] = gn();
  
    dfs(1);
    if (s[1]) {
        int son = e[1][0];
        add(son); add(1); add(son);
    }
    printf("%d\n", (int)res.size());
    for (auto x : res) printf("%d ", x);

    return 0;
}

Ex. Linear Maximization

维护一个二维向量集，支持：

插入一个二维向量 \((x, y)\)

查询集合中和给定向量 \((u, v)\) 点积的最大值

[SDOI2014]向量集弱化版，线段树维护凸包即可。

AtCoder AtCoder Beginner Contest

Constructive Algorithm Dynamic Programming Bitmask

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

AtCoder Grand Contest 001 Previous

Codeforces Round #777 (Div. 2) Next