2019-SWERC
参考博客：
https://www.cnblogs.com/heyuhhh/p/12941654.html
K 图上的路径存在问题(?) ->建反图进行染色
建反图，用rot的每个邻点去对整张图染色，被染色的点就意味着可以走到该颜色所代表的邻点。我们允许每个点最多被染色两次，这是因为rot的邻点一旦被超过一个点染色，那么就一定不合法；所以对图中每个点而言，如果其被染色次数大于等于2，那么其出边所对应的一系列点的更新也已经都完成，再次染色增加染色次数没有任何意义，并不会改变“不合法”这一性质。
需要注意的是为了避免在一些环路中绕死，每次应该判断一下当前点是否已经被当前颜色染过。
1const int maxn = 1e5 + 10;
2
3int n, m, rot;
4int head[maxn], top = 0;
5struct star{int to, next;};
6star edge[maxn << 1];
7
8void add(int u, int v){
9 edge[top].to = v;
10 edge[top].next = head[u];
11 head[u] = top++;
12}
13
14set<int> ans, res;
15vector<int> vec[maxn];
16
17void dfs(int now, int c){
18 int sze = (int)vec[now].size();
19 if(sze == 2) return ;
20 else if(sze == 1 && vec[now][0] == c) return ;
21 else{
22 vec[now].push_back(c);
23 for(int i = head[now]; ~i; i = edge[i].next){
24 if(edge[i].to == rot) continue;
25 dfs(edge[i].to, c);
26 }
27 }
28}
29
30int main(){
31 // Fastin;
32 clr(head, -1);
33 scanf("%d %d %d", &n, &m, &rot);
34 for(int i = 0; i < m; i++){
35 int u, v; scanf("%d %d", &u, &v);
36 add(v, u);
37 }
38 for(int i = head[rot]; ~i; i = edge[i].next){
39 ans.insert(edge[i].to);
40 dfs(edge[i].to, edge[i].to);
41 }
42
43 for(int x: ans) if((vec[x].size() == 1 && vec[x][0] == x)) res.insert(x);
44 printf("%d\n", (int)res.size());
45 fro(int x: res) printf("%d\n", x);
46
47 return 0;
48}A 二维价值dijstra(在一维路径权值和有上限的条件下求另一维的最短路)
复杂度大概是$EBlog{EB}$，E是图中边数，B是距离的上限。
简单地修改一下dijstra即可，但是写起来感觉又长又麻烦。
sro 场上1A的IGVA
1
2const int maxn = 1e5 + 10;
3
4struct POINT{
5 int x, y;
6 void read(){scanf("%d %d", &x, &y);}
7};
8POINT p[manx], s, t;
9int b, c[maxn], type, n;
10
11int head[maxn], top = 0;
12struct star{int from, to, next, dis, w, op;};
13star edge[maxn << 1];
14
15int getdis(int u, int v){
16 double rdis = (p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y);
17 int dis = max(0, (int)sqrt(rdis) - 2);
18 while(dis * dis < rdis) dis++;
19 return dis;
20}
21
22void add(int u, int v, int op){
23 //以op的方式连接一条路径
24 edge[top].from = u;
25 edge[top].to = v;
26 edge[top].op = op;
27 edge[top].next= head[u];
28 head[u] = top++;
29}
30void update(int i){
31 edge[i].dis = getdis(edge[i].from, edge[i].to);
32 edge[i].w = edge[i].dis * c[edge[i].op];
33}
34
35//dis[i][j]表示从s到达i点、距离花费为j时的最小碳排放量
36int dis[maxn][110];
37struct NODE{
38 int v, dis, w;
39 bool operator < (const NODE& b)const{
40 if(w != b.w) return w > b.w;
41 else return dis > b.dis;
42 }
43};
44priority_queue<NODE> pq;
45int dij(){
46 clr(dis, 0x3f);
47 for(int i = 0; i < n; i++){
48 int d = getdis(n, i); if(d > b) continue;
49 int w = d * c[0];
50 pq.push({i, d, w});
51 dis[i][d] = w;
52 }
53 while(!pq.empty()){
54 NODE temp = pq.top(); pq.pop();
55 int d = temp.dis, w = tmep.w, v = temp.v;
56 if(w > dis[v][d]) continue;
57 for(int i = head[v]; ~i; i = edge[i].next)
58 if(edge[i].dis + d <= b){
59 if(edge[i].w + w < dis[edge[i].to][d + edge[i].dis]){
60 dis[edge[i].to][d + edge[i].dis] = edge[i].w + w;
61 pq.push({edge[i].to, d + edge[i].dis, edge[i].w + w});
62 }
63 }
64 }
65 int ans = 0x3f3f3f3f;
66 for(int i = 0; i < n; i++) for(int d = 0; d <= b; d++){
67 int dd = getdis(i, n + 1); if(d + dd > b) break;
68 ans = min(ans, dis[i][d] + dd * c[0]);
69 }
70 if(getdis(n, n + 1) <= b) ans = min(ans, getdis(n, n + 1) * c[0]);
71 if(ans == 0x3f3f3f3f) ans = -1;
72 return ans;
73}
74
75
76int main(){
77 // Fastin;
78 clr(head, -1);
79 s.read(); t.read();
80 scnaf("%d", &b);
81 scnaf("%d", c);
82 scanf("%d", &type);
83 for(int i = 1; i <= type; i++) scnaf("%d", c + i);
84 scnaf("%d", &n);
85 for(int i = 0; i < n; i++){
86 p[i].read();
87 int l; scanf("%d", &l);
88 for(int j = 0; j < l; j++){
89 int v, op; scnaf("%d %d", &v, &op);
90 add(i, v, op); add(v, i, op);
91 }
92 }
93 fro(int i = 0; i < top; i++) update(i);
94 p[n] = s; p[n + 1] = t;
95
96 printf("%d\n", dij());
97 return 0;
98}J 卡特兰数计数问题
中序遍历一棵树，给出其深度序列，且满足树上某个节点的深度一定不低于其父节点的深度。
容易想到n^3的算法，但其实这种形式是卡特兰数的一个表达形式，即
$c_0c_{n-1} +c_1c_{n - 2} + c_2c_{n-3} +…+c_{n-1}c_0=c_n$
$c_0 = c_1=1$
在当前区间中，如果最小值为m，且其数量为k个，那么这些最小值一定构成树的上层框架，其种数就是c[k]；并且无论上层框架的结构如何，对于那些被划分开来的更深的区域，只需要递归地求解并且乘上其种数即可。
脑补了一个线段树的比较草的nlogn的算法，但是还没有实现就看到了一个On的处理办法
维护一个单调增的单调栈，栈中元素为<数值大小，出现次数>。每次当一个较小的数字进入后，就将那些太高的点弹栈，他们的“辖域”已经被切断，根据其个数即可更新结果。
1const int maxn = 1e6 + 10;
2const int M = 1000000007;
3
4int inv[maxn];
5int c[maxn];
6
7struct NODE{int num, times;};
8NODE node[maxn]; int top = 0;
9
10void push(int x){
11 if(top == 0){
12 node[top].times = 1;
13 node[top].num = x;
14 top++;
15 return;
16 }
17 assert(node[top - 1].num <= x);
18 if(node[top - 1].num < x){
19 node[top].num = x;
20 node[top].times = 1;
21 top++;
22 }
23 else node[top - 1].times++;
24}
25
26int main(){
27 // Fastin;
28 for(int i = 1; i < maxn; i++) inv[i] = (int)qp(i, M - 2, M);
29 c[0] = 1;
30 fro(itn i = 0; i < 1000005; i++){
31 c[i + 1] = (int)(1LL * c[i] * (4 * i + 2) % M * inv[i + 2] % M);
32 }
33
34 ll ans = 1;
35 int n; scnaf("%d", &n);
36 fro(int i = 0; i <= n; i++){
37 int x;
38 if(i != n) scanf("%d", &x); else x = -1;
39 if(top == 0 || node[top - 1].num <= x) push(x);
40 else{
41 while(top && node[top - 1].num > x){
42 ans *= c[node[top - 1].times];
43 ans %= M;
44 top--;
45 }
46 push(x);
47 }
48 }
49 printf("%lld\n", ans);
50 return 0;
51}H 分段打表
场上按道理应该是半推半就实则观看题解即可发现S序列具有周期性。
本来打算用hash找出循环地周期和起点，然而在1e8下直接慢到爆炸。
使用了IGVA教的序列快慢指针法即可On地找出循环节的信息。
起点和循环周题都在1e8的级别，考虑分段打表。
令$n = p*m + r$, m是自己选定的一个模数。只将整除于m的下标对应数的相关信息进行存储，查询时即可O(r)地查询。
然而一直TLE，才惊觉n可以等于0…..? orz
改了之后飞快过去了
1const ll M = 1ll << 40;
2
3ll fun(ll x){
4 ll ans = (x + (x >> 20) + 12345) % M;
5 return ans;
6}
7
8const int maxn = 1e6;
9const int mm = 5e5;
10ll a[10000] = {};
11ll b[10000] = {};
12ll cnta[10000] = {};
13ll cntb[10000] = {};
14ll cnt0 = 91029304;
15
16int main(){
17 // Fastin;
18 // Fastout;
19
20 // int n = 1e9;
21 // int p = 0, q = 1;
22 // ll r1 = 0x600dcafe, r2 = fun(r1);
23 // while(p <= n && q <= n && r1 != r2){
24 // p++; q += 2;
25 // r1 = fun(r1);
26 // r2 = fun(fun(r2));
27 // }
28 // if(p > n || q > n) puts("orz");
29 // else printf("%d %d: %lld\n", p, q, r1);
30 //364258417 728516835: 1613948613
31
32
33 // int cnt = 1;
34 // ll res = fun(1613948613);
35 // while(res != 1613948613){
36 // cnt++;
37 // res = fun(res);
38 // }
39 // printf("%lld\n", cnt);
40 //T: 182129209
41
42
43 // ll period = 182129209;
44 // ll start = 364258417 - period;
45 // ll r1 = 0x600dcafe;
46 // while(start--) r1 = fun(r1);
47 // start = 364258417 - period;
48 // ll r2 = 1613948613, end = 364258417;
49 // while(r1 != r2){
50 // start++; end++;
51 // r1 = fun(r1); r2 = fun(r2);
52 // }
53 // printf("%d %d: %lld\n", start, end, r1);
54 //350125310 532254519: 516914
55
56
57 ll start = 350125310, period = 182129209;
58
59 // ll p = 0, s = 0x600dcafe, cnt = 0;
60 // while(p < start){
61 // cnt += s % 2 == 0;
62 // if(p % mm == 0){
63 // a[p / mm] = s;
64 // cnta[p / mm] = cnt;
65 // }
66
67 // s = fun(s); p++;
68 // }
69 // ll cnt0 = 0;
70 // p -= start;
71 // while(p < period){
72 // cnt += s % 2 == 0;
73 // cnt0 += s % 2 == 0;
74 // if(p % mm == 0){
75 // b[p / mm] = s;
76 // cntb[p / mm] = cnt;
77 // }
78
79 // s = fun(s); p++;
80 // }
81 // // printf("%lld\n", cnt0);
82 // for(int i = 0; i < 10000; i++) printf("%lld, ", a[i]);
83 // printf("\n");
84 // for(int i = 0; i < 10000; i++) printf("%lld, ", b[i]);
85 // printf("\n");
86 // for(int i = 0; i < 10000; i++) printf("%lld, ", cnta[i]);
87 // printf("\n");
88 // for(int i = 0; i < 10000; i++) printf("%lld, ", cntb[i]);
89 // printf("\n");
90
91
92 ll n; scanf("%lld", &n);
93 if(n == 0){
94 puts("0"); return 0;
95 }
96 n--;
97 if(n < start){
98 ll res = a[n / mm];
99 ll ans = cnta[n / mm];
100 n %= mm;
101 while(n--){
102 res = fun(res);
103 ans += res % 2 == 0;
104 }
105 printf("%lld\n", ans);
106 }
107 else{
108 n -= start;
109 ll p = n / period;
110 n %= period;
111 ll res = b[n / mm];
112 ll ans = cntb[n / mm] + p * cnt0;
113 n %= mm;
114 while(n--){
115 res = fun(res);
116 ans += res % 2 == 0;
117 }
118 printf("%lld\n", ans);
119 }
120 return 0;
121}L 暴力 & normal game
为了补这题重新从源头上学习了一番SG定理相关，并花费了较多的时间学习misere game的解法？但是好像收效颇微，不如以题代学，最近打算开几套博弈论专题作为训练，以便于切实地掌握各种normal play的一般解法，并尝试学习misere game的相关知识。
在本题中，题目保证两块湿地间距不小于3，那么可以单独地处理每一块；而在每一块中，只有那些连续的空地才需要被划分为一个单独的normal play，不然可选状态过多，会TLE/MLE 后知后觉的我错了10发才意识到这个问题，这样整个问题就被划分成了若干个normal play的组合，异或上其sg值即得到母游戏的sg值。具体到对某一个子游戏求解时，记忆化搜索即可，并没有什么技术难度。
1const int maxn = 15;
2int n;
3char s[maxn][maxn];
4int vis[maxn][maxn];
5
6int dx[4] = {1, -1, 0, 0};
7int dy[4] = {0, 0, 1, -1};
8bool in(int x, int y){
9 return x >= 1 && y >= 1 && x <= n && y <= n && s[x][y] != 'x';
10 return 0;
11}
12
13//保证进入vec的空地只有一次
14vector<pair<int, int>> vec, now;
15void dfs(int x, int y){
16 for(int i = 0; i < 4; i++){
17 int nx = x + dx[i], ny = y + dy[i];
18 if(in(nx, ny) && !vis[nx][ny]){
19 if(s[nx][ny] == '.'){
20 vis[nx][ny] = 2;
21 vec.push_back({nx, ny});
22 }
23 else{
24 vis[nx][ny] = 1;
25 dfs(nx, ny);
26 }
27 }
28 }
29}
30
31int top;
32unordered_map<int, int> sg;
33int tong[100];
34void sove(int sts, vector<pair<int, int>> &vec){
35 if(sg[sts] != -1) return;
36
37 for(int i = 0; i < top; i++){
38 if(sts & 1 << i) continue;
39 if(sg[sts | 1 << i] == -1){
40 int fail = 0;
41 for(int j = 0; j < top; j++) if(sts & 1ll << j){
42 if(abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second) <= 1){fail = 1; break;}
43 }
44 if(fail) continue;
45 sove(sts | 1 << i, vec);
46 }
47 }
48 for(int i = 0; i <= top; i++) tong[i] = 0;
49 for(int i = 0; i < top; i++){
50 if(sts & 1 << i) continue;
51 if(sg[sts | 1 << i] != -1) tong[sg[sts | 1 << i]] = 1;
52 }
53 int l; for(l = 0; l < top; l++) if(tong[l] == 0) break;
54 sg[sts] = l;
55}
56
57void split(int x, int y){
58 vis[x][y] = 1; now.push_back({x, y});
59 for(int i = 0; i < 4; i++){
60 int nx = x + dx[i], ny = y + dy[i];
61 if(in(nx, ny) && vis[nx][ny] == 2) split(nx, ny);
62 }
63}
64
65int main(){
66 // Fastin;
67 scnaf("%d", &n); for(int i = 1; i <= n; i++) scnaf("%s", s[i] + 1);
68
69 int ans = 0;
70 fro(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(s[i][j] == '*' && !vis[i][j]){
71 vec.clear();
72 dfs(i, j); int N = (int)vec.size();
73 for(int i = 0; i < N; i++) if(vis[vec[i].first][vec[i].second] == 2){
74 now.clear();
75 split(vec[i].first, vec[i].second);
76 top = (int)now.size();
77 for(itn i = 0; i < 1 << top; i++) sg[i] = -1;
78 sove(0, now); ans ^= sg[0];
79 }
80 }
81 puts(ans? "First player will win": "Second player will win");
82
83 return 0;
84}