20thZJCPC

省赛补题，顺序大致按难度(赛时通过人数)排列

CF的gym里暂时还没有今年省赛的题目上传，目前只查到了D/F/G/H/I的补题链接
2023.08.22

A.Look and Say

翻译：

给一个数字序列，你需要使用以下方法“描述”它：

1.每段划分成最大的连续相同的数字；

2 . 对于每段，将其替换为段的长度加段中的数字。例如，“0” 应替换为 “10”， ”9999999999“ 应替换为“109”

3.将替换的段连接在一起并输出

输入：

第一行包含一个整数n，范围是[1,1000]，表示输入序列的长度；

第二行为一个长度为n的序列，表示原始序列

输出：

输出转换后的序列

签到题，就是相同连续的数字压缩成长度+数字的组合输出

#include <bits/stdc++.h>

using namespace std;

int n, cnt = 1;
char pre = '#', t;

signed main() {
    freopen("input.txt", "r", stdin);
    freopen("my.txt", "w", stdout);
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t;
        if (t == pre)++cnt;
        else if (pre != '#') {
            cout << cnt << pre;
            cnt = 1;
        }
        pre = t;
    }
    cout << cnt << t;
    return 0;
}

E.Interval Sum

翻译

构造一个长度为n的排列，使其所有子序列的和中能够被n整除的子序列的个数最多，输出任意一种构造。

输入：

一个n，表示排列的长度

输出：

一行排列，空格分开排列中的元素

一道贪心题，猜想比较好想：考虑哪些数相加为n，有n，{1，n-1},{2,n-2}…..注意n是偶数时，要把n放排列的最前面或者最后面，并且最后没有{n/2,n-n/2}这种组合

#include <bits/stdc++.h>

using namespace std;

int n, t;

signed main() {
    freopen("input.txt", "r", stdin);
    freopen("my.txt", "w", stdout);
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    t = n / 2 + (n & 1);
    if (!(n & 1))cout << n / 2 << ' ';
    cout << n << ' ';
    for (int i = 1; i < t; ++i) cout << i << ' ' << n - i<<' ';
    return 0;
}

这道题P9573 「TAOI-2」核心共振和它比较像，但更难一点

M.A Wine and Four Dishes

翻译：

Rice老师为自己准备了一场盛宴。宴会上有x瓶酒和y盘菜，这意味着他需要x杯和y盘。

有n个箱子。第i个盒子里有a杯子和b盘子。请帮助Rice老师确定他必须打开的最小数量的盒子，这样他才能收集到足够的杯子和盘子。如果Rice老师不可能收集到足够的杯子或盘子，那么输出“IMPOSSIBLE”。

输入

第一行包含了三个整数n,x,y表示箱子数，瓶子和盘子数

接下来n行表示每个箱子含有的瓶子和盘子数量

输出

最小数量的盒子，无解输出IMPOSSIBLE

贪心题，注意到每个箱子包含的盘子数是[0,1]，所以如果x不是0，那么优先从含有x的箱子中选最大的那几个，选完了就选剩下的箱子中y最大的那几个，如果选完了都凑不出那么就是无解，数据很小，随便做都可以过

#include <bits/stdc++.h>

using namespace std;

struct Bottle {
    int a, b;
} box[40];
int n, x, y, bound = 1, t;

signed main() {
    freopen("input.txt", "r", stdin);
    freopen("my.txt", "w", stdout);
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> x >> y;
    if (!(x || y)) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= n; ++i) cin >> box[i].a >> box[i].b;
    if (x) {
        sort(box + 1, box + 1 + n, [&](Bottle A, Bottle B) { return A.a > B.a || A.a == B.a && A.b > B.b; });
        if (!box[x].a) {
            cout << "IMPOSSIBLE";
            return 0;
        }
        for (int i = 1; i <= x; ++i, ++bound) t += box[i].b;
        if (t >= y) {
            cout << x;
            return 0;
        }
        sort(box + bound, box + 1 + n, [&](Bottle A, Bottle B) { return A.b > B.b; });
        for (int i = bound; i <= n; ++i) {
            t += box[i].b;
            if (t >= y) {
                cout << i;
                return 0;
            }
        }
        cout << "IMPOSSIBLE";
    } else {
        sort(box + 1, box + 1 + n, [&](Bottle A, Bottle B) { return A.b > B.b; });
        for (int i = 1; i <= n; ++i) {
            t += box[i].b;
            if (t >= y) {
                cout << i;
                return 0;
            }
        }
        cout << "IMPOSSIBLE";
    }
    return 0;
}

比赛的时候还不知道sort还有这种写法，嫌写比较函数太复杂用优先队列和pair瞎搞做对的，有些队伍用搜索剪枝过的，好像背包也可以

F.Turn the Light

翻译：
这是一个交互问题。
Putata有n个灯，从1到n从左到右编号。最初，所有的灯都是关着的。其中一盏灯是他最喜欢的灯,灯的号码是隐藏的。 Budada想知道Putata最喜欢的灯的编号，他可以做如下查询:
“? x”:如果x的灯是关的，打开编号为x的灯，然后问putata，在putata最喜欢的灯的左边打开的灯数的绝对值减去右边打开的灯数。
Budada只能进行不超过40次的查询。请帮他找到putata最喜欢的灯。在这个问题中，交互者是自适应的，这意味着答案可能不是固定的，交互者可以任意选择它，并且答案将与你与交互者的交互相一致。
已通过此oj的评测
2023.08.22
一眼二分，因为首先这个数据范围符合二分(log2(n)<40)，并且不难看出如果输出和上一次比较没有变化那么那个数就是喜欢的数，但是发现由于输出的是差的绝对值，所以没有单调性，但又发现log2(n)*2是一个接近40的数，所以猜测每次问两次保证单调性：每次都先问左边界的数是不是喜欢的数字，然后再二分问中间的数是不是喜欢的先问左边界就保证了左边的数始终大于右边的数，也就去掉了绝对值使其有了单调性。

