题目链接: http://codeforces.com/contest/1555
A. PizzaForces
solve: gcd是120，但是要处理240之内的最优情况，因为121就不是120+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#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f typedef long long ll; const int mx = 3e2 + 10; int sum[mx]; int main(){ memset(sum, inf, sizeof(sum)); sum[0] = 0; for (int i=1; i < mx; i++){ if (i>=6) sum[i] = min(sum[i-6]+15, sum[i]); if (i>=8) sum[i] = min(sum[i-8]+20, sum[i]); if (i>=10) sum[i] = min(sum[i-10]+25, sum[i]); } for (int i=mx-2; i; i--) sum[i] = min(sum[i], sum[i+1]); int t; scanf("%d",&t); while(t--) { ll n; scanf("%lld",&n); if (n <= 240) { printf("%dn",sum[n]); } else { ll a = n / 120 - 1; ll b = n % 120 + 120; ll ans = a * 300 + sum[b]; printf("%lldn", ans); } } return 0; }
B - Two Tables
solve: 往四个方向平移，讨论四种情况即可。
复制代码
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#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f typedef long long ll; const int mx = 3e2 + 10; int sum[mx]; int main(){ int t; scanf("%d",&t); while(t--) { int W,H; int x1,y1,x2,y2; int w,h; scanf("%d%d",&W,&H); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); scanf("%d%d",&w,&h); int ans = 1e9; int w1,h1; w1 = W; h1 = H - y2; if (h - h1 <= y1) ans = min(ans, max(0, h - h1)); //if (W >= h) //ans = min(ans, max(0, w - h1)); h1 = y1; if (h - h1 <= H -y2) ans = min(ans, max(0, h - h1)); //if (W >= h) //ans = min(ans, max(0, w - h1)); w1 = x1, h1 = H; if (w - w1 <= W - x2) ans = min(ans, max(0, w - w1)); //if (H >= w) //ans = min(ans, max(0, h - w1)); w1 = W - x2; if (w - w1 <= x1) ans = min(ans, max(0, w - w1)); //if (H >= w) //ans = min(ans, max(0, h - w1)); if (ans == 1e9) puts("-1"); else printf("%.6lfn", (double)ans); } return 0; }
C - Coin Rows
sovle: 暴力枚举Alice的走法，最后Bob要么从第一行一直走到尾，要么到第二行一直走到尾。
复制代码
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#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f typedef long long ll; const int mx = 1e5 + 10; int arrays[2][mx]; int pre[mx],suf[mx]; int main(){ int t; scanf("%d",&t); while(t--) { int m; scanf("%d",&m); int sums[2] = {0,0}; suf[m+1] = 0; for (int i=0;i<2;i++) { for(int j=1;j<=m;j++) { scanf("%d",arrays[i]+j); sums[i] += arrays[i][j]; if (i==0) pre[j] = pre[j-1] + arrays[0][j]; } } for (int i=m; i; i--) suf[i] = suf[i+1] + arrays[1][i]; int ans = 1e9 + 7; for (int i=1;i<=m;i++) { int res = 0; res = max(res, sums[0] - pre[i]); res = max(res, sums[1] - suf[i]); ans = min(ans, res); } printf("%dn", ans); } return 0; }
D - Say No to Palindromes
sovle: 要想保证不出现回文子串，那么就有a[i+3] == a[i]，所以只要知道前面三个字符是啥，后面就都一样了，又因为3个字符的排列只有六种，然后再用前缀和处理一起求区间的，这里前缀和又要考虑偏移，也就是三种情况，最后是18种情况。预处理一下就可以了。
复制代码
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#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f typedef long long ll; const int mx = 2e5 + 10; char str[mx]; int ans[3][6][mx]; int main(){ int n,m; scanf("%d%d",&n,&m); scanf("%s", str+1); for (int j=1;j<=min(n,3);j++) { for (int i=j;i<=n;i++) { ans[j-1][0][i] = ans[j-1][0][i-1]; ans[j-1][1][i] = ans[j-1][1][i-1]; ans[j-1][2][i] = ans[j-1][2][i-1]; ans[j-1][3][i] = ans[j-1][3][i-1]; ans[j-1][4][i] = ans[j-1][4][i-1]; ans[j-1][5][i] = ans[j-1][5][i-1]; if ((i-j) % 3 == 0) { if (str[i] != 'a') { ans[j-1][0][i]++; ans[j-1][1][i]++; } if (str[i] != 'b') { ans[j-1][2][i]++; ans[j-1][3][i]++; } if (str[i] != 'c') { ans[j-1][4][i]++; ans[j-1][5][i]++; } } else if ((i-j) % 3 == 1) { if (str[i] != 'a') { ans[j-1][2][i]++; ans[j-1][4][i]++; } if (str[i] != 'b') { ans[j-1][0][i]++; ans[j-1][5][i]++; } if (str[i] != 'c') { ans[j-1][1][i]++; ans[j-1][3][i]++; } } else { if (str[i] != 'a') { ans[j-1][3][i]++; ans[j-1][5][i]++; } if (str[i] != 'b') { ans[j-1][1][i]++; ans[j-1][4][i]++; } if (str[i] != 'c') { ans[j-1][0][i]++; ans[j-1][2][i]++; } } } } while (m--) { int x ,y; scanf("%d%d", &x, &y); int z = (x-1) % 3; int ret = 1e9 + 7; ret = min(ret, ans[z][0][y] - ans[z][0][x-1]); ret = min(ret, ans[z][1][y] - ans[z][1][x-1]); ret = min(ret, ans[z][2][y] - ans[z][2][x-1]); ret = min(ret, ans[z][3][y] - ans[z][3][x-1]); ret = min(ret, ans[z][4][y] - ans[z][4][x-1]); ret = min(ret, ans[z][5][y] - ans[z][5][x-1]); printf ("%dn", ret); } return 0; }
E - Boring Segments
sovle:按value排个序，然后发现具有单调性，双指针扫一下，拿个线段树维护一下。
复制代码
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#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,(rt<<1)|1 typedef long long ll; const int mx = 3e5 + 10; struct node { int l, r; int w; bool operator < (const node& a) { return w < a.w; } }s[mx]; int minv[mx<<3]; int lazy[mx<<3]; void update(int l, int r,int rt, int L,int R, int v) { if (L <= l && R >= r) { lazy[rt] += v; minv[rt] += v; return; } int mid = (l + r) >> 1; if (lazy[rt]) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; minv[rt<<1] += lazy[rt]; minv[rt<<1|1] += lazy[rt]; lazy[rt] = 0; } if (L <= mid) update(lson, L, R, v); if (R > mid) update(rson, L, R, v); minv[rt] = min(minv[rt<<1], minv[rt<<1|1]); } int main() { int n,m; scanf("%d%d",&n,&m); for (int i=0;i<n;i++) { scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].w); } sort(s, s+n); int l = 0, r = 0; while (!minv[1]) { update(1, m-1, 1, s[r].l, s[r].r-1, 1); r++; } int ans = s[r-1].w - s[l].w; while (l < r) { update(1, m-1, 1, s[l].l, s[l].r-1, -1); l++; while (!minv[1] && r < n) { update(1, m-1, 1, s[r].l, s[r].r-1, 1); r++; } if (minv[1]) ans = min(ans, s[r-1].w - s[l].w); } printf("%dn", ans); return 0; }
F - Good Graph
sovle: 首先可以推出以下2个结论
(1)如果一个环的weight是1，那么把这个环分成两半一半是weight是1，另一半肯定是0。由此推出如果两个点u,v可以经过一个环，那么u,v形成的简单环里必有一个weight为。所以不能加u,v边。
(2)假设u所在的图和v所在的图不连通，那么必然可以加u,v这条边
根据第二个结论可以先把成环的边先不考虑，把不成环的边先加进来，那么就会形成若干颗不连通的树，然后我们再把成环的边放进来考虑。设一个dis[u]为树的根到达节点u的weight，那么这个边能加入这棵树必须满足结论(1)以及dis[u]+dis[v]-2*dis[LCA(u,v)]+w(u,v) % 2 == 1,也就是dis[u]+dis[v]+w(u,v) % 2 == 1,这个可以O(1)求得，至于结论(1)可以通过将已经成环的路径染色，然后求u,v父边染色的总和- 2 * LCA(u,v)父边被染色的总和，如果大于0，说明u,v路径上存在成环的边，所以不能加入。时间复杂度大概是(n * long(n) + m*log(n))，不过使用倍增+树状常数过大容易被卡(反正我没过)。另一种更新方法用树链剖分可能也行，还有一种方法是"拆"树，也就可以看做是k个点的环上的边都删除，生成了k颗新的树，这k颗新的树间的节点不能相连。看上去很复杂，实际用线段树更新一下每个节点最近一个父节点在环上的是哪个，用dfs序表示就是保存最大的父节点值，然后只要看u,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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,(rt<<1)|1 typedef long long ll; const int mx = 3e5 + 10; struct node { int first; int second; int flag; node (int f, int s, int f1): first(f), second(s), flag(f1) {} node () {} }s[mx<<1]; bool ans[mx<<1]; bool vis[mx]; vector <node> vec[mx]; int refa[mx]; int deep[mx]; int val[mx]; int sum[mx]; int L[mx], R[mx]; int lca[mx][20]; int siz; int n,m; int find(int x) { return x == refa[x]? x : find(refa[x]); } void dfs(int u, int v) { L[v] = ++siz; vis[v] = 1; lca[v][0] = u; deep[v] = deep[u] + 1; for (int i=1;i < 20;i++) lca[v][i] = lca[lca[v][i-1]][i-1]; for (auto sub: vec[v]) { int son = sub.first; int w = sub.second; if (vis[son]) continue; val[son] = val[v] + w; dfs(v, son); } R[v] = siz; } int get_sum(int x) { int ans = 0; while (x) { ans += sum[x]; x -= x&(-x); } return ans; } void add(int x, int v) { while (x <= n) { sum[x] += v; x += x&(-x); } } int LCA(int u,int v){ if(deep[u]<deep[v]) swap(u,v); int i = 19,j; for(j=i;j>=0;j--) if((deep[u]-(1<<j))>=deep[v]) u=lca[u][j];//使u和v相同深度 if(u==v) return u; for(j=i;j>=0;j--){ if(lca[u][j]!=lca[v][j]){//不断逼近 u=lca[u][j]; v=lca[v][j]; } } return lca[u][0]; } int main() { scanf("%d%d", &n, &m); for (int i=1;i<=n;i++) { refa[i] = i; } for (int i=0;i<m;i++) { scanf("%d%d%d",&s[i].first,&s[i].second,&s[i].flag); int u = s[i].first,v = s[i].second,x = s[i].flag; int rfu = find(u); int rfv = find(v); if (rfu != rfv) { refa[rfv] = rfu; vec[u].push_back(node(v,x,1)); vec[v].push_back(node(u,x,1)); ans[i] = 1; s[i].flag = -1; } } for (int i=1;i<=n;i++) if(!vis[i]) dfs(i, i); for (int i=0;i<m;i++) { if (s[i].flag == -1) continue; int u = s[i].first, v = s[i].second, x = s[i].flag; int cnt = val[u] + val[v] + x; if ((cnt & 1) == 0) continue; int fuv = LCA(u, v); if (get_sum(L[u]) + get_sum(L[v]) > 2*get_sum(L[fuv])) continue; while (u != fuv) { add(L[u], 1); add(R[u] + 1, -1); u = lca[u][0]; } while (v != fuv) { add(L[v], 1); add(R[v] + 1, -1); v = lca[v][0]; } ans[i] = 1; } for (int i=0;i<m;i++) puts(ans[i]?"YES":"NO"); return 0; }
"拆"树做法:
复制代码
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
158
159
160
161
162
163#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,(rt<<1)|1 typedef long long ll; const int mx = 3e5 + 10; struct node { int first; int second; int flag; node (int f, int s, int f1): first(f), second(s), flag(f1) {} node () {} }s[mx<<1]; bool ans[mx<<1]; bool vis[mx]; vector <node> vec[mx]; int refa[mx]; int size[mx]; int deep[mx]; int val[mx]; int up[mx]; int L[mx], R[mx]; int belong[mx<<2]; int lazy[mx<<2]; int siz; int n,m; int find(int x) { return x == refa[x]? x : find(refa[x]); } void dfs(int u, int v) { L[v] = ++siz; vis[v] = 1; for (auto sub: vec[v]) { int son = sub.first; if (vis[son]) continue; dfs(v, son); } R[v] = siz; } void merge(int u, int v) { up[v] = u; deep[v] = deep[u] + 1; for (auto sub: vec[v]) { int son = sub.first; int w = sub.second; if (son == u) continue; val[son] = val[v] + w; merge(v, son); } } void update(int l,int r,int rt,int L,int R,int v) { if (L<=l&&R>=r) { lazy[rt] = max(lazy[rt], v); belong[rt] = max(belong[rt], lazy[rt]); return ; } int mid = (l + r) >> 1; if (lazy[rt]) { lazy[rt<<1] = max(lazy[rt<<1], lazy[rt]); lazy[rt<<1|1] = max(lazy[rt<<1|1], lazy[rt]); belong[rt<<1] = max(belong[rt<<1], lazy[rt]); belong[rt<<1|1] = max(belong[rt<<1|1], lazy[rt]); lazy[rt] = 0; } if (L <= mid) update(lson, L, R, v); if (R > mid) update(rson, L, R, v); belong[rt] = max(belong[rt<<1], belong[rt<<1|1]); } int query(int l, int r, int rt, int q) { if (l == r) { return belong[rt]; } int mid = (l + r) >> 1; if (lazy[rt]) { lazy[rt<<1] = max(lazy[rt<<1], lazy[rt]); lazy[rt<<1|1] = max(lazy[rt<<1|1], lazy[rt]); belong[rt<<1] = max(belong[rt<<1], lazy[rt]); belong[rt<<1|1] = max(belong[rt<<1|1], lazy[rt]); lazy[rt] = 0; } if (q <= mid) return query(lson, q); return query(rson, q); } int main() { scanf("%d%d", &n, &m); for (int i=1;i<=n;i++) { size[i] = 1; refa[i] = i; up[i] = i; deep[i] = 1; } for (int i=0;i<m;i++) { scanf("%d%d%d",&s[i].first,&s[i].second,&s[i].flag); int u = s[i].first,v = s[i].second,x = s[i].flag; int rfu = find(u); int rfv = find(v); if (rfu != rfv) { if (size[rfu] < size[rfv]) { swap(u, v); swap(rfu, rfv); } refa[rfv] = rfu; size[rfu] += size[rfv]; val[v] = val[u] + x; merge(u, v); vec[u].push_back(node(v,x,1)); vec[v].push_back(node(u,x,1)); ans[i] = 1; s[i].flag = -1; } } for (int i=1;i<=n;i++) if(!vis[i]) { int fi = find(i); dfs(fi, fi); } for (int i=0;i<m;i++) { if (s[i].flag == -1) continue; int u = s[i].first, v = s[i].second, x = s[i].flag; int qu = query(1, n, 1, L[u]); int qv = query(1, n, 1, L[v]); if (qu != qv) continue; int cnt = val[u] + val[v] + x; if ((cnt & 1) == 0) continue; int du = u, dv = v; while (du != dv) { if (deep[du] > deep[dv]) { update(1, n, 1, L[du], R[du], L[du]); du = up[du]; } else { update(1, n, 1, L[dv], R[dv], L[dv]); dv = up[dv]; } } ans[i] = 1; } for (int i=0;i<m;i++) puts(ans[i]?"YES":"NO"); return 0; }
最后
以上就是眼睛大小丸子最近收集整理的关于Educational Codeforces Round 112 (Rated for Div. 2) 题解的全部内容，更多相关Educational内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[luogu P1495] 【模板】中国剩余定理(CRT)/曹冲养猪题目解题思路代码](/uploads/reation/bcimg13.png)
发表评论 取消回复