HKU Provincists 2nd Training

Posted on 繁/简： set

题目来自 杭电 2023 "钉耙编程" 中国大学生算法设计超级联赛。link

好难！做得满头大汗了。


  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!


Hide-And-Seek Game

好题。用到了 LCA + exGCD 求二元一次同余方程的最小正整数解。

首先找到两条链 \(L_a,L_b\) 的相交链。

令 \(f(x,y)\) 为 \(x,y\) 之间的距离：如果某点 \(x\) 满足 \(f(S_a,x)+f(x,T_a)=f(S_a,T_a)\)，那么我们能够断定 \(x\) 在链 \(L_a\) 上。如果某点 \(x\) 既在链 \(L_a\) 上又在链 \(L_b\) 上，那么它一定位于 \(L_a,L_b\) 的相交链上。快速询问树上两点间的距离用 LCA 解决。

由于 \(n\) 比较小，我们暴力枚举所有相交链上的点 \(x\)。\(A\) 到达 \(x\) 的时间为：

  • (往 \(T_a\) 方向) \(2k_1\cdot f(S_a,T_a)+f(S_a,x)\)
  • (往 \(S_a\) 方向) \((2k_1+1)\cdot f(S_a,T_a)+f(x,T_a)\)

类似的，\(B\) 到达 \(x\) 的时间也有两个表达式：

  • (往 \(T_b\) 方向) \(2k_2\cdot f(S_b,T_b)+f(S_b,x)\)
  • (往 \(S_b\) 方向) \((2k_2+1)\cdot f(S_b,T_b)+f(x,T_b)\)

总共可以列出 \(2\times 2=4\) 个二元一次同余方程，用 exGCD 求出最小正整数解即可。(四个最小正整数解中取令时间表达式最小的解为答案)

注意系数 \(a,b\) 或常数 \(c\) 为负数的情况：我们只关注 \(x\) 的最小正整数解，因此我可以强行将 \(b\) 视为正数 (对应的 \(y\) 取反即可) 并通过向等式两边 \(+b\) (对应的 \(y\) 减去若干数即可) 的方式消除负数。

这里顺便复习一下 exGCD 求最小正整数解。给出方程 \(ax+by= c\)：

  • 使用 exGCD 分别求出 \(d=\gcd(a,b)\) 与 \(ax+by=d\) 的一组特解 \(x',y'\)。
  • 若 \(d|c\)，原方程有解。
  • 对应原方程的一组特解为 \(\frac{c}{d}x', \frac{c}{d}y'\)。
  • \(x\) 的通解周期为 \(T_1=\frac{b}{d}\)，\(y\) 的通解周期为 \(T_2=\frac{a}{d}\)；\(x\) 每增加一个 \(T_1\)，\(y\) 就减少一个 \(T_2\)。
  • 因此 \(x\) 的最小正整数解 \(x_1=(\frac{c}{d}x' \mod{T_1}+T_1)\mod{T_1}\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 3e3 + 10;
const long long inf = 1e18;

int fa[MAX_N][15];
int dep[MAX_N];

int n, m;
int sa, ta, sb, tb;
int ans;

long long minTime;

vector<int> e[MAX_N];

void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;

    for (int i = 1; i < 13; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int to : e[u]) {
        if (to == f)    continue;
        dfs(to, u);    
    }
}

int LCA(int x, int y) {
    if (dep[x] < dep[y])    swap(x, y);

    int gap = dep[x] - dep[y];
    for (int i = 0; i < 13; ++i) {
        if (!gap)   break;
        if (gap & 1)    x = fa[x][i];
        gap >>= 1;
    }
    if (x == y) return x;
    for (int i = 12; i >= 0; --i) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}

bool onPath(int x, int u, int v) {
    return dis(x, u) + dis(x, v) == dis(u, v);
}

int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y, y = tmp - a / b * y;
    return d;
}

