比赛链接：https://qoj.ac/contest/1864
队友秒了 F,A,J,I ，我看了 L ，但是当时觉得比较难写就往后拖了下，40 min 过了 L 。（这一场前期我怎么这么摸鱼）
然后队友秒了 K ，我秒了 C ，队友秒了 D ，我秒了 H ，此时三个小时过去了，然后我会了 M ，此时过去三个半小时。
G 从比赛开始队长就在想结论，但是我已知没听懂他那个玩意要怎么量化，后面终于听懂了，写了过了。
后面进入开摆环节，一个小时什么都不会，E 搁那阿巴了半天用正方形去拟合，后面队长问了句如果题目就是正方形该怎么做，我说了句扫描线，然后队长神经突然通了，然后大喊，没错，就是扫描线，遂讲述具体做法。非常好做法，让我这个想了一小时正方形拟合的人像个小丑 🤡 ，这个做法之前有见过，但是确实想不出来，菜就多练了属于是。
这场比赛不能说难，但是打的也确实不行，看看隔壁的夏日影吧，感觉就是每道题目都卡的比他们久，然后就似了。
看一下榜，woc，好像是我在犯罪，C 写了一个半小时，呃呃呃，那没事了，不过当时确实没反应过来怎么切三角形，有点唐，代码水平有待提高，至于别的，D 题他们比我们早过一个小时，所以很长一段时间我们比他们少题，然后后面就一直在追夏日影的进度了。
你要说有什么问题，我感觉就是我代码水平急需提高以及大伙菜就多练了，我们硬实力很多时候确实有点弱，尤其是大伙没睡醒的时候，怎么队长天天疲劳作战。
J
简要题意：给定有向图，找一种顶点排列，使得至少一半的边满足：如果边是 $(u, v)$ ，则 $u$ 在 $v$ 之前。输出任意一种排列，或判断无解。
做法
一个做法是随机，由于期望是 $\frac{m}{2}$ 的，所以感觉上很容易随出一组解，事实也确实，排列和排列的 reverse 一定有一个是合法解，所以每次随机成功的概率是 $\frac{1}{2}$ ，当然也可以直接 reverse 。
还有一种做法是每次找出度大于等于入度的点，把他删了，也是一个做法。
时间复杂度：$O(n)/O(n\log{n})$ 。
L
tag：状压dp
简要题意：给定两个字符串 $s$ 和 $t$，它们的最长公共子串为 $w$，且 $w$ 的长度不超过 3。求有多少对长度分别为 $n$ 和 $m$ 的二进制字符串 $s$ 和 $t$，使得它们的最长公共子串为 $w$，结果对 $998244353$ 取模。
做法
考虑连续三个字母构成的图，显然只有至多 $2^4$ 种转移，
所以每个字符串的状态可以用 $2^{16}$ 来描述，当然，也可以用连续四个字母构成的图来看，这样关心的是点的数量而不是转移。然后要求两个字符串的状态不交，随便状压处理一下就行了。
时间复杂度：$O(2^{2^{k+1}}*(n + m))$
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
| #include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 1e2 + 5;
const int L = (1 << 3);
const int V = (1 << 16);
int n, m, k, goal;
char st[N];
LL dp[2][L][V], tmp[2][L][V], f1[V], f2[V];
void upd(LL &x, LL y){x = (x + y % mod + mod) % mod;}
int main(){
cin >> n >> m >> k;
cin >> st;
for(int i = 0; i < k; i++) goal = (goal << 1) | (st[i] - '0');
int c0 = (1 << k), c1 = (1 << (k + 1));
for(int i = 0; i < c0; i++){
upd(dp[i == goal][i][0], 1ll);
}
for(int T = k; T <= max(n, m); T++){
if(T == n){
for(int j = 0; j < c0; j++){
for(int s = 0; s < (1 << c1); s++){
upd(f1[s], dp[1][j][s]);
}
}
}
if(T == m){
for(int j = 0; j < c0; j++){
for(int s = 0; s < (1 << c1); s++){
upd(f2[s], dp[1][j][s]);
}
}
}
memcpy(tmp, dp, sizeof(tmp));
memset(dp, 0, sizeof(dp));
for(int o = 0; o <= 1; o++){
for(int j = 0; j < c0; j++){
for(int s = 0; s < (1 << c1); s++){
for(int t = 0; t <= 1; t++){
int x = j | (t << k);
int ss = s | (1 << x);
int y = x >> 1;
upd(dp[o | (y == goal)][y][ss], tmp[o][j][s]);
}
}
}
}
}
for(int i = 0; i < c1; i++){
for(int j = 0; j < (1 << c1); j++){
if(!((j >> i) & 1)) upd(f2[j | (1 << i)], f2[j]);
}
}
LL ans = 0ll;
for(int i = 0; i < (1 << c1); i++) upd(ans, f1[i] * f2[((1 << c1) - 1) ^ i]);
cout << ans << "\n";
return 0;
}
|
K
简要题意：Kevin 发明了一个特殊的键盘，每个键都有一个字母序列。每次按下键 $i$，该键的第一个字母会被输入，然后该字母会移动到序列的末尾。给定每个键的初始字母序列，求最短的不可通过这种键盘输入的由前 $e$ 个小写字母组成的字符串。
做法
队友做出来的，而且只要听到结论就知道怎么做了，所以并没有心路历程。
做法非常简单，结果一定可以是同一个字母的形式，证明非常简单，考虑结果串的一个终止局面，一定是字符串末尾有个 $x$ 且现在没有键位能输出 $x$ ，则前面换成 $x$ 一定会在当前状态甚至更前面的状态停下来，所以答案不会变劣，证毕。
然后应该就随便做了。
要说怎么想出来的，一种可能的想法是，考虑什么时候会停下来，是不是当前局面没有键位能输出 $x$ ，那么再放一个 $x$ 就结束了，所以从结果的角度反推过程，你前面如果放非 $x$ 的字母只有可能在答案变劣的同时增加更多输出 $x$ 的可能性，有了这个想法后就很有可能想到前面那个结论，而前面那个结论的正确性是几乎显然的，所以就做完了。虽然我并没有做这道题目，但是我觉得这个思考过程比较自然，也很有可能就是如果我做出这道题目的心路历程。
C
tag：dp ，矩阵快速幂
简要题意：给定一个 $n$ 边的正多边形蛋糕，主席 capybara 在上面做了 $m$ 条不交叉的对角线切割，分成 $m+1$ 块。要求计算将蛋糕的每个角落涂上 $k$ 种颜色的方案数，使得相邻的角落颜色不同。相邻的角落是指：在原始蛋糕中相邻的角落，或者是同一条切割的两个端点。结果对 $998244353$ 取模。
做法
注意到，对于多边形边上的一个小三角形，其中间的点的唯一限制就是三角形两端的异色点，而且中间的点对三角形外的点没有限制，所以不妨假设两端的颜色为 $1,2$ ，把中间涂上色后直接删掉就行了。
一个问题是如何去割这个三角形，当时铸币了，刚开始写代码的时候以为还要用数据结构去维护，后面发现这个数据结构可以换成栈，分析了一下这里栈实际是在干什么后，总算恍然大悟，明白了这种多边形切三角形的一个好的处理方法：
把多边形理解成一个 $n$ 个点以及一个覆盖 $[1,n]$ 的区间，然后每条边就是覆盖了一个区间，然后用栈去维护这个覆盖关系就行了。
至于中间的涂色方案数要怎么处理，直接用矩阵快速幂就行了。
时间复杂度：$O(n\log{V})$ 。
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
| #include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef array<int, 3> A3;
const LL mod = 998244353;
const int N = 2e5 + 5;
struct Matrix{
int n, m;
LL a[3][3];
Matrix(){memset(a, 0, sizeof(a)); n = m = 0;}
LL* operator[](int x){return a[x];}
};
Matrix operator*(Matrix x, Matrix y){
assert(x.m == y.n);
Matrix z;
z.n = x.n;
z.m = y.m;
for(int i = 1; i <= z.n; i++){
for(int j = 1; j <= z.m; j++){
for(int k = 1; k <= x.m; k++){
z[i][j] = (z[i][j] + x[i][k] * y[k][j]) % mod;
}
}
}
return z;
}
Matrix unit(int n){
Matrix a; a.n = a.m = n;
for(int i = 1; i <= n; i++) a[i][i] = 1;
return a;
}
Matrix ksm(Matrix x, LL y){
assert(x.n == x.m);
Matrix ans = unit(x.n);
while(y){
if(y & 1) ans = ans * x;
x = x * x; y >>= 1;
}
return ans;
}
int n, m, k;
Matrix trans;
void init(){
trans.n = trans.m = 2;
trans[1][1] = k - 2; trans[1][2] = 1ll;
trans[2][1] = k - 1; trans[2][2] = 0ll;
}
LL solve(int c){
assert(c >= 3);
Matrix f; f.n = 1; f.m = 2;
f[1][1] = k - 2; f[1][2] = 1ll;
f = f * ksm(trans, c - 3);
return f[1][1];
}
bool in(A3 x, PII y){return y.first >= x[0] && y.second <= x[1];}
PII a[N];
int main(){
int T;
cin >> T;
while(T--){
cin >> n >> m >> k;
init();
for(int i = 1; i <= m; i++){
cin >> a[i].first >> a[i].second;
assert(a[i].first + 1 < a[i].second);
}
sort(a + 1, a + m + 1, [](PII x, PII y){return x.first == y.first ? x.second > y.second : x.first < y.first;});
vector<A3> stk;
stk.push_back({1, n, 0});
LL ans = 1ll;
for(int i = 1; i <= m; i++){
while(!in(stk.back(), a[i])){
auto [l, r, c] = stk.back(); stk.pop_back();
ans = ans * solve(r - l + 1 - c) % mod;
assert(!stk.empty());
stk.back()[2] += r - l - 1;
}
stk.push_back({a[i].first, a[i].second, 0});
}
while(!stk.empty()){
auto [l, r, c] = stk.back(); stk.pop_back();
ans = ans * solve(r - l + 1 - c) % mod;
if(!stk.empty()){
stk.back()[2] += r - l - 1;
}
}
cout << ans * k % mod * (k - 1) % mod << "\n";
}
return 0;
}
|
D
简要题意：给定一个 $n$ 台服务器构成的环形网络，每台服务器的计算负载由非负整数 $a_i$ 表示，Devin 希望通过脚本使每台服务器的负载相等，并且尽量使负载值最大化。每次在服务器 $i$ 上运行脚本时，该服务器的负载减少 2 单位，同时前一个服务器的负载（如果存在）也会减少 1 单位（过程中所有数字与 $0$ 取 max ）。如果 $i = 1$，则前一个服务器是服务器 $n$（因为是环形）。Devin 可以多次运行脚本，求最大可能的相等负载值。
做法
队友想出来的，做法我个人感觉很神。
一个显然的事情是，我们只需要关心所有数字 $>0$ 的终局，因为只要有数字为 $0$ ，结局就一定为 $0$ ，而 $>0$ 的终局显然过程中不会取到 max ，所以我们就不用考虑 max 了，而这更意味着我们可以列方程了。
首先队友观察到如果在每个位置操作一次，就会全部减 $3$ ，所以这意味着，如果列 $n$ 个三元方程，秩是不够的，我们需要多加一维。
一个想法就是枚举终局状态，但是我们不可能枚举值域。而根据上面的性质，在 $\mod{3}$ 的意义下，可以二分。现在，在确定终局状态的情况下，我们可以列出 $n$ 个二元方程，用主元法可以轻松知道这个方程满秩，有唯一解。
但还有一个问题，这个方程主元法过程中的值域特别大，怎么办，注意到系数一定是 $2^k-1$ 的形式，而且解也是 $\le 5*10^8$ 的，所以可以在模意义下处理，只要 $2$ 的阶数够大，就不用担心除 $0$ 的问题，最后 check 一下解就行了。
这样就做完了，但是队友还有想法。
可以不用二分，因为解唯一，所以差 $3$ 的解可以通过全体加减 $1$ 得到，所以只需要跑出终局为 $0,1,2$ 的解，在合法后一直升到某个操作次数为 $0$ 就行了。
时间复杂度：$O(n)$
总结：我也想了这题，但我的思路偏了，我是往找性质的角度出发的，就是去思考是否有操作是必做的，在没想到后又差分，变成 -1 -1 +2 ，然后还是没找到性质就弃了。完全没有往方程的角度上想。
按照之前赛后总结说的思考本质的思考方式来想，这种题我目前认为，考虑方程是比较本质的想法。虽然从性质的角度思考并非错误，但是我认为，优先思考更为本质的方程解法才是正确的选择，更别提我这种想都没想的情况，找性质应该是在思考方程无果后才应该考虑的事情。
这道题目我认为，只要从方程的角度考虑，二分做法应该是好想的，但是不用二分的做法确实需要点思维，感觉得对方程的熟练度比较高才能比较自然的想出这个做法。
总结一下，如果方程满秩，就可以考虑这题做法的类似物，如果不满秩，就存在变形方程的方法，这个时候就可以考虑通过这个变形，去找到一定存在的操作，然后递归下去。
H
简要题意：这是一个改进版的汉诺塔问题。给定 3 根杆和 $n$ 个盘子，盘子的大小按从下到上的顺序递减。有效的操作是将最小的盘子从一根杆移到另一根杆，且不能将大盘子放到小盘子上。在此变种中，盘子只能在相邻的两根杆之间移动，即可以在杆 1 和杆 2 之间、杆 2 和杆 3 之间移动，但不能在杆 1 和杆 3 之间移动。目标是从初始配置通过最少的移动次数，转移到给定的目标配置。求最少的移动次数，并输出结果对 $998244353$ 取模。
做法
严重怀疑致敬 WF2023 。
最优移动方式是显然的，每次找到不在位置的最大的盘子，移动过去就行了，至于为什么是最小的，我的回答是，你可以发现每一步都是必经之路，且每一步都是不一样的，所以这自然是最小的。
然后做法就是维护一个变量 $x$ 表示 $1\sim x$ 层的盘子都在一个柱子上，然后用这个维护一下过程就行了。
时间复杂度：$O(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
91
92
93
94
95
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 1e5 + 5;
LL f[N][3][3];
int n, a[N], b[N];
int tog, pos;
LL ans = 0ll;
void upd(LL &x, LL y){x = (x + y % mod + mod) % mod;}
int sgn(int x){return x > 0 ? 1 : (x == 0 ? 0 : -1);}
void merge(int dep, int goal){
if(!dep) return ;
if(tog == dep){
assert(pos != -1);
upd(ans, f[tog][pos][dep]);
pos = dep;
return ;
}
if(a[dep] == goal){
merge(dep - 1, goal);
assert(!tog || pos == goal);
}
else if(abs(goal - a[dep]) == 1){
int x = 3 - goal - a[dep];
merge(dep - 1, x);
assert(!tog || pos == x);
upd(ans, 1ll + f[dep - 1][x][goal]);
}
else{
merge(dep - 1, goal);
assert(!tog || pos == goal);
upd(ans, 2ll + f[dep - 1][0][2] * 2);
}
tog = dep; pos = goal;
}
void solve(int type){
tog = 0; pos = -1;
int p = n;
while(p && a[p] == b[p]) p--;
if(p){
if(type) merge(p, b[p]);
else{
if(abs(a[p] - b[p]) == 1){
int x = 3 - a[p] - b[p];
merge(p - 1, x);
upd(ans, 1ll);
}
else{
merge(p - 1, b[p]);
upd(ans, 2ll + f[p - 1][0][2]);
pos = a[p];
}
for(int i = 1; i <= n; i++){
swap(a[i], b[i]);
if(i <= tog) b[i] = pos;
else b[i] = a[i];
}
solve(1);
}
}
}
int main(){
int T;
cin >> T;
while(T--){
ans = 0ll;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
if(j == k) f[i][j][k] = 0ll;
else if(abs(j - k) == 1){
int w = 3 - j - k;
f[i][j][k] = (f[i - 1][j][w] + 1 + f[i - 1][w][k]) % mod;
}
else{
assert(abs(j - k) == 2);
f[i][j][k] = (f[i - 1][0][2] * 3 + 2) % mod;
}
}
}
}
for(int i = 1; i <= n; i++){
cin >> a[i]; a[i]--;
}
for(int i = 1; i <= n; i++){
cin >> b[i]; b[i]--;
}
solve(0);
cout << ans << "\n";
}
return 0;
}
|
做法 2
学习了一下夏日影的做法，短一些。
他们观察到了两个性质。
性质 1 ：当有完整一堆 $1,2,…,n$ 连续移动两个柱子时，则一定会在中间的柱子出现完整的一柱。
性质 2 ： 完整一堆移动一个柱子（即无论 $2\to 3$ 还是 $3\to 2$ ） 的步数都是一样的。
证明都是简单的，递归证明一下就行了。
在知道这两个结论后直接讨论都可以写出比较短的代码，在此就不再赘述了。
感想：不懂怎么想出上面两个结论，感觉这两个结论对我而言都是觉得有没有道理都有可能，编不出什么自然的想出这两个结论的思考过程。不过我那个做法也并不是很难写，所以赛场上想不出来这两个结论其实问题不大，只是如果能想到这两个性质就更好了。
M
tag：dp
简要题意：在修改版的 Préférence 游戏中，给定一个包含 $A$ 个花色和 $B$ 个牌面值的牌组。每个花色的牌面值从 $1$ 到 $B$，并且每个玩家有 $n$ 张牌。我们的目标是通过选择并添加 $x$ 张尚未拥有的牌，然后从 $n + x$ 张牌中选择并丢弃 $x$ 张，剩下的 $n$ 张牌应满足一种条件：对于每个花色，将该花色的牌按牌面值从小到大排列后，满足每张牌的牌面值 $b_i$ 满足 $b_i \geq 2i - 1$，其中 $i$ 是该花色中这张牌的位置（从小到大排序）。如果某个花色没有牌，则该条件自动满足。要求找出最小的 $x$，使得通过这样的选择和丢弃操作后，你可以得到一个符合“Guaranteed Misère”条件的手牌。
做法
一个显然的事情是，每种花色的牌，每次移除一定会移除最大的，所以每种花色会有若干个二元组的贡献表示：这堆牌删了多少张牌，以及还需要多少张牌补充进来。
然后发现关心两个值：删了多少张牌，需要删多少张牌。只要最后删的牌的数量大于等于需要删的就合法，显然让需要删的尽可能小，跑个 dp 就行了。
不过我赛时维护的是：删减需要删，然后最小化删牌数。
时间复杂度：$O(n^2)$
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
| #include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
const int INF = 1e9;
const int N = 5e3 + 5;
const int M = 1e4 + 5;
int dp[M], tmp[M];
map<int, vector<int> > m;
int n, A, B;
int main(){
int T;
cin >> T;
while(T--){
m.clear();
cin >> n >> A >> B;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
m[x].push_back(y);
}
for(int i = 0; i <= n + n; i++) dp[i] = INF;
dp[n] = 0;
for(auto [t, a] : m){
sort(a.begin(), a.end());
swap(tmp, dp);
for(int i = 0; i <= n + n; i++) dp[i] = INF;
for(int j = 0; j <= n + n; j++){
if(tmp[j] == INF) continue;
dp[j + a.size()] = min(tmp[j] + (int)a.size(), dp[j + a.size()]);
}
int now = 0;
for(int i = 0; i < a.size(); i++){
now++;
now += max((a[i] - (2 * now - 1) + 1) / 2, 0);
int add = now - i - 1;
int del = a.size() - i - 1;
for(int j = 0; j <= n + n; j++){
if(tmp[j] == INF || j + del - add < 0) continue;
dp[j + del - add] = min(tmp[j] + del, dp[j + del - add]);
}
}
}
int ans = INF;
for(int i = n; i <= n + n; i++) ans = min(ans, dp[i]);
cout << ans << "\n";
}
return 0;
}
|
夏日影的做法好像是用了某种奇怪的近似然后迭代五十轮，但是写这道题题解的时候距离模拟赛已经很多天了，具体做法给忘了，有点呃呃了。
G
tag：博弈
简要题意：两名玩家在一个无限向右延伸的棋盘上玩游戏，棋盘分为若干个格子，每个格子内可以有红色棋子（玩家 1 的棋子）或蓝色棋子（玩家 2 的棋子），每个玩家轮流操作。在每一轮，玩家可以选择跳过回合，或者将一颗自己的棋子移动到相邻的格子。如果相邻格子没有对方的棋子，移动即可完成；如果相邻格子内有对方的棋子，双方各移除一颗棋子。游戏的目标是判断，在双方都执行最优策略下，哪一方会获胜，或者是否会进入平局。
如果两名玩家的棋子都用完，则游戏以平局结束。如果只有一名玩家的棋子用完，则这名玩家输了，另一名玩家获胜。如果经过 $10^{100}$ 回合游戏还未结束，则强制结束并判定为平局。
做法
直接说结论，后面再说怎么想的：
如果双方棋子数量相同，则一定平局。
先手的棋子少于后手，设从右往左先后手的棋子坐标为 $x_i,y_i$ ，如果 $\exists j:\sum\limits_{i=1}^j x_i-y_i>0$ ，则平局，否则后手胜利。
反之：如果 $\exists j:\sum\limits_{i=1}^j x_i-y_i<-1$ ，则平局，否则先手必胜。
证明不算困难，这里不再赘述。
时间复杂度：$O(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
| #include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 5;
int n, fl;
void print(int type){
if(type == 1) cout << "First " << fl << " +\n";
else if(type == 0) cout << "Draw " << fl << " +\n";
else cout << "Second\n";
}
void solve(int type, vector<PII> &f, vector<PII> &s){
LL val = 0ll;
while(!f.empty()){
assert(!s.empty());
auto [x1, c1] = f.back();
auto [x2, c2] = s.back();
int c = min(c1, c2);
val += 1ll * (x1 - x2) * c;
f.back().second -= c;
if(f.back().second == 0) f.pop_back();
s.back().second -= c;
if(s.back().second == 0) s.pop_back();
if(val > 0){
print(0);
return ;
}
}
if(!type) print(-1);
else print(1);
}
int main(){
int T;
cin >> T;
while(T--){
cin >> n;
vector<PII> first, second;
LL c1 = 0ll, c2 = 0ll;
for(int i = 1; i <= n; i++){
int x, c;
char tmp[10];
cin >> x >> c >> tmp;
if(tmp[0] == 'R'){
first.push_back({x, c});
c1 += c;
}
else if(tmp[0] == 'B'){
second.push_back({x, c});
c2 += c;
}
}
fl = first.back().first;
if(c1 == c2) print(0);
else if(c1 < c2){
solve(0, first, second);
}
else{
auto [x, c] = first.back();
if(c == 1) first.pop_back();
else first.back().second--;
first.push_back({x + 1, 1});
swap(first, second);
solve(1, first, second);
}
}
return 0;
}
|
怎么想到的：首先这个结论大体上已经被队长说出来了，只不过他并没有用这个语言表达出来，大概就是说找个分隔点，然后计算步数差之类的。
然后我按着他的说法去想，思考他说的道理：首先只考虑最右边一个棋子的情况，然后不断给双方加入次右边的棋子，如此往复，然后讨论每一种情况下双方可能的最优策略，然后突然发现好像在所讨论的最优策略下，有一个量一直没有改变，就是双方对应棋子的距离和，即 $\sum\limits x_{i}-y_i$ ，无论 $x_i,y_i$ 的大小关系如何（当时是发现这些棋子好像具有某种隐形的匹配关系，接下来就观察到貌似和匹配点的距离有关，再接下来就观察到这个式子了），在观察到这个式子后，感觉这个式子就非常的正确，而且感觉证明也自然，不算困难，写代码也很快，然后写了就过了。
总结一下怎么发现的，就是在大量手模的经验积累下，观察到的，无它，唯手熟耳。
E
tag：扫描线
简要题意：给定平面上的 $n$ 个圆，每两个圆最多有一个交点，圆与圆之间可能相互接触，或一个圆在另一个圆内，但不可以有两个交点或重合。我们需要找到满足“8-shaped”条件的圆对，即两个圆接触且彼此不包含对方。换句话说，两个圆如果接触且其中一个不完全包含在另一个内部，就算是一个有效的 8-shaped 图形。
做法
考虑扫描线，可以发现，由于题目的限制，所以在扫描线过程中，线截每个圆得到的区间所构成的树结构是不变的，利用这个数据结构，可以得到圆之间所有的相交点，然后再计数一下每个点有多少个圆经过，以及是以什么朝向经过的，然后计数就行了。
时间复杂度：$O(n\log{n})$
总结：这个做法倒是十分经典，一个很典的问题就是，已知线段交点不超过 $k$ 个，要求你全部求出来，也可以用扫描线来做，时间复杂度：$O((n+k)\log{n})$ 。感觉这个做法确实很难自然想出来，至少以我现在的水平来看，我感觉这个做法是想到就想到了，想不到就很难通过一些线索自然的想出来，目前只能当成经典模型记下来了。
B
tag：网格图
简要题意：Barrett 发现了一个古老的迷宫，迷宫是一个 $n \times m$ 的网格，其中有些单元格是空的，有些是被阻挡的。可以通过相邻的空单元格走动（上下左右）。其中有两个空单元格分别是入口和出口，可以通过走动从入口到达出口。Barrett 想在迷宫中建一堵墙，阻止出口从入口处到达，墙应该是连续的并且只能是水平或垂直的，且长度为 $k$。墙不能包含入口、出口或已被阻挡的单元格。
你的任务是帮助 Barrett 找到最短的墙长，使得入口无法到达出口。
做法
首先，我们需要知道这玩意是否有解，这是简单的，把所有极长的横段作为点建一棵树，然后求割点，竖段同理。
这样我们就知道，哪些横段和竖段的子区间能够作为答案。
于是一个自然的想法是，我们每次拿出一个可能成为答案的段，在与长度相关的复杂度内处理出这个段的最优答案，这样就解决了这个问题。
显然，我们需要得到这个段的一些信息，一个自然的想法是：哪些格子能够在不经过这个横段的情况下，从起点到达/从终点到达，以及这个段自己内部的点，能否在不经过能到达起点或者终点的格子到达这个段另外一个内部点。
想到这个点的一个启发是，考虑这个段对应的树：
可以看到，这三种颜色的路径被这个点切割，而其中每一种颜色上的点都具有一定程度上的类似，自然会考虑这三种路径就是我们需要的三种不同的信息。
而且，不难发现，处理出所有段的信息的总时间复杂度是 $O(nm)$ 的。
现在的问题是，知道这三种信息就够了吗，现在来讨论一下。
不妨设 $s$ 能到达的段上格子为 $s$ 格，$t$ 同理。
所以一个自然的想法是，如果子段覆盖了所有的 $s$ 格或者 $t$ 格，则显然成功分割。
如果没有覆盖，则显然一段里面有 $s$ 格，另外一段里面有 $t$ 格，所以一个问题就是，一端的 $s$ 格能否通过中间桥梁到达 $t$ 格。
然后就是手动模拟一下，可以发现，对于一个内部到内部的路径，其连接了段上的点集 $S$ ，我们实际上只关心 $S$ 中两端的点，因为其余点要么已经被盖住了，要么可以直接从段上到达。
一个例子：
浅蓝色和蓝色都是这个路径联通的点集，但实际上我们只关心其连接了两个蓝色点。
所以，问题转化为，段上有一些连接两个点的边，现在盖住了中间一段点，能否通过左边的点到达右边的点，这自然是简单的。
但我们要求最优答案，所以现在要求出最短的段，使得一边只有 $s$ 格，另外一边只有 $t$ 格，且无法从一边到另外一边。
不考虑网格图的性质，一个自然的想法是：考虑移动 $l$ ，然后求出最好的 $r$ ，那么一条边 $[l,r]$ 会对中间的左端点添加一个右端点一定要 $\ge r$ 的一个限制，然后随便维护一下就行了。
我觉得写的好一点能做到 $O(nm)$ ，写差一点多个 $\log$ 也能过。
但是相当难写，所以我没有写。
至于考虑网格图的性质能否得到更好写的做法，我没有细想，毕竟已经能做到 $O(nm)$ 吗，而且考虑了以后，顶多多一些段上边的性质，顶多简化一下最后求右端点的部分，但是代码显然是复杂在处理是否有解和以及处理信息的部分，所以意义不大。更何况路径可以从这个段的一边走，也可以从另外一边走，所以边的性质也并没有很好，只能说确实不会很乱来。
总结：这道题目我除了在求解后，要考虑段上讨论的步骤是看题解的，其余都是在花了一些时间后想出来的，而且我认为讨论段这个步骤，是在知道怎么判合法后，迟早能够想出来的，只是当时没有花足够的时间。并非说这道题目不难，只是我认为，这道题目每个步骤都是比较自然的，并非不可想的题目。当然，这是比赛题，要做到在比赛时想出来，还要能写出来，确实是件极其困难的事情。