#include <bits/stdc++.h>

using namespace std;

int n, pre, t;

signed main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + 1 + r) >> 1;
        cout << "? " << l << endl;
        cin >> t;
        if (t == pre) {
            cout << "! " << l << endl;
            return 0;
        }
        pre = t;
        cout << "? " << mid << endl;
        cin >> t;
        if (t == pre) {
            cout << "! " << mid << endl;
            return 0;
        }
        if (pre > t) r = mid - 1, l++;
        else l = mid + 1;
        pre = t;
    }
    return 0;
}

//验题代码
#include <bits/stdc++.h>

#define random(a, b) ((a)+rand()%((b)-(a)+1))

using namespace std;

int n, pre, t;

bool st[1000006];
int lLight, rLight, cnt;


void get_num(char c, int x, int fav) {
    ++cnt;
    if (c == '!') {
        if (x == fav && cnt <= 40)cout << "Accept" << endl;
        else if (cnt > 40)cout << "Time Limit Error" << endl, getchar();
        else cout << "Wrong Answer" << endl, getchar();
    } else {
        if (x > fav && !st[x]) {
            ++rLight;
            st[x] = true;
        }
        if (x < fav && !st[x]) {
            ++lLight;
            st[x] = true;
        }
        cout << abs(lLight - rLight) << endl;
        t = abs(lLight - rLight);
    }
}

void init() {
    memset(st, false, sizeof st);
    n = pre = t = lLight = rLight = cnt = 0;
}

void solve() {
    init();
    n = random(1, 1000000);
    int num = random(1, n);
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << n << endl;
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + 1 + r) >> 1;
        cout << "? " << l << endl;
        get_num('?', l, num);
        if (t == pre) {
            cout << "! " << l << endl;
            get_num('!', l, num);
            return;
        }
        pre = t;
        cout << "? " << mid << endl;
        get_num('?', mid, num);
        if (t == pre) {
            cout << "! " << mid << endl;
            get_num('!', mid, num);
            return;
        }
        if (pre > t)
            r = mid - 1, l++;
        else
            l = mid + 1;
        pre = t;
    }
}


signed main() {
    for (int i = 1; i <= 1024; ++i) {
        cout << "正在运行第" << i << "个数据" << endl;
        solve();
    }
    return 0;
}

跑了很多组对拍发现其实这个算法能够在29次询问以内通过

K. Lazy but Diligent

翻译：
PigeIand大学拥有n幢编号分别为1-n的建筑物，其中1号楼是学生宿舍，其他是教学楼。所有建筑物通过双向路径连接，其中第i条路是长度为li,链接xi和yi楼，从a时间开始，到b时间结束。小猪需要在t时间后回到宿舍休息，更重要的是，在她的学习时间，小猪可以偷偷溜回去睡觉。小猪很懒，但很聪明，所以她希望 在学习期间至少花 s 个单位的时间在宿舍睡觉。我们认为小猪参加课程i，当且仅当她在从ai到bi的时间里都待在pi楼，这意味着她必须完成整个课程。请输出小猪最多能学习多少门课程，同时满足她的睡眠要求。
输入：
第一行包含五个整数n，m，g，t，s，表示建筑物的数目、道路的数目、课程的数目，总学习时间，需要睡眠的时间
以下m行中的每一行都包含三个整数$x_{i},y_i,l_i$，表示连接x和y的双向路径，长度为l。
以下q行中的每一行都包含三个整数$a_i,b_i,p_i$，表示这门课程在p楼从a点开始到b点结束。
输出：
最多能学习多少门课程

这题的程序对拍目前只验证了树这一特殊图的情况
2023.08.21
第一次做这种图上的dp。一般没有什么思路感觉像深搜的时候就可以考虑dp了。
n个楼，m条路，m的数据保证了图是联通的，q个课程，问在满足条件下最多可以学几门。
看范围q<=400,考虑n^3的dp，也就是说状态的维数必须是小于等于3，首先因为要枚举，所以显然有一维一定是i，表示当前枚举到第几个课程，那么可以发现上一步在哪里也会影响到后面的决策，所以再加一维j，表示在哪里，由于要枚举当前和之前在哪里，所以复杂度再加上n^2,总复杂度在n^3左右可以通过。
除了第i个课并且此时在j楼时最多能学习的课程的数目要用dp表存储以外，这道题还需要在第i个课并且此时在j楼时最多能休息的时间长度上dp，因为存在中途可以回去睡觉的情况：当这个人前一步在k位置并且要走到j位置时，因为j课程有开始时间的限制，所以如果他走到j还要花时间等待j课程到开始时间，所以不如在k点时先回到1号点休息后再从1号点走到j点，这样就能保证在不耽误课程的情况下能够谁最多的时间（前提是回1号点再走到j点不会大于j课程开始时间）。
状态定义：
dp[i][j]，表示已经上到i个课并且此时在j楼时最多能学习的课程的数目
rest[i][j],表示已经上到i个课并且此时在j楼时最多能休息的时间的长度
状态转移：
当枚举的前一个有课的教学楼的位置能够到达（只有在这个位置上过课的才有必要停留在这个位置，否则对于结果没有贡献也就没有必要到那个位置），并从这幢楼的课程的结束时间加上从这个位置到当前想去的位置所需要的时间：
即当满足：
dp[i - 1][course[k].p] && dist[course[k].p][course[j].p] + course[k].b <= course[j].a
就可以计算从k点时先回到1号点休息后再从1号点走到j点最多可以休息的时间restT：
restT = max(course[j].a - course[k].b - dist[course[k].p][1] - dist[1][course[j].p], 0)
然后需要判断两个限制条件：一个是学完课程后能不能在规定的时间内回到1号点，第二个是总的睡眠时间小于需要的睡眠时间，
即当满足：
course[j].b + dist[course[j].p][1] <= t && (t - course[j].b - dist[course[j].p][1]) + restT + rest[i - 1][k] >= s
有转移方程：
dp[i][course[j].p] = max(dp[i][course[j].p], dp[i - 1][course[k].p] + 1)
rest[i][j] = min(s, max(rest[i][j], rest[i - 1][k] + restT))
同时更新答案：ans = max(ans, dp[i][course[j].p])
开始之前先floyd跑出任意2栋楼直接最短路，存在dist数组里预处理。也要预处理出到第一个位置可以睡的最长时间和能不能到达那个位置，因为第一个位置比较特殊不用考虑前一个位置

