cf掉分日记 - Codeforces Round #769 (Div. 2) A - C
2022/1/31 6:04:37
本文主要是介绍cf掉分日记 - Codeforces Round #769 (Div. 2) A - C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- A- ABC
- 题目大意:
- 分析:
- B - Roof Construction
- 题目大意:
- 分析:
- C - Strange Test
- 题目大意:
- 分析:
- 总结:
A- ABC
题目大意:
给你一个字符串,判断是否可以在重排列这个字符串后,使得字符串不存在 长度大于等于 2 的回文子串。
分析:
很容易发现,一旦字符串长度超过 2,无论怎样都会存在回文子串,000,001,010,011,100,101,110,111。都存在回文子串。然后只需要特判一下 11, 00 即可
int main (){ IOS int t; cin >> t; while (t --){ int n; cin >> n; string s; cin >> s; if (n >= 3){ cout << "NO" << endl; } else{ if (s == "11" || s == "00") cout << "NO" << endl; else cout << "YES" << endl; } } return 0; }
B - Roof Construction
题目大意:
给你一个 0 到 n - 1 的排列,要求你构造出 最大相邻亦或值最小的排列顺序。
分析:
由题给样例的输出结果 2, 4,8,大胆猜测答案一定是 2 的幂次。
要使相邻数的亦或值最小,势必要尽可能消去二进制表达中最高位的 1。
我们拿 8 举例:
000 001 010 011 100 101 110 111
要使相邻的异或值最小,最高位是 1 的所有数应该放在一起相互抵消,但是一定有一个数的最高位是是抵消不掉的。要使这个值尽可能小,我们应该使亦或的结果只保留最高位的1。最简单的方法就是让 0 和 状如100000 的数 (此处 1 是最高位其他位均为 0),相邻摆放,小于100000的数放 0 一侧,大于的放另一侧。这样构造的结果可以保证答案不超过100000.
以 16 为例:
即 1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15,最大相邻亦或值为 8。
int main (){ IOS int t; cin >> t; while (t --){ int n; cin >> n; int m = 1; for (int i = 1 ; i <= n + 3; i *= 2){ if (i * 2 > n - 1){ m = i; break; } } for(int i = 1 ; i < m ; i ++) cout << i << ' '; cout << 0 << ' '; for (int i = m ; i < n ; i ++) cout << i << ' '; cout << endl; } return 0; }
C - Strange Test
题目大意:
进行尽可能少的操作使得 a = b,操作如下:
- a ++
- b ++
- a = a | b
分析:
非常蒙蔽的题,和标题一样觉得很神奇。结论是,只进行操作 1 或者 操作 2,直到进行一次操作 3就可以使得 a = b。
基于本人水平无法给出证明,但是题目有个很可疑的条件,b 的总和 不超过 1e6。其实看到这个条件就应该往暴力方向想了。赛中写了半年的模拟,一直 WA2。本场比赛依旧是小寄。
int main (){ IOS int t; cin >> t; while (t --){ int a, b, ans1 = 0, ans2 = 0; cin >> a >> b; int ta = a, tb = b; while ((ta | tb) != tb){ ta ++; ans1 ++; } ta = a, tb = b; int tempb = b * 2 + 100; while (((ta | tb) != tb) && tb < tempb){ tb ++; ans2 ++; } cout << min (min (ans1 + 1, ans2 + 1), b - a) << endl; } return 0; }
总结:
打得比上一次好,但是 C 做得依旧是一脸懵逼。最近的 C 感觉都有点阴间了。B过得慢了,但又好像没有太慢。可能是atcoder打多了。
这篇关于cf掉分日记 - Codeforces Round #769 (Div. 2) A - C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!