Codeforces Round #805 (Div. 3) A——E补题
2022/7/12 23:24:04
本文主要是介绍Codeforces Round #805 (Div. 3) A——E补题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A. Round Down the Price
题意: 给一个数n,要求找到离这个数最近的10的幂次。然后输出两者差值
思路:看了下数据范围,1e9,直接枚举就好了。从1e9开始,如果大于n就除10,否则就停止,相减即可
解决代码:
void solve() { int n; cin >> n; int a = 1e9; while(a > n) { a /= 10; } cout << n - a << endl; }
B. Polycarp Writes a String from Memory
题意:给出一个单词,从前向后记,每次可以记住三种字母,问多少次可以记完整个单词。
思路:用set遍历字符串,尽可能的向后读。当set即将存进第四种字母的时候,说明set中已经有了3种字母,且已经达到了最大程度的存储,此时,ans++,将set清空,然后再存进第四种字母。
解决代码:
void solve() { string s; cin >>s; int len = s.size(); int cnt = 0; set<char> se; for(int i = 0; i < len; i ++) { se.insert(s[i]); if(se.size() == 4) { se.clear(); se.insert(s[i]); cnt ++; } } if(se.size()) cnt ++; cout << cnt <<endl; }
C. Train and Queries
题意: 给出一组数字,位于前面的数字可以到达后面的数字,但后面的不能到达前面的,数字可以重复。给出k次询问,每次给出a, b,问a是否能到达b。
一开始被吓到了,以为是邻接表并查集之类的。没想到只是水平太差了。基本没涉及到算法层次。
思路:用map存储每个数字出现的下标。然后在查询的时候访问是否a的第一个下标小于b的最后一个下标,若是yes,不是no。
解决代码:
void solve() { int n, k; cin >> n >> k; map<int, vector<int>> mp; for(int i = 1; i <= n; i++) { int x; cin >>x; mp[x].push_back(i); } while(k --) { int a, b; cin >> a>> b; if(mp.find(a) == mp.end() || mp.find(b) == mp.end()) //特判,当a或者b没出现在数组中,也是no { puts("No"); continue; } auto t = mp[a][0]; if(t < mp[b].back()) puts("Yes"); else puts("No"); } }
D. Not a Cheap String
题意:给出一个字符串,和一个数p。字母a——z分别对应价值1——26,问最少删除几个字符可以使字符串的总价值小于等于p。
思路:贪心即可。存储字符串里每个字符出现的次数,然后从大到小减去即可。当小于等于p时停止。然后输出子串的时候直接看存储数组中是否还有这个字符,没有就不输出,有就输出。
解决代码:
int ch[30]; void solve() { string s; cin >> s; int p; cin >> p; int v = 0; memset(ch, 0, sizeof(ch)); for(int i = 0; i < s.size(); i ++) { int t = s[i] - 'a' + 1; ch[t] ++; v += t; } if(v == p) { cout << s <<endl; return ; } for(int i = 26; i >= 1; i--) { if(ch[i]) { while(ch[i] && v > p) { v -= i; ch[i] --; } } } for(int i = 0; i < s.size(); i ++) { int t = s[i] - 'a' + 1; if(ch[t]) cout << s[i], ch[t] --; } cout << endl; }
E. Split Into Two Sets
题意:给出n张带有两个数字的牌,问是否能将之完全分为两份。每份都含有1——n所有的数字且不重复。(n是偶数)
写的时候没想到,天真就以为两个set就能写。写了半天发现不对劲,后来补题才知道是二分图。
思路:我看的解法是用并查集求连通块大小的思路写的。他所使用的方法是将每次输入的两个数放入一个集合里,然后如果两组数据中有交叉部分,则此集合的大小必然不是偶数。也就是有奇数环,我们知道,有奇数环必然不是二分图。而如果每个数出现的次数不等于2次,那么说明也必然不能完美分成两个集合。
解决代码:原作者题解网址
int p[N], sz[N], cnt[N]; int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; } void merge(int x, int y) { int a = find(x), b = find(y); if(a != b) { p[a] = b; sz[b] += sz[a]; } } void solve() { int n; cin >> n; for(int i = 1; i <= n; i ++) p[i] = i, cnt[i] = 0, sz[i] = 1; for(int i = 1; i <= n; i++) { int a, b; cin >> a >> b; merge(a, b); cnt[a] ++, cnt[b] ++; } for(int i = 1; i <= n; i ++) { if(cnt[i] != 2) { puts("No"); return ; } } for(int i = 1; i <= n; i ++) { if(i != p[i]) continue; if(sz[find(i)] % 2 == 1) { puts("No"); return ; } } puts("Yes"); }
总结:这场打的很水,虽说写了四道题,但是后两题a的很慢,且还有一道在重测的时候被官方样例hack了。
问题在于:
(1)题目没读清楚就开始盲目解题,第四题就是,以为必须等于p,还以为要用dp写,后面才发现就是个贪心,几分钟就可以解决,结果放了一个小时才去写。
(2)思维还是不够灵活,第三题其实也是自己写出来的,后来也就差一步,没用O(n)做法被刷了。但是解决速度较慢,没有快速能过想到。
(3)算法知识基本没有掌握,很多题目都是知道大概解法,但是不会写。要多去温习以前学过的知识,然后多了解不知道的知识。
这篇关于Codeforces Round #805 (Div. 3) A——E补题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 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功能效果提升