5 4 3 10 2
3 4 1
2 5 1
4 5 1
3 1 1
2 9 2
3 9 4
6 8 3
output：1


5 4 4 15 3
3 4 1
4 1 1
5 2 2
5 3 2
5 6 4
8 9 3
13 14 2
4 6 5
output：2

hack：

6 5 1 5883 1327
2 1 43
3 2 8
4 3 48
5 2 37
6 2 43
1398 5257 2
output：1

7 6 5 3760 1835
2 1 2
3 2 16
4 2 53
5 2 89
6 2 61
7 6 49
320 1728 4
437 2046 2
1950 2242 6
3754 3758 3
1689 3242 5
output: 1

6 5 3 1967 1249
2 1 40
3 1 72
4 3 93
5 1 49
6 3 36
1651 1928 5
591 770 6
1557 1612 4
output:1

大样例:
155 154 126 3118 1830 
2 1 7
3 2 10
4 2 7
5 1 66
6 2 89
7 6 42
8 4 81
9 3 59
10 1 28
11 8 33
12 4 38
13 3 70
14 3 93
15 13 71
16 15 28
17 2 87
18 8 41
19 4 67
20 13 12
21 15 27
22 15 59
23 15 72
24 4 6
25 11 59
26 12 12
27 8 57
28 15 50
29 15 51
30 4 18
31 1 82
32 3 66
33 3 35
34 10 28
35 5 89
36 14 70
37 5 22
38 15 93
39 10 52
40 29 8
41 25 10
42 26 103
43 39 36
44 7 65
45 21 71
46 37 91
47 11 67
48 8 52
49 32 91
50 31 46
51 10 83
52 19 58
53 42 77
54 31 85
55 30 31
56 2 37
57 31 104
58 26 20
59 55 14
60 47 73
61 60 27
62 12 43
63 36 36
64 19 95
65 33 71
66 27 3
67 17 99
68 29 4
69 17 32
70 63 64
71 44 51
72 20 25
73 31 47
74 65 23
75 43 29
76 50 5
77 59 63
78 60 17
79 30 86
80 41 32
81 3 15
82 26 72
83 80 2
84 39 49
85 66 40
86 22 26
87 5 7
88 38 91
89 22 96
90 36 4
91 52 52
92 66 99
93 52 54
94 1 73
95 67 1
96 6 21
97 65 23
98 90 91
99 42 32
100 75 55
101 90 47
102 10 1
103 32 77
104 47 86
105 5 76
106 83 50
107 90 3
108 52 88
109 10 72
110 40 96
111 71 71
112 45 10
113 21 85
114 21 56
115 15 80
116 40 59
117 34 78
118 60 66
119 114 47
120 64 24
121 72 19
122 101 68
123 46 27
124 55 17
125 22 13
126 8 12
127 49 96
128 70 28
129 58 35
130 108 21
131 58 65
132 40 9
133 100 37
134 65 73
135 74 76
136 17 54
137 42 63
138 21 32
139 44 102
140 45 91
141 17 40
142 120 56
143 74 78
144 31 1
145 12 75
146 47 46
147 26 86
148 30 14
149 115 69
150 32 12
151 57 87
152 106 20
153 110 57
154 139 3
155 121 60
1889 2840 127
2328 2789 9
1254 1456 52
2231 3048 25
1937 2019 96
71 117 91
556 1318 79
2029 2616 33
363 1158 29
60 1979 40
2938 2971 95
1506 2530 15
484 1232 13
2142 2273 94
2418 3085 26
1456 2049 69
409 2793 81
2506 2876 122
1694 2651 43
2734 3020 87
665 1578 134
1107 1681 145
2654 3059 73
387 1226 143
1957 2556 133
1355 1893 93
995 1661 152
1011 2205 51
1251 2780 58
2251 2374 121
1824 1847 54
504 1866 42
738 2361 154
1233 1627 78
1330 2763 68
1994 2048 18
1636 2392 66
17 2079 155
1324 2415 45
675 1181 129
1536 2185 108
1332 1752 57
1307 2932 85
1078 1130 99
902 982 24
1791 2453 21
1528 2256 148
3032 3047 114
1493 3016 103
1298 2529 104
434 2578 63
1682 2611 36
1722 3056 5
350 2091 20
1822 2810 62
1196 1885 38
486 1738 105
722 1375 17
495 1559 120
262 837 37
404 2209 124
1621 2570 89
1966 2783 65
2970 3024 50
2020 3033 136
1410 1559 83
504 1481 90
288 1350 97
755 1289 117
1232 1552 80
2967 3025 70
1695 2304 106
2874 2900 109
1257 3109 56
1900 2510 101
2535 2961 32
2636 2975 48
2951 2962 14
2964 2994 130
1325 1407 35
60 523 88
1701 2273 12
710 2279 31
557 668 76
2459 2546 111
2925 3092 119
700 2041 128
2117 2311 125
2152 2252 126
1646 2038 8
1867 3039 102
2341 2360 34
906 1225 86
1270 1906 150
267 2672 39
1684 1807 55
1622 1746 149
170 1839 142
1234 2035 132
3045 3065 151
1832 2659 2
2800 3045 110
56 1396 135
2119 3050 140
218 299 118
1911 2022 41
1737 2205 137
2694 2728 27
1661 2797 72
1662 2828 131
49 390 146
2206 2350 3
293 331 10
1784 2204 47
43 192 74
596 769 46
2109 2766 144
2992 3050 22
2381 3024 123
2156 2873 107
67 1236 67
717 726 98
2357 2483 4
211 686 100
1506 2983 116
1196 1301 77
output:6