long long work(int a, int b, int p, int q) {
    int c = q - p;
    c = (c % b + b) % b;
    int x, y;
    int d = exgcd(a, b, x, y);
    if (c % d)  return inf;
    int t1 = b / d;
    long long minPosSol = ((x * c / d) % t1 + t1) % t1;
    return minPosSol * a + p;
}

void calcOnPoint(int i) {
    if (onPath(i, sa, ta) && onPath(i, sb, tb)) {
        int a = 2 * dis(sa, ta), b = 2 * dis(sb, tb);
        int p1 = dis(sa, i);
        int p2 = dis(sa, ta) + dis(i, ta);
        int q1 = dis(sb, i);
        int q2 = dis(sb, tb) + dis(i, tb);
                
        long long sol1 = work(a, b, p1, q1);
        long long sol2 = work(a, b, p1, q2);
        long long sol3 = work(a, b, p2, q1);
        long long sol4 = work(a, b, p2, q2);
        long long minSol = min(min(sol1, sol2), min(sol3, sol4));

        if (minSol < minTime) {
            minTime = minSol;
            ans = i;
        }
    }
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        e[i].clear();
        dep[i] = 0;
        for (int j = 0; j < 13; ++j)    fa[i][j] = 0;
    }

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs(1, 0);

    while (m--) {
        cin >> sa >> ta >> sb >> tb;

        ans = -1;
        minTime = inf;

        int LCAa = LCA(sa, ta), i = sa;
        while (i != LCAa) {
            calcOnPoint(i);
            i = fa[i][0];
        }
        i = ta;
        while (i != LCAa) {
            calcOnPoint(i);
            i = fa[i][0];
        }
        calcOnPoint(LCAa);

        cout << ans << endl;
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;

    while (tt--) {
        solve();
    }

    return 0;
}


City Upgrading

图 \(G\) 的支配集 (dominating set) \(S\subseteq V\)，满足对于任意顶点 \(v\in V\)，要么 \(v\in S\)，要么 \(v\) 与 \(S\) 中至少一个顶点相邻。若 \(S\) 的任何子集都不是支配集，我们称 \(S\) 是 \(G\) 的最小支配集 (minimal dominating set)。

求树的最小权支配集模板；使用树形 DP 解决。令

  • \(f_{u,0}\) 表示 \(u\) 被其子节点支配时，\(u\) 子树的答案。
  • \(f_{u,1}\) 表示选择 \(u\) 时，\(u\) 子树的答案。
  • \(f_{u,2}\) 表示 \(u\) 被其父节点支配时，\(u\) 子树的答案。

转移如下 (\(v\) 是 \(u\) 的子节点)：

  • \(f_{u,0}=\sum_{v} \min(f_{v,0}, f_{v,1}) + \mathrm{cost}\).
    • \({\mathrm{cost}}=\min \{f_{v,1}-\min(f_{v,0}, f_{v,1})\}\) 选择某个子节点所需要付出的最小补偿代价。
  • \(f_{u,1}=\sum_v \min\{f_{v,0}, f_{v,1}, f_{v,2}\}\).
  • \(f_{u,2}=\sum_v \min(f_{v,0}, f_{v,1})\).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 10;
const int inf = INT_MAX;

int val[MAX_N];
long long f[MAX_N][3];

vector<int> g[MAX_N];

void dfs(int u, int fa) {
    bool leaf = true;
    
    for (int v : g[u]) {
        if (v == fa)	continue;
        leaf = false;
        dfs(v, u);
    }

    if (leaf) {
        f[u][0] = inf;
        f[u][1] = val[u];
        f[u][2] = 0;
        return;
    }

    long long sum_0 = 0, sum_1 = 0, sum_2 = 0;
    long long cost = inf;

    for (int v : g[u]) {
        if (v == fa)	continue;
        sum_0 += min(f[v][0], f[v][1]);
        sum_1 += min(f[v][0], min(f[v][1], f[v][2]));
        sum_2 += min(f[v][0], f[v][1]);
        cost = min(cost, f[v][1] - min(f[v][0], f[v][1]));
    }

    f[u][0] = sum_0 + cost;
    f[u][1] = sum_1 + val[u];
    f[u][2] = sum_2;
}

