Codeforces Round #544 (Div. 3) 错过上分记Codeforces Round #544 (Div. 3) 错过上分记ABCDF1

Codeforces Round #544 (Div. 3) 错过上分记

rating是不可能上1600的。这辈子都不可能的。所以只能在Div.3遨游。

Virtual Participant做到简单的比赛总是很恨哦！

A

全换算成秒，算平均值，再换算回来就完事了。

用printf的话就可以直接用%02d，可惜我当时用的是cout，浪费了一点时间。

B

边界情况没考虑明白，我WA了3次。

显然每个数都对(k)取模。这些数就可以用100的桶存下来了。

两个点先特殊考虑：(0)和(frac{k}{2})（当(k)为偶数）。对答案的贡献就是除2乘2。

其他的点只需要取其中的最小值，除2乘2再加进答案。

然后就完事了。

C

这道题我脑子里面乱想，乱写就过了。。。

显然要找一个长度为10的区间，包含最多的数。

但是值域太大了，怎么搞？

其实只需要排序后，一个upper_bound减掉lower_bound即可算出任意一个区间内数的多少。

为了考虑周全，把每一个数左右5个数都考虑为该左节点，右节点就是左节点加10。一次查询只需要(O(log n))。

但是我怕考虑太多TLE了，于是用了一个unordered_map判重。

然后就过了。。。

D

比赛时没想出来，用了两种方法。第一种用double当map的key，第二种用pair表示分数，当map的key。

第一种方法会被卡精度过不去，怒用long double就TLE了。。。

第二种方法由于自己菜，没能过。

---

其实第二种方法就是标算。

首先对(a_i)和(b_i)分类讨论，可以得出：

1. 当(a_i = b_i = 0)时，(d)取任何数都成立。

2. 当(a_i neq 0, b_i = 0)时，(d)只能取(0)。

3. 当(a_i = 0, b_i neq 0)时，(d)取什么都不成立。

4. 当(a_i neq 0,b_i neq 0)时，(d)只能取一个非0实数(-frac{b_i}{a_i})。

对第一种情况，用一个变量记录，最后的答案加上即可。

其他的情况我们统统用分数记录。现在我们要做的就是统一所有的分数形式，然后用pair存下来。

人为规定第二种情况的(d)为(frac{0}{0})，第四种情况的(d)分子一定为正数。

规定后最后的一件事情只需要针对第四种，即约分。

注意：求gcd的两个数都只能是非负整数，绝对不能有负数！

最后遍历map，找到最大的数，加上第一种情况的个数就完事了。

F1

显然需要经过那个原图度数最多的点，如果有多个的话随便取。

然后从这个点开始跑个bfs，得到的bfs树就是一个最大度数的生成树了。

我这个sb居然用堆优化的prim还想了很久。。。

其他的题目