#include <bits/stdc++.h>

#define N 405
using namespace std;

int dist[N][N], dp[N][N], n, m, q, t, s, ans;
int rest[N][N];

struct Node {
    int a, b, p;
} course[N];

void floyd() {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

}

signed main() {
    //freopen("input.txt", "r", stdin);
    //freopen("my.txt", "w", stdout);
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m >> q >> t >> s;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[b][a] = min(dist[a][b], c);
    }
    floyd();
    for (int i = 1; i <= q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        course[i].a = a, course[i].b = b, course[i].p = c;
    }
    for (int i = 1; i <= q; ++i) {
        if (dist[1][course[i].p] <= course[i].a) {
            rest[1][i] = min(course[i].a - dist[1][course[i].p], s);
            if (t - (dist[course[i].p][1] + course[i].b) + rest[1][i] >= s) {
                ++dp[1][course[i].p];
                ans = max(ans, dp[1][course[i].p]);
            }
        }
    }
    for (int i = 2; i <= q; ++i)
        for (int j = 1; j <= q; ++j)
            for (int k = 1; k <= q; ++k)
                if (dp[i - 1][course[k].p] && dist[course[k].p][course[j].p] + course[k].b <= course[j].a) {
                    int restT = max(course[j].a - course[k].b - dist[course[k].p][1] - dist[1][course[j].p], 0);
                    if (course[j].b + dist[course[j].p][1] <= t && (t - course[j].b - dist[course[j].p][1]) + restT + rest[i - 1][k] >= s) {
                        dp[i][course[j].p] = max(dp[i][course[j].p], dp[i - 1][course[k].p] + 1);
                        rest[i][j] = min(s, max(rest[i][j], rest[i - 1][k] + restT));
                        ans = max(ans, dp[i][course[j].p]);
                    }
                }
    cout << ans;
    return 0;
}

//对拍代码，生成的不是一张图而是一棵树，没有判断过不是树的情况
#include<bits/stdc++.h>
using namespace std;

#define random(a, b) ((a)+rand()%((b)-(a)+1))

int dsu[1000005];
int mapp[10000005];
bool st[1000005];

void build(int n) {
    ofstream fout("input.txt",ios::trunc);
    //ofstream fout("input.txt",ios::app);
    //fout.seekp( 0, ios::end);
    int q = random(1,n-1),t = random(3,10004);
    int s = random(0,t);

    for (int i = n; i >= 2; --i) {
        dsu[i] = random(1, i - 1);//生成一颗以1为根节点的树
    }
    for (int i = 1; i <= n; ++i) mapp[i] = i;
    //打印树，必要可以随机边权
    cout << n << ' '<< n-1<< ' '<<q<< ' '<<t<< ' '<<s<< ' '<<endl;
    fout << n << ' '<< n-1<< ' '<<q<< ' '<<t<< ' '<<s<< ' '<<endl;
    for (int i = 2; i <= n; ++i) {
        int temp = random(1,104);
        cout << mapp[i] << ' ' << mapp[dsu[i]] << ' '<<temp <<endl;
        fout << mapp[i] << ' ' << mapp[dsu[i]] << ' '<<temp<< endl;
    }
    for(int i = 1;i<=q;++i){
        int p = random(2,n);
        while(st[p])p = random(2,n);
        int a = random(1,t-2);
        int b = random(a+1,t-1);
        cout<<a<<' '<<b<<' '<<p<<endl;
        fout<<a<<' '<<b<<' '<<p<<endl;
    }
    fout.close();
}


void create_dataset() {
    int n = random(2, 400);
    int t = 1;
    while (t--) build(n);
    //::getchar();
}

bool work() {
    create_dataset();
    //system("standDP.exe < input.txt > stand.txt");
    //system("myDP.exe < input.txt > my.txt");
    system("stand.exe < input.txt");
    system("my.exe < input.txt");
    return system("fc stand.txt my.txt");

}

void dp(int tot){
    for (int i = 1; i <= tot; i ++ ) {
        cout << "正在运行第" << i << "个数据" << endl;
        if(work()){
            cout << "出错了\n";
            getchar();
        }
    }
}

int main() {
    srand(time(nullptr));
    //work(); 
    dp(512);
    cout << "Done";
    return 0;
}

这道题算不上太难，但因为实现细节有很多，算上Floyd一共做了3次dp，补题的时候包括写对拍程序一共做了两个晚上，每次对拍都会出现不少没有考虑到的情况，第一次的时候没有考虑到存在中途回去睡觉可以是最优解的情况，之后的几次都是在代码的细节上出错，比如dp[i][course[j].p]写成dp[i][j]等，而且是在有clion的静态代码分析的情况下写了这么久，比赛时devc++没有分析和代码补全功能，所以在那种环境下更有可能没处理好拿好几次罚时。

G. Puzzle: Kusabi

Grammy是个拼图高手。今天，她正在玩“Kusabi”拼图的变体。在这个变体中，有一棵有根的树，上面有一些汉字。树的根是顶点1，没有标记。有标记的顶点可以有“长”、“短”或“同”的符号。其目标是将所有标记的顶点连接成对，以便:
每个标记顶点通过标记它们之间的最短路径上的每条边连接到另一个标记顶点
字符“长”的顶点与根之间的距离必须比对应点到根的距离长。
字符“短”的顶点与根之间的距离必须比对应点到根的距离短。
字符“同”的顶点与根之间的距离必须与对应点到根的距离相同。
树上的每一条边最多只能标记一次。
左图展示了一个只有条件的可行谜题，右图展示了一个可行的解题方法。
Grammy当然知道如何解决这个难题，但她决定给你一个小测验。请解开这个谜题。
输入：
第一行包含一个整数n(1接下来的n-1行中的每一行都包含两个整数i，$p_i$和字符串$t_i(t_i\in \left \{ chang,duan,tong,- \right \} )$表示在$p_i$和i之间有一条边，以及顶点的类型I是$t_i$”_”表示未标记顶点i)。保证i是按递增顺序给出的。还保证至少有一个标记的顶点。
输出：
如果解决方案不存在，则在单行上输出“NO”
否则，在第一行输出“YES”，然后输出几行，每行包含两个整数Ui，Vi，表示解决方案中的一对连接顶点。如果有多个解，输出任意一个。
已通过此oj的评测
2023.08.22

