我是靠谱客的博主 专注大米，这篇文章主要介绍第八届“图灵杯”NEUQ-ACM程序设计竞赛（全题解&&详细）A 切蛋糕B 小宝的幸运数组C 上进的凡凡D Seek the Joker IE Seek the Joker IIF 成绩查询ingG 贪吃的派蒙H 数羊I 买花J 这是一题简单的模拟K 黑洞密码L 建立火车站，现在分享给大家，希望可以做个参考。
此文转载自：https://blog.csdn.net/liudashuai666/article/details/113481852#commentBox
个人感觉这场比赛题目难度大概对应CF的div3吧。
直接记录每段非降序子数组长度，然后(1+len)*len/2求出该段对应个数累加即可。
假设派蒙的位置为p，那如果p-1>k(这种情况下循环不足一个周期)，那就意味着还没轮到他就已经没了(他前面那个人洗碗)，或者(循环了至少一个周期)左边人的最大总和要小于k，这种情况下还是轮不到他洗碗。至于其余情况，则他必洗碗。
先用节点存城市与城市之间的距离(sum)、被分成段的长度(val)以及它们之间站台数+1(len)。然后拿优先队列存节点，按val降序排列。循环k次每次取val最大的，并弹出节点，len++，更新val(val=sum/len)，再把新的节点push进去，最后队顶的val就是答案(当然啦，如果最后的val是小数，那么结果应该是val的整数部分+1)。
比赛链接
感谢出题人手下留情，第一次补完所有题，着实开心。
个人感觉这场比赛题目难度大概对应CF的div3吧。
A 切蛋糕
题目：
第一题本来打算开它的，两分钟没啥头绪，就跳了。赛后看大佬们的代码，好家伙，我直接好家伙，上来就是暴力，先切2047次，把蛋糕切成2048块(也就是2的16次方，比题目要求的15次方大就行)，然后嘛就按照题目意思去解方程：|x/2048-1/k|<=1/2^10，最后循环k次，每次将x个蛋糕打包。循环的时候用到了左移位，不太懂位运算的同学可以参考这篇博客(click here)，里面介绍的很全哦~。
Code：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int main() { int k; cin >> k; cout << k + 2047 << endl; for (int i = 0; i < 11; i++) for (int j = 1; j <= (1<<i); j++) cout << 1 << ' ' << i << endl; int x = (1<<11) / k; for (int i = 1; i <= k; i++) { cout << 2 << ' ' << x << ' '; for (int j = 1; j <= x; j++) cout << "11 "; cout << endl; } return 0; }
B 小宝的幸运数组
就是要求能被k整除的最大连续子数组的长度嘛。数据范围这么大，暴力必TLE。可以先用sum[]去记录前i项的和。假设前m项的和取模k得到x, 前n项的和取模k得到的也是 x, 那么m+1-n这个子序列的和肯定是能够被k整除的。想到这个那么问题就很简单了。
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
26ll a[100005], sum[100005]; ll pos[100005]; int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; } mem(pos, INF); ll ans = -1; for (int i = 1; i <= n; i++) { ll m = sum[i] % k; if (m == 0) ans = max(ans, 1ll*i); if (pos[m] != INF) ans = max(ans, i - pos[m]); pos[m] = min(pos[m], 1ll*i); } cout << ans << endl; } return 0; }
C 上进的凡凡
直接记录每段非降序子数组长度，然后(1+len)*len/2求出该段对应个数累加即可。
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
26struct node { ll len; }e[100005]; ll sum(ll len) { return (1+len)*len/2; } ll a[100005]; int main() { int n, id = 1, pos = 1; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; e[i].len = 1; } a[n+1] = -INF; for (int i = 1; i <= n; i++) if (a[i]<=a[i+1]) { e[id].len++; } else id++; ll ans = 0; for (int i = 1; i < id; i++) ans += sum(e[i].len); cout << ans << endl; return 0; }
D Seek the Joker I
巴什博弈，老经典的博弈入门题了，只是把取光者剩改成取最后一个败，其实原理是一样的。对于这题来说，n % (k + 1) == 1就是一个必败点嘛。
Code：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; if (n == 1) cout << "ma la se mi no.1!" << endl; else if (n <= k) cout << "yo xi no forever!" << endl; else { int tmp = n % (k + 1); if( tmp == 1 ) cout << "ma la se mi no.1!" << endl; else cout << "yo xi no forever!" << endl; } } return 0; }
E Seek the Joker II
两堆石子，一堆k-1，另一堆n-k，先取到任意一堆的最后一个输，emm，这不是威佐夫博弈嘛。啪的一下就AC了，很快啊~
Code：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17const double GSR=(1+sqrt(5.0))/2; int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; int a = k-1, b = n-k; if(a > b) swap(a, b); if(a == (int)(GSR*(b-a))) cout << "ma la se mi no.1!" << endl; else cout << "yo xi no forever!" << endl; } return 0; }
F 成绩查询ing
交了一发暴力，先TLE为敬。然后就掏出了C with STL的传统艺能map+set，想着应该能过，结果还是TLE了，补题的时候才发现。。。把endl改成"n"直接就能过，emm，这又是什么玄学，然后听说endl要比"n"慢一些，然后嘛。。。反手就加了一句
#define endl “n”
(毕竟疯起来连int都define成longlong手动狗头)
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
43struct node { string name; int grade, sex, sno; }s[100005]; int cmp(node a, node b) { return a.name<b.name; } map<string, node> m; set<string> se[200]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> s[i].name >> s[i].grade >> s[i].sex >> s[i].sno; sort(s, s+n, cmp); for (int i = 0; i < n; i++) { m[s[i].name] = s[i]; se[s[i].grade].insert(s[i].name); } int t; cin >> t; while (t--) { int op; cin >> op; if (op == 1) { string str; cin >> str; node tmp = m[str]; if (tmp.sno != 0) { cout << tmp.grade << ' ' << tmp.sno << ' ' << tmp.sex <<endl; } } else { int grade; cin >> grade; set<string>::iterator it; it = se[grade].begin(); for(;it!=se[grade].end();it++) cout<<*it<<endl; } } return 0; }
G 贪吃的派蒙
假设派蒙的位置为p，那如果p-1>k(这种情况下循环不足一个周期)，那就意味着还没轮到他就已经没了(他前面那个人洗碗)，或者(循环了至少一个周期)左边人的最大总和要小于k，这种情况下还是轮不到他洗碗。至于其余情况，则他必洗碗。
Code：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23ll s[100005]; int main(){ int q; cin >> q; while (q--) { int n, k; cin >> n >> k; int m = 0, p; for (int i = 1; i <= n; i++) { int x; cin >> x; if (x > m) { m = x; p = i; } s[i] = s[i-1] + x; } if (p > k+1 || (s[n] >= k && s[p-1] < k)) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }
H 数羊
直接根据题目给出来的公式写个dfs就行了。
Code：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20const ll mod = 998244353; ll dfs(int n, int m) { if (n == 1 && m == 0) return 2; if (n == 0 && m >= 0) return 1; if (n >= 2 && m == 0) return n+2; if (m == 1) return (2*n)%mod; return dfs(dfs(n-1, m), m-1)%mod; } int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; cout << dfs(n, m) % mod << endl; } return 0; }
I 买花
emm，等比数列前n项和，直接暴力遍历一遍(总共才15天嘛)。
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
30int qpow(int a, int n) { int ans = 1, base = a ; while (n) { if (n & 1) ans = (ans * base) ; base = (base * base); n >>= 1; } return ans; } int main() { int t, n; cin >> t; while (t--) { cin >> n; int flag = 0; for (int i = 2; i <= 15; i++) { int k = pow(2,i)-1; if (n%k == 0) { flag = 1; break; } } if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
J 这是一题简单的模拟
正如题名所述，”这是一道简单的模拟“，出题人诚不欺我。照着题目要求码一遍就好了，如果WA了，就多看几遍题目。
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
51int mp[305][305]; int a[2005], v[305]; int main() { int N, M; cin >> N >> M; mem(mp, -1); for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; mp[u][v] = mp[v][u] = w; } int k, ans = INF; cin >> k; for (int j = 0; j < k; j++) { mem(v, 0); mem(a, 0); int n, bol = 1; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; v[a[i]]++; if (v[a[i]]>1) bol = 0; } for (int i = 1; i <= N; i++) { if (v[i] != 1) { bol = 0; break; } } if (bol == 0) continue; bol = 1; int sum = 0; a[0] = a[n+1] = 0; for (int i = 1; i <= n+1; i++) { if (mp[a[i]][a[i-1]] == -1) { bol = 0; break; } else { sum += mp[a[i-1]][a[i]]; } } if (bol) { ans = min(ans, sum); } } if (ans != INF) cout << ans << endl; else cout << -1 << endl; return 0; }
K 黑洞密码
感觉这和上一题差不多，就差把 ”这是道模拟题“ 写在题面上了。对着题目要求直接码一遍就行了。
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
33char s1[100],s2[100],s3[100]; int main() { cin >> s1; int l = 0, r = 0, len = strlen(s1); for (int i = 0; i < len; i++) if (s1[i] >= '0' && s1[i] <= '9') s2[l++] = s1[i]; else s3[r++] = s1[i]; for (int i = 0; i < r; i++) { if (s3[i] >= 'a' && s3[i] <= 'z') { s3[i] -= 'a'; s3[i] = s3[i] + s2[i] - '0'; if (s3[i] >= 26) { s3[i] %= 26; if (s3[i] == 25) s3[i] = 'b'; else s3[i] += 'B'; } else s3[i] += 'a'; } else { s3[i] -= 'A'; s3[i] = s3[i] + s2[i] - '0'; if (s3[i] >= 26) { s3[i] %= 26; if (s3[i] == 25) s3[i] = 'B'; else s3[i] += 'b'; } else s3[i] += 'A'; } } for (int j = 4; j <= 16; j += 4) for (int i = j-1; i >= j-4; i--) cout << s3[i]; return 0; }
L 建立火车站
先用节点存城市与城市之间的距离(sum)、被分成段的长度(val)以及它们之间站台数+1(len)。然后拿优先队列存节点，按val降序排列。循环k次每次取val最大的，并弹出节点，len++，更新val(val=sum/len)，再把新的节点push进去，最后队顶的val就是答案(当然啦，如果最后的val是小数，那么结果应该是val的整数部分+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
39struct node { friend bool operator< (node a, node b) { return a.val < b.val; } ll len; long double val, sum; }; priority_queue<node> q; ll dt[100005], a[100005]; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a+n); for (int i = 1; i < n; i++) dt[i] = a[i]-a[i-1]; for (int i = 1; i < n; i++) { node tmp; tmp.val = tmp.sum = dt[i]; tmp.len = 1; q.push(tmp); } while (k--) { node tmp = q.top(); q.pop(); tmp.len++; tmp.val = tmp.sum/tmp.len; q.push(tmp); } node ans = q.top(); ll key = (ll)ans.val; if (ans.val == key) cout << key << endl; else cout << key+1 << endl; return 0; }
最后
以上就是专注大米最近收集整理的关于第八届“图灵杯”NEUQ-ACM程序设计竞赛（全题解&&详细）A 切蛋糕B 小宝的幸运数组C 上进的凡凡D Seek the Joker IE Seek the Joker IIF 成绩查询ingG 贪吃的派蒙H 数羊I 买花J 这是一题简单的模拟K 黑洞密码L 建立火车站的全部内容，更多相关第八届“图灵杯”NEUQ-ACM程序设计竞赛（全题解&&详细）A内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复