long long solve(int n) {
    
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
        f[i][0] = f[i][1] = f[i][2] = 0;
        g[i].clear();
    }

    int x, y;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 0);

    return min(f[1][0], f[1][1]);
}

int main() {


    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;

    while (tt--) {
        int n;
        cin >> n;
        cout << solve(n) << endl;
    }

    return 0;
}


Mr.Liang play Card Game

比较明显的区间 DP。问题在于如果 \(O(nmr)\) 转移的话感觉一定会超时。然而赛后看题解发现标答的单组时间复杂度正是 \(O(n^3 mr)\) 的……人还是要有梦想。

考虑区间 \([l,r]\)，无论以什么方式进行消除，最后总会留下一张卡片并在之后被打出。我们把每个区间消去到最后剩余的卡片作为 anchor 进行 DP 状态的设计。令：

  • \(f_{l,r,t,k}\) 为区间 \([l,r]\) 消去到只剩一张 type 为 \(t\)，level 为 \(k\) 的卡片时获得的最大价值。
  • \(g_{l,r}\) 为全部消去区间 \([l,r]\) 后获得的最大价值。

很明显有以下关系：\(g_{l,r}=\max_{t,k}\{f_{l,r,t,k}+p^{k-1}\cdot v_t\}\).

接下来设计状态的转移：考虑区间 \([l,r]\)，枚举断点 \(i \ (l\leq i\leq r)\).

  • 不考虑合并卡片：\(f_{l,r,t,k}=\max_i\{(g_{l,i}+f_{i+1,r,t,k}), (f_{l,i,t,k}+g_{i+1,r})\}\).
  • 考虑合并卡片 \((k\geq 2)\)： \(f_{l,r,t,k}=\max_{i}\{f_{l,i,t,k-1}+f_{i+1,r,t,k-1}\}\).

全部消去 \([l,r]\) 后获得的最大价值 \(g_{l,r}\) 同步进行转移：

  • \(g_{l,r}=\max_i\{g_{l,i} + g_{i+1,r}\}\).
  • \(g_{l,r}=\max_{t,k}\{f_{l,r,t,k}+p^{k-1}\cdot v_t\}\).