贪心题：
1.显然总的标记为Tong的数量必须为偶数，Chang和Duan数量一定相同
2.标记为Tong的一定和相同深度的配对，标记为Chang的深度为第i深的一定和深度为第i深的标记为Duan的配对，如果配不上则需要考虑第3条贪心策略是不是无解，证明：
$S_{Duan} = \left \{…i…j… \right \} ,S_{Chang} = \left \{…i…j… \right \} $
假设没有按照这个规则配对，则必有“Duan”的i和“Chang”的j配对（i小于j）,可以发现“Duan”的j号点所对应的“Chang”被占，“Duan”的j号点又不一定可以与小于j的“Chang”的点配对，也就是说选择变少了，如果“Duan”的j号位的深度大于“Chang”的点中的j-1号位，那么就无法配对，最优性不如原先的假设，所以按照之前的排法是最优的。
3.对于一棵子树，最多只能留出一个点无法与子树内的其他点配对，去和别的子树上的点去配对，否则无解，这个也是显然的，因为要去到别的子树的最短路，有一条边是必须要经过的：子树的根节点到这颗子树的父亲节点的这条边，因为每条边只能经过一次，所以最多只能保留一个结点；还有一种可能无解是考虑当前子树的剩下那个点不是给“Tong”节点并且“Tong”的个数是奇数，那么一定无解
4.保留的一个结点的选择：
对于“Chang”和“Duan”这种节点有剩的：“Chang”结点剩最长的，因为这样可以选择的“Duan”结点就会最多，“Duan”也是同理，应该剩最短的
对于“Tong”这种结点有剩的：保留的结点只要选择不能配对的就可以，对深度没有要求，因为不管怎样都一定要和深度一样的配对，实现方法很简单，对所有没有配对的“Tong”结点小到大排序，排完之后两两配对，如果剩下最后一个配不上或者两两配对时深度不一样就将这个点存为剩下的点，注意无解的情况：考虑这棵树最后是不是还保留了一个“Tong”结点，如果是，那么也是无解的
红点表示“Tong”蓝点表示不是“Tong”的标记点，第一张图表明第一种无解情况，第二张表明第二种无解情况，注意并不需要特地判断当前子树是不是存在两个及以上的无法配对的情况，证明需要根据奇偶性分四类讨论：
1.假设当前子树剩的是偶数个未配对的“Tong”结点，并且根节点的父节点除当前子树以外所包含的“Tong”结点个数是奇数，那么总共加起来一定是奇数，一定会留下一个交给其他子树配对，参考第二张图去掉左上那个节点的情况；
2.假设当前子树剩的是偶数个未配对的“Tong”结点，并且根节点的父节点除当前子树以外所包含的“Tong”结点个数是偶数，那么因为当前子树会尝试和其他不是该子树上的“Tong”节点配对，不管怎么配对于根节点的父节点来说都是配不完的，一定会留下一个交给其他子树配对；
3.假设当前子树剩的是奇数个未配对的“Tong”结点，并且根节点的父节点除当前子树以外所包含的“Tong”结点个数是奇数，那么如果配的上就可以配成合法情况（剩0个），如果配不上也会剩下偶数个，也就变成了第一第二种情况
4.假设当前子树剩的是奇数个未配对的“Tong”结点，并且根节点的父节点除当前子树以外所包含的“Tong”结点个数是偶数，同第一种情况，那么总共加起来一定是奇数，一定会留下一个交给其他子树配对；
所以观察无解的情况都是会剩下一个和其他子树上的节点配对，所以可以有由叶子结点归纳，一步一步扩大子树的大小直到变成一整棵树都是这样的情况，由于到一整棵树还是会剩一个，这种情况就是第二个无解情况，所以不需要考虑
5.这种贪心决策的路径一定不会重叠，证明用类似树形dp的思想，可以从最原始的情况一步步归纳：
最底层：当前只有叶子结点时，显然不用考虑，
往上一层：将所有同一个父结点的叶子结点连接与父结点组成子树，那么就算是前面讨论的有剩余的未配对结点，那也是最多选出一个通过父结点和其他子树相连，也就相当于是父结点存在一个标记为“Chang”“Duan”“Tong”中的任意一个，他的儿子结点因为已经配对完就不用考虑，所以不会重叠
归纳：对父结点和它对应的祖先组成子树，这个子树显然也可以看成第二层的情况，也不会出现重叠
所以整个情况合起来路径不会重叠,因此这种贪心策略是正确的
代码的实现：
d[u]数组：存储当前结点对应的深度
ver[u]数组：存储当前结点对应的种类，0表示不是特殊点，1-3表示“Duan”“Chang”“Tong”，三种状态
remain[u]数组：存储当前结点的儿子们有无剩余的未配对的结点，数值同ver数组
num[u][i]数组：存储当前u结点下包括自身的所有状态为i的结点个数
edge[N]数组：邻接表存图
v[i]vector数组：存储当前子树所有没有配对的结点，并可由size()统计个数
flag变量：表示当前是否有无解的状态

#include<bits/stdc++.h>

using namespace std;
const int N = 1000005;

typedef pair<int, int> PII;
int d[N], ver[N], remain[N], num[N][4], n;
bool flag = true;
char s[10];
vector<PII> ans;
vector<int> edge[N];

