Codeforces Round 886 (Div. 4)20230722
title: Codeforces Round 886 (Div. 4)20230722
categories:
- ICPC
tags:
- null
abbrlink: 22d7386e
date: 2023-02-27 00:00:00
总结:既然不会用python就不要比赛的时候再去查再想着用,chatgpt的思路和题意理解也就看个乐子
https://codeforces.com/contest/1850
1.B题wa了一发,对于vector熟练度不够,导致忘记对于每次一个测试点结束以后,vector没有clear2.D题:初看想复杂了,发现删除的题目数有单调性,就以为是二分。多看几个样例才发现是一个基于贪心但需要用排序加双指针实现的简单题
3.E题本质上是求解一个一元二次方程的整数解,由于数据量过大,如果普通二分longlong也不够,所以根据题目答案范围做了特判,超过1e18直接结束本轮,更新右端点。
考虑写一个解一元二次方程的模板函数,最好精度比较高
一道题题面如下,时间限制1s,每个测试点有t组样例 (1≤t≤100),然后n的范围是2e5,假设数据很强,我的算法 时间复杂度n*根号n,根据计算已经1e9所以肯定过不了
还有一个问题就是,如何理解下面这句话?
- 保证对于所有的测试用例,n 的总和不超过 2e5,
- 我的理解是对于一个测试点来说,由于有多组测试样例,在这一个测试点中,每次给出的n的加起来不超过2e5.
4.时间节点:写到F题只剩十分钟了,争取下次写快点
F题:由于比赛经验太少自己口胡了一个o(n*sqrt(n))的做法,显然tle了。
类题:https://www.acwing.com/problem/content/1293/
受到这题启发,成功ac了F题。
思路:提前预处理所有答案范围内的点,反向思考,遇到约数题时考虑从小到大枚举倍数,注意维护cnt数组需要对a[]排序且从大到小,防止重复叠加
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!