最后答案即为 \(g_{1,n}\)。注意应用一个小优化 \(r=\min(r, \log n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 110;

int n, m, R, P;

int type[MAX_N];
long long v[MAX_N], ppow[MAX_N];

long long f[MAX_N][MAX_N][25][25];
long long g[MAX_N][MAX_N];

long long dfs(int l, int r) {
    if (g[l][r])
        return g[l][r];
    
    if (l == r) {
        g[l][r] = v[type[l]];
        f[l][r][type[l]][1] = 0;
        return g[l][r];
    }

    long long res = 0;

    for (int i = l; i < r; ++i)
        res = max(res, dfs(l, i) + dfs(i + 1, r));

    for (int i = l; i < r; ++i) {
        for (int t = 1; t <= m; ++t) {
            for (int k = 1; k <= R; ++k) {
                if (f[l][i][t][k] >= 0)
                    f[l][r][t][k] = max(f[l][r][t][k], f[l][i][t][k] + dfs(i + 1, r));
                if (f[i + 1][r][t][k] >= 0)
                    f[l][r][t][k] = max(f[l][r][t][k], dfs(l, i) + f[i + 1][r][t][k]);
                if (k >= 2) {
                    if (f[l][i][t][k - 1] >= 0 && f[i + 1][r][t][k - 1] >= 0)
                        f[l][r][t][k] = max(f[l][r][t][k], 
                                            f[l][i][t][k - 1] + f[i + 1][r][t][k - 1]);
                }
            }
        }
    }

    for (int t = 1; t <= m; ++t) {
        for (int k = 1; k <= R; ++k) {
            if (f[l][r][t][k] >= 0)
                res = max(res, f[l][r][t][k] + ppow[k - 1] * v[t]);
        }
    }

    return g[l][r] = res;
}


long long solve() {

    memset(f, -1, sizeof f);
    memset(g, 0, sizeof g);

    cin >> n >> m >> R >> P;
    R = min(R, (int) log2(n) + 1);

    for (int i = 1; i <= n; ++i)    cin >> type[i];
    for (int i = 1; i <= m; ++i)    cin >> v[i];

    ppow[0] = 1;
    for (int i = 1; i <= R; ++i)
        ppow[i] = 1LL * ppow[i - 1] * P;
    
    return dfs(1, n);
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--) {
        cout << solve() << endl;
    }

    return 0;
}


Cyclically Isomorphic

循环同构串题目加多个字符串匹配，首先想到 AC 自动机做法：动态的插入字符串，若查询失败则将其的两倍插入 AC 自动机中。然后发现自己已经忘记 AC 自动机怎么写了。

后来想到一个很简单的方法：用字符串的最小表示法 + 哈希来划分循环同构串群即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 10;

int n, m;
int id[MAX_N];

map<string, int> Hash; 

string getCore(string str) {
    int i = 0, j = 1, k = 0;
    while (k < m && i < m && j < m) {
        char fir = str[(i + k) % m], sec = str[(j + k) % m];
        if (fir == sec) 
            ++k;
        else {
            (fir > sec) ? (i += (k + 1)) : (j += (k + 1));
            k = 0;
            if (i == j) ++j;
        }
    }
    i = min(i, j);
    string res = "";
    for (int k = 0; k < m; ++k) res += str[(i + k) % m];
    return res;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;

    while (tt--) {
        cin >> n >> m;

        int cnt = 0;
        string str;
        for (int i = 1; i <= n; ++i) {
            cin >> str;
            string core = getCore(str);        
            if (!Hash.count(core))
                Hash[core] = ++cnt;
            id[i] = Hash[core];
        }

        int q;
        cin >> q;
        while (q--) {
            int x, y;
            cin >> x >> y;
            cout << (id[x] == id[y] ? "Yes" : "No") << endl;
        }

        Hash.clear();
        for (int i = 1; i <= n; ++i)    id[i] = 0;
    }

    return 0;
}


Assertion

唯一的一道水题。抽屉原理。


Play on Tree

好题，一道题覆盖了博弈论 + 换根两个知识点。哪天找个时间写下关于 NIM 游戏，SG 定理的东西，这些概念确实很有趣，但也很烧脑。

Tutorial 里直接把结论摆出来了：\(\mathrm{SG}(u)=(\mathrm{SG}(v_1)+1)\oplus(\mathrm{SG}(v_2)+1)\oplus(\mathrm{SG}(v_3)+1)\)，然而这对我来说一点都不显然。我还是想详细的证明一下，不然说服不了我自己。

首先定义 base case：

  • 当 \(n=1\) 时，必输态，\(\mathrm{SG}(u)=0\)。
  • 当 \(n=2\) 时，\(\mathrm{SG}(u)=\mathrm{MEX}\{\mathrm{SG}(v)\}=\mathrm{MEX}\{0\}=1\)，满足 \(\mathrm{SG}(u)=\mathrm{SG}(v)+1\)。

开始进行数学归纳法：若 \(n\leq k\) 时该结论成立，则 \(n=k+1\) 时该结论仍然成立。

设根节点为 \(u\)，且 \(\mathrm{size}(u)=k+1\)。

  • 当 \(u\) 只有一颗以 \(v\) 为根的子树时。(显然 \(\mathrm{size}(v)=\mathrm{size}(u)-1=k\))
    • 删去 \(v\) 必胜，该局面存在 \(\mathrm{SG}(u')=0\) 的后继。
    • 删去 \(v\) 子树中某内部节点得到局面 \(v'\)；此时 \(\mathrm{size}(u')\leq k\)；由归纳假设得 \(\mathrm{SG}(u')=\mathrm{SG}(v')+1\)。由于 \(v'\) 是 \(v\) 的后继局面，根据 \(\mathrm{SG}\) 函数定义有 \(\mathrm{SG}(v')\in[0,\mathrm{SG}(v)-1]\)。
    • 由 (ii) 得 \(\mathrm{SG}(u')=\mathrm{SG}(v')+1\in[1,\mathrm{SG}(v)]\)，又由 (i) 可知 \(\mathrm{SG}(u')\) 可取到 \(0\)：综上所述，局面 \(u'\) 的 SG 值 \(\mathrm{SG}(u')\in[0,\mathrm{SG}(v)]\)。
    • 根据 SG 函数的定义，\(\mathrm{SG}(u)=\mathrm{MEX}\{\forall {\mathrm{SG}(u'\}}\}=\mathrm{SG}(v)+1\)，归纳完毕。
  • 当 \(u\) 有若干棵子树 \(v_1,v_2,v_3...v_m\) 时。
    • 观察到根节点 \(u\) 对答案没有影响 (删除 \(u\) 必败，后继局面的 SG 函数无限大)，我们将 \(u\) 拆点，有 \(m\) 颗子树就拆成 \(m\) 个点 \(u_1,u_2,...,u_m\)，每个点挂一颗子树。
    • 这样我们把游戏转化为了 \(m\) 个子游戏，本质上与 \(m\) 堆石头的 NIM 游戏没有区别。
    • 根据 SG 定理，\(\mathrm{SG}(u)=\oplus_{i=1}^m \mathrm{SG}(u_i)\)；在情况一中我们已经证明 \(\mathrm{SG}(u_i)=\mathrm{SG}(v_i)+1\)，至此我们证明了那个“显然的”结论 \(\mathrm{SG}(u)=\oplus_{i=1}^m (\mathrm{SG}(v_i)+1)\)。

至于换根就比较简单了，我们定义 \(g_u\) 为 \(u\) 父亲方向子树的答案，DFS 一遍即可求出 \(g\)。设以 \(1\) 为根时 \(u\) 子树的 SG 函数为 \(\mathrm{SG}(u)\)，那么最后的答案为 \(\frac{1}{n}\sum[\mathrm{SG}(u)\oplus g_u>1]\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>

using namespace std;

const int mod = 1e9 + 7;
const int MAX_N = 2e5 + 10;

int n;
int SG[MAX_N], g[MAX_N];

vector<int> e[MAX_N];

int qpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)
            res = 1LL * res * x % mod;
        y >>= 1;
        x = 1LL * x * x % mod;
    }
    return res;
}

int dfs1(int u, int fa) {
    for (int to : e[u]) {
        if (to == fa)   continue;
        SG[u] ^= (dfs1(to, u) + 1);
    }
    return SG[u];
}

void dfs2(int u, int fa) {
    if (fa != 0) {
        g[u] = (SG[fa] ^ (SG[u] + 1) ^ g[fa]) + 1;
    }
    for (int to : e[u]) {
        if (to == fa)   continue;
        dfs2(to, u);
    }
}

int solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        e[i].clear();
        SG[i] = g[i] = 0;
    }
    
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs1(1, 0);
    dfs2(1, 0);

    int ans = 0;
    if (SG[1] > 0)  ans = 1;
    for (int i = 2; i <= n; ++i) {
        if (SG[i] ^ g[i])   ++ans;
    }

    return 1LL * ans * qpow(n, mod - 2) % mod;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--) {
        cout << solve() << endl;
    }

    return 0;
}


Reference

-----------------------------------そして、次の曲が始まるのです。-----------------------------------