void dfs(int u, int par) {
    vector<int> v[4];
    d[u] = d[par] + 1;//计算深度
    ++num[u][ver[u]];//计算当前u结点的转态
    for (int i = 1; i <= 3; ++i) if (ver[u] == i)v[i].push_back(u);//计算当前结点属于哪个状态
    for (auto &ne: edge[u]) {//递归儿子结点
        if (ne == par) continue;
        dfs(ne, u);
        for (int i = 1; i <= 3; ++i)
            if (ver[remain[ne]] == i) v[i].push_back(remain[ne]);//存储儿子结点的状态
        for (int i = 1; i <= 3; ++i) num[u][i] += num[ne][i];//存储所有i状态的数量
    }
    if (!flag) return;//判断有无解，无解就不用再继续运行
    //特判两种无解情况
    if (abs(num[u][1] - num[u][2]) >= 2) {//如果当前“Chang”和“Duan”个数相差大于1就说明无解
        flag = false;
        return;
    }
    if (num[u][1] != num[u][2] && (num[u][3] & 1)) {//如果当前子树的剩下那个点不是给“Tong”节点并且“Tong”的个数是奇数，那么一定无解
        flag = false;
        return;
    }
    //排序
    for (int i = 1; i <= 3; ++i)
        sort(v[i].begin(), v[i].end(), [&](const int u, const int v) { return d[u] < d[v]; });
    int v1 = (int) v[1].size(), v2 = (int) v[2].size(), v3 = (int) v[3].size();
    //分类遍历
    for (int i = 0; i < v3; i += 2) {
        if (i == v3 - 1) {
            remain[u] = v[3][i];
            break;
        }
        if (d[v[3][i]] != d[v[3][i + 1]]) remain[u] = v[3][i++];
        ans.emplace_back(v[3][i], v[3][i + 1]);
    }
    if (num[u][1] > num[u][2]) {
        int l = v1 - 1, r = v2 - 1;
        while (l >= 0 || r >= 0) {
            if (l >= 0 && r >= 0 && d[v[1][l]] < d[v[2][r]]) {
                ans.emplace_back(v[1][l--], v[2][r--]);
            } else if (!remain[u] && l >= 0) {
                remain[u] = v[1][l--];
            } else {
                flag = false;
                return;
            }
        }
    } else {
        int l = 0, r = 0;
        while (l < v1 || r < v2) {
            if (l < v1 && r < v2 && d[v[1][l]] < d[v[2][r]]) {
                ans.emplace_back(v[1][l++], v[2][r++]);
            } else if (!remain[u] && r < v2) {
                remain[u] = v[2][r++];
            } else {
                flag = false;
                return;
            }
        }
    }
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v >> s;
        edge[u].push_back(v), edge[v].push_back(u);
        if (s[0] == 'D')ver[u] = 1;
        if (s[0] == 'C')ver[u] = 2;
        if (s[0] == 'T')ver[u] = 3;
    }
    dfs(1, 0);
    if (!flag || remain[1]) cout << "NO\n";//注意remain[1]里面有东西也是无解的
    else {
        cout << "YES\n";
        for (auto &it: ans)
            cout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}

树上贪心问题，这题的贪心策略并不算好想，也融合了树的遍历，树形dp的思想，由于树这种结构天然的适合dp和递归，所以题目就算没有要用树形dp去解也要考虑是否可以利用这个特殊的结构去实现算法，这道题的坑点也很多，像没看到每条边只能经过一次这个条件就会误以为是很简单的一道贪心题，最后关于“Tong”结点的处理也不好想到，很难在短时间内验证正确性

H. Puzzle: Tapa

翻译：
Grammy是解谜大师，今天，她正在玩一个“Tapa”拼图的变体。在这个变体中，有 (2n − 1)×(2m−1)矩形网格上的n×m个线索。所有线索都位于单元格（i，j）上，其中i，j都很奇怪。每条线索都是一个等于或比周围单元格数小1的数字线索。具体来说，网格角落上的线索可以是2条或3条，网格边缘上的线索可以是4或5并且网格中心上的线索可以是7或8。目标是对一些格子进行遮光，例如即：
•所有线索单元格都未加阴影。
•每个线索单元格表示其周围连续阴影单元格的数量。
左上图显示了一个可能的5×5网格，只有线索，右上图显示了可能的解决谜题的方法，底部的图片显示了一个错误的谜题解决方案，因为阴影4周围的单元格是不连续的。
Grammy肯定知道如何解决这个难题，但她决定给你一个小测验。请解开这个谜题。
输入
第一行包含两个整数n，m（2≤n，m≤50），表示网格的大小。
接下来的2n−1行中的每一行都包含2m−1个字符，表示具有给定线索的网格。点（’.’）
表示没有线索的单元格，而数字表示单元格上的线索。它保证了
奇数行和奇数列的交叉点有一条线索，所有其他单元格都不包含任何线索。
输出
如果解决方案不存在，则在单行上输出“NO”。
否则，在第一行输出“YES”，然后输出2n−1行，每行包含2m−1个字符，
表示谜题的答案。格式类似于输入网格，但您应该标记
用“#”对单元格进行着色。换句话说，输出中的点（’.’）表示一个没有线索的无阴影单元格，
（’#’）表示带阴影的单元格，数字表示单元格上的线索。
如果有多个解决方案，请输出任何一种解决方案。
已通过此oj的评测
2023.08.26
大致意思就是扫雷，数字表示周围连续的雷的数量，判断有无解，如果有解就输出任意一种，注意涂色的点必须是联通的。

这题的通过率低到离谱，是除了只有一队通过的C题以外最低的一题，原因可能是题目只说了每个线索单元格表示其周围连续阴影单元格的数量，没有说明要涂色的点必须是联通的，像

3 3
3.2.3
.....
5.7.5
.....
3.5.3
output:
NO

