我是靠谱客的博主 怕孤单黑夜，这篇文章主要介绍【数论】【DP】【LCM】2018 USP-ICMC【待补】A. Nicoleta and the circle of kidsB. Ugly NumberC. Two CatsE. Loppinha, the boy who likes sopinhaG. Traffic ManagementI. I Will Go，现在分享给大家，希望可以做个参考。
比赛传送门
A. Nicoleta and the circle of kids
Description
每个人可以连边，最远连到第（i+k）%n 个人，边权为两个人之间的距离，求最大生成树
Range
1 ≤ K < N ≤ 1e9
Solution
方案一：LCM
如果每个人都选取最优的连边策略，假设在人数可以无限扩大的前提下，那么每个人都可以向接下来的第k个人连边，很容易得出一个循环节，长度为 lcm(n, k)，那么针对于每一个循环节，可以做为连边的起点（左边没有点与它相连）的点一共有 n * k / l 个，同时从每一个起点出发的线路长度为 k 的边一共有 l / k - 1个。经过这样的策略连边后，就形成了 n * k / l 条（也就是所谓的起点数）独立的长链，那么只需对这些条长链间再两两之间连一条长度为 k-1 的边即可形成一棵树。
方案二：gcd
每一个人都优先向第k个人连边，剩下的连第k-1个人，这样得到的边权和一定是最大的
Code
复制代码
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#pragma GCC diagnostic error "-std=c++11" #include <cstdio> #include <tr1/unordered_map> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #define pb push_back #define mp make_pair #define fi first #define se second #define lowbit(x) x&(-x) #define PII pair<int, int> #define mst(a, b) memset(a, b, sizeof(a)) #define rush() int T; scanf("%d", &T); while(T--) #define FIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef double db; typedef long long LL; const int INF = 0x3f3f3f3f; const double eps = 1e-8; const int Mod = 1e9 + 7; const int MaxN = 5e5 + 5; LL n, k; LL gcd(int a, int b) { return b ? gcd(b, a % b) : a; } LL lcm(LL x, LL y) { return x / gcd(x, y) * y; } int main() { while(~scanf("%lld %lld", &n, &k)) { LL g = gcd(n, k), l = lcm(n, k); // 方案一 LL cnt = l / k - 1, group = n * k / l; LL ans = group * cnt * k + (group - 1) * (k - 1); // 方案二 // LL ans = 1LL * k * g * (n / g - 1) + 1LL * (g - 1) * (k - 1); printf("%lldn", ans); } return 0; }
B. Ugly Number
Description
给出一串长度为n的数，不停地旋转这个数，询问在旋转的过程中会不会出现比初始状态小的数
Solution
对于这个字符串，可以求出一个最小表示法，也就是在旋转过程中会出现的数中最小的那一个，如果最小表示法的第一个字符不是初始串的第一个字符就不合法
Code
复制代码
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#pragma GCC diagnostic error "-std=c++11" #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #define fi first #define se second #define mst(a, b) memset(a, b, sizeof(a)) #define rush() int T; scanf("%d", &T); while(T--) #define lowbit(x) x&(-x) using namespace std; typedef long long LL; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const double eps = 1e-9; const int Mod = 1e9 + 7; const int MaxN = 1e6 + 5; char s[MaxN]; int main() { int n; scanf("%d %s", &n, s + 1); for(int i = 1; i <= n; i++) { s[n+i] = s[i]; if(s[i] < s[1]) { printf("Non"); return 0; } } int l = 1, r = 2; while(l <= n && r <= n) { int k = 0; while(k <= n && s[l+k] == s[r+k]) k++; if(s[l+k] <= s[r+k]) r += k + 1; else l += k + 1; } if(min(l, r) == 1) printf("Yesn"); else printf("Non"); return 0; }
C. Two Cats
Description
Solution
Code
E. Loppinha, the boy who likes sopinha
Description
Solution
Code
G. Traffic Management
Description
在一条直线上有n辆车在匀速行驶，每辆车都有自己的初始位置和速度，当后面车与前面的车相撞时，后面车的速度会瞬间变得和前面车一样，询问最后一次相撞的时刻。
Solution
Code
复制代码
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#pragma GCC diagnostic error "-std=c++11" #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #define fi first #define se second #define pd push_back #define mst(a, b) memset(a, b, sizeof(a)) #define rush() int T; scanf("%d", &T); while(T--) #define lowbit(x) x&(-x) using namespace std; typedef long long LL; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const double eps = 1e-9; const int Mod = 1e9 + 7; const int MaxN = 2e5 + 5; struct node { double s, v; }a[MaxN]; bool cmp(node x, node y) { return x.s < y.s; } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lf %lf", &a[i].s, &a[i].v); sort(a + 1, a + 1 + n, cmp); int pos = n; double ans = 0.0; for(int i = n; i >= 1; i--) { if(a[i].v <= a[pos].v) pos = i; else { double tmp = (a[pos].s - a[i].s) / (a[i].v - a[pos].v); ans = max(ans, tmp); } } printf("%.6fn", ans); return 0; }
I. I Will Go
Description
有一个游戏，现在一共有n个人，给出n个关系，如果第i个人去的话，那么第 a[i] 个人也必须去
Solution
第 i 个人去第 a[i] 个人也必须去的话，就形成了一组关系， 那么利用这些点之间的关系就可以建造一个森林，将每一个被连了的点打上标记，那么没有边连的点就可以作为森林中每颗树的根节点。
方案一：LCA
建立一个虚拟结点，使之分别与这些树的根节点相连，于是就形成了一棵树，对这棵树查询结点 u 是不是结点 v 的祖先即可。
方案二：DFS
以每棵树的根节点跑一遍dfs序，那么这个结点 u 的dfs序是否在点 v 内即可判断从 u 能否能到达 v。
Code
复制代码
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#pragma GCC diagnostic error "-std=c++11" #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #define fi first #define se second #define mst(a, b) memset(a, b, sizeof(a)) #define rush() int T; scanf("%d", &T); while(T--) #define lowbit(x) x&(-x) using namespace std; typedef long long LL; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const double eps = 1e-9; const int Mod = 1e9 + 7; const int MaxN = 1e6 + 5; // 方案一 vector<int> G[MaxN]; bool vis[MaxN]; int lg[MaxN], dep[MaxN]; int acst[MaxN][22]; int n; void init() { for(int i = 1; i <= n; i++) { lg[i] = lg[i-1] + ((1 << lg[i-1]) == i); } for(int i = 0; i <= n; i++) { vis[i] = 0; G[i].clear(); } } void dfs(int u, int fa){ int len = G[u].size(); acst[u][0] = fa; for(int i = 1; (1 << i) <= dep[u]; i++){ acst[u][i] = acst[acst[u][i-1]][i-1]; } for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != fa){ dep[v] = dep[u] + 1; dfs(v, u); } } } int LCA(int x, int y){ if(dep[x] < dep[y]) swap(x, y); while(dep[x] > dep[y]) { x = acst[x][lg[dep[x]-dep[y]]-1]; } if(x == y) return x; for(int i = lg[dep[x]] - 1; i >= 0; i--) { if(acst[x][i] != acst[y][i]) x = acst[x][i], y = acst[y][i]; } return acst[x][0]; } int main() { int q; scanf("%d %d", &n, &q); init(); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); x++; if(x) { G[x].pb(i); // G[i].pb(x); vis[i]++; } } for(int i = 1; i <= n; i++) { if(!vis[i]) G[0].pb(i); } dep[0] = 1; dfs(0, -1); while(q--) { int u, v; scanf("%d %d", &u, &v); u++; v++; if(LCA(u, v) == v) printf("Yesn"); else printf("Non"); // printf("%dn", LCA(u, v)); } return 0; } // 方案二： /* vector<int> G[MaxN]; int ind[MaxN]; int l[MaxN], r[MaxN]; // 记录每个点的dfs序的起始 int cur = 0; void dfs(int x) { l[x] = ++cur; for(int i = 0; i < G[x].size(); i++) { int u = G[x][i]; dfs(u); } r[x] = ++cur; } int main() { int n, q; scanf("%d %d", &n, &q); for(int i = 0; i < n; i++) { int v; scanf("%d", &v); if(v == -1) continue; G[v].push_back(i); ind[i]++; } for(int i = 0; i < n; i++) { if(!ind[i]) dfs(i); } while(q--) { int u, v; scanf("%d %d", &u, &v); if(l[v] <= l[u] && r[v] >= r[u]) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }*/
最后
以上就是怕孤单黑夜最近收集整理的关于【数论】【DP】【LCM】2018 USP-ICMC【待补】A. Nicoleta and the circle of kidsB. Ugly NumberC. Two CatsE. Loppinha, the boy who likes sopinhaG. Traffic ManagementI. I Will Go的全部内容，更多相关【数论】【DP】【LCM】2018内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[二分 前缀优化建图 2-SAT] Codeforces 587D. Duff in Mafia](/uploads/reation/bcimg4.png)
发表评论 取消回复