如果理解为涂色点可以不联通只要最多的联通数量等于给的线索那么输出会是

YES
3 3
3#2#3
##.##
5#7#5
#####
3.5.3

由于要求连续，所以有一个很重要的结论：
如果合法那么最外圈（除去数字的最外圈）一定全是’#’，原因很简单因为要求连续，像上面的例子给出的就是不合法的，只有最外圈全是’#’才能保证数字的最外圈每个阴影都是连续的。
正难则反，假设现在全部都是阴影，如果能去掉一些阴影来满足条件那么就是合法的。将这个想象成一张图，没有’#’的相邻两个数字，即这两个数字周围允许有空白（即不是3,5,8）就是存在一条边，相邻才会有一条边，并且一定不会存在一行像3.4.5.4.3这样隔一列的合法情况，那也就是说奇数行和偶数行可以被两两匹配，就很容易联想到跑一次二分图的最大匹配，一边的点集全是奇数行列，一边的点集全是偶数行列，如果做得到完全匹配那么就是一种合法情况。然后再结合上面的结论可以枚举出二分图的边集：如果都是在最外层的或者都是在里面的并且相邻那么这两个点之间就存在一条边，跑一遍匈牙利算法如果是完全匹配那么就是合法的。
需要注意的是二分图不一定的两个集合不是必须按照点来划分，这道题只要能够正确描述点与点之间的关系并且可以判断是不是完全匹配就可以。代码中是将点的集合重新分配一个编号，将这个编号与编号之间的关系作为一条边建二分图，而且因为是用编号映射点，所以：
1.下标是从0开始的，与正常的模板相比，数组的初始化一定要初始化成-1，如果没有初始化是0那么就是说明这个下标与第0个点匹配，这样就会出错，并且条件的判断也要从!=0变成!=-1
2.输出的时候要考虑映射关系
用邻接表存储编号的数组一定要开到1500左右，因为n和m最大都是50，两两组合有50*49/2，所以要开的足够大才不会re

#include <bits/stdc++.h>

#define N 1505
using namespace std;

typedef pair<int, int> PII;
vector<int> edge[N];
int n, m, v[N];
bool st[N];
vector<PII> vl, vr;

bool find(int x) {
    st[x] = true;
    for (auto y: edge[x]) {
        if (v[y] == -1 || (!st[v[y]] && find(v[y]))) {
            v[y] = x;
            return true;
        }
    }
    return false;
}

int match(int num) {
    int ans = 0;
    memset(v, -1, sizeof v);
    for (int i = 0; i < num; ++i) {
        memset(st, false, sizeof st);
        if (find(i)) ++ans;
    }
    return ans;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<string> mat(2 * n - 1);
    for (auto &s: mat) {
        cin >> s;
        for (auto &c: s)
            if (c == '.') c = '#';
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            char t = mat[2 * i][2 * j];
            if (t == '3' || t == '5' || t == '8')continue;
            if ((i + j) % 2 == 0)vl.emplace_back(i, j);
            else vr.emplace_back(i, j);
        }
    int v1 = (int) vl.size(), v2 = (int) vr.size();
    if (v1 != v2) return cout << "NO\n", 0;
    for (int i = 0; i < v1; ++i) {
        auto [x1, y1] = vl[i];
        for (int j = 0; j < v2; ++j) {
            auto [x2, y2] = vr[j];
            int dist = abs(x1 - x2) + abs(y1 - y2);
            bool isBoundary = (x1 == 0 && x2 == 0) || (x1 == n - 1 && x2 == n - 1) ||
                              (y1 == 0 && y2 == 0) || (y1 == m - 1 && y2 == m - 1);
            bool isIntern = mat[2 * x1][2 * y1] == '7' && mat[2 * x2][2 * y2] == '7';
            if (dist == 1 && (isBoundary || isIntern)) edge[i].push_back(j);
        }
    }
    if (match(v1) != v1) cout << "NO\n";
    else {
        cout << "YES\n";
        for (int i = 0; i < v2; ++i) {
            auto [x2, y2] = vr[i];
            int j = v[i];
            auto [x1, y1] = vl[j];
            mat[x1 + x2][y1 + y2] = '.';
        }
        for (auto &s: mat) cout << s << '\n';
    }
    return 0;
}
/*
struct MBM {
    int L;
    vector<int> match, seen;
    vector<vector<int> > g;

    MBM(int L, int R) : L(L), match(R), seen(R), g(L) {};

    void add_edge(int l, int r) { g[l].push_back(r); };

    bool dfs(int u) {
        return any_of(g[u].begin(), g[u].end(), [&](int v) {
            if (seen[v]++ == 0 && (match[v] == -1 || dfs(match[v]))) {
                match[v] = u;
                return true;
            }
            return false;
        });
    }

    int max_matching() {
        int ans = 0;
        fill(match.begin(), match.end(), -1);
        for (int u = 0; u < L; ++u) {
            fill(seen.begin(), seen.end(), 0); 
            ans += dfs(u);
        }
        return ans;
    }
};
*/

可以像注释里的代码一样定义一个结构体，将所有的初始化，数组长度在结构体初始化的时候申请对应的大小就可以保证空间也不会被浪费。
其实还是很套路的一道题，如果题目做多了就会发现棋盘矩阵其实天生的适合划分成两个点集，这些题基本上程序的框架是一样的，的比如像这样黑白染色：

行号加列号是偶数就染黑，奇数就染白，就可以变成黑格是一类点，白格是一类点，黑白相邻格子之间连上一条边，就可以解决这道棋盘覆盖问题：

I. Equation Discovering

翻译：

Mika教授是一位计算机科学研究人员，他提出了以下问题:给定n对(x,y)，其中1≤n≤20,我们如何找到适用于所有对的控制方程y=f(x)?换句话说，他试图确定一个方程，该方程涉及二元运算符(+，-，x，÷)、一元运算符(sin，cos)、符号x和适用于所有给定对的括号，例如y=xx÷sin(x)或y=x(x+x÷x)。

为了生成所有有效的方程，我们定义了一个上下文无关语法，如下所示:

1.起始符号为S。

2.S→S+S | S-S

3.S→SxS | S+S

4.S→sin(S) | cos(S)

5.S→(S) l x

然而，为了防止过拟合，我们将方程的复杂度限制为小于或等于9，其中复杂度定义为二元运算符(+，-，x，÷)数量的两倍加上方程中一元运算符(sin，cos)数量的一倍。例如，方程x+(x+xx)的复杂度为6，而xsin()的复杂程度为3。只有复杂度小于或等于9的方程才会被认为是正确的。

输入

第一行包含一个整数n(1≤n≤20)，表示要拟合的(x，y)对的数量。以下n行，每行两个实数r，y(zl，<103)，小数点后正好有六位数字，表示(x，y)对。

x的值保证是准确的，我们使用一些有效的方程来生成y的值，然后将其四舍五入到六位数。

输出

输出只有一行表达式f，由’+’、-’、*’(对于x)、/’(对于÷)、’sin’、’cos’、’x’、(’和)’组成。

如果您的答案满足以下条件，则视为正确:

1.表达式f是使用前面描述的上下文无关语法生成的，并且根据该语法是有效的。

2表达式f的复杂度不超过9，并且长度不超过1000个字符。

3.对于每个(z，y)对，f(z)和g之间的绝对或相对误差不大于10

3。即≤10-3

4.在计算除法运算时，被除数的绝对值必须不小于0.01。

留坑待填

赛后总结

…没去颁奖现场也没找到获奖率的通知，文件里面只写了这些：
本届竞赛按本科组、专科组分别进行评奖和设奖，根据每队答题数量及解题时长进行排名。为与国际竞赛获奖名称接轨，特设置奖项如下：
颁发金、银、铜奖（牌）：若干名；
颁发最佳女队奖（牌）：1名；要求获等级奖的参赛队中，应有3名女生组队，则有资格参评此奖项；
颁发顽强拼搏奖（牌）:1名；
要求竞赛中表现特别顽强的队伍，如提交某题次数最多、在比赛结束前最后成功通过一题的队伍等，都有可能获此奖项；
颁发高校优秀组织奖（牌）：若干名。
上述获奖比例按浙江省大学生科技竞赛委员会相关规定执行，奖牌颁发给参赛高校，获奖证书颁发给获奖师生本人。
如果按2014年的评奖规则：
本届竞赛按本科组、大专组分别进行评奖和设奖，根据每队解答竞赛题目的数目多少及解题程序算式所需时间长短进行排名。评定以下奖项：
特等奖：1队（可空缺），颁发奖杯、证书；
一等奖：8%参赛队，颁发金牌、证书；
二等奖：15%参赛队，颁发银牌、证书；
三等奖：25%参赛队，颁发铜牌、证书；
特别奖：最佳女队奖（获等级奖的参赛队中，应有3名女生组队，则有资格参评此奖项）、顽强拼搏奖（竞赛中表现特别顽强的队伍，如提交某题次数最多、在比赛结束前最后成功通过一题的队伍等，都有可能获此奖项）、最佳组织奖（颁发给积极参与竞赛的学校）若干，颁发奖牌。
优胜奖：未获等级奖和特别奖，但在比赛中至少成功解答一题的队。无证书。
成功参赛奖：未获上述奖项的参赛。无证书。

比赛时做了AEFM四道题，按照这个规则来看，如果要拿铜必须要做得快，银牌需要做出K题，做出G题稳银，再做出H题稳金。
这次打铁也属于是意料之中了，队友之间的配合明显不算好，可以看出做简单题花时间检查比直接交上去赌对而错了罚时的收益高，但是在做F题的时候仍然出现了一次罚时，这是因为我没有看清题目每次查询都会返回绝对值而不是差值，导致第一次在设计程序的时候总体思路就错了，最后我拍了几组错误的输出发现没错就提交罚时一次，在发现题目看错了又重新设计程序，就因为一个绝对值导致思路和之前的完全不一样，算上罚时总共浪费了一个多小时，导致来不及细想K题最后只解出了四道题，如果以现在补题时的能力来看，前面做的快，留出充足的时间是有可能写五道题拿银。但是金牌的话G题的难度过大不大可能在有限的时间内想出完全正确的贪心，H题更不可能联想到建模成二分图跑最大匹配(其实棋盘建模成二分图是比较套路的做法)
总的来说大一没有拿牌还是能力和比赛经验不够，练得太少做不到将想法写成程序，在补题的时候还只是第一次做这种dp，比赛时就更弱了，在写M题的时候写个sort的比较函数都要写半天，最后是一个队友用STL里面的pair加优先队列做出来的。并且英语也很重要，平时英文题也没有练过，比赛时三个人在做题的时候原本的想法是三个人分开看题，结果甚至查英文字典都看不懂题目，都是看哪题通过率高的没写就三个人一起翻译题目，这样做明显降低了读题速度，一直到比赛结束都没看K题以后的题目。并且F题题面都加粗了绝对值但是读完还是忘了…其实在英语题练多了后去打比赛，可以在做完签到题后英语好的两个人读题，一个人从前往后一个人从后往前，另一个在devc++上先打好缺省源顺便看看榜单里面哪一题做的人多，这样可以节省不少时间。

比赛的排名规则

首先按解题数量排序，每道题权值一样，解题数量越多的排在前面，题数一样多的队伍按时间排（表中的score），时间的具体计算是：每道题第一次ac的时间（单位为分钟）的总和加上已ac的题目中先前提交wa的次数20。像我们队解出AEMF的时间分别是比赛开始后的10，49，95，210，其中F题罚时一次，那么总时间就是10+49+95+210+201 = 384,所以四题里用时比我们长的都排在后面

终榜