进度:A
B
C
D
。
不锁题解了,不讲武德的年轻人耗子尾汁。
涂了个鸦,不能怕被别人捣毁或把颜料沾走是吧啊啊。
总结比赛经验:注重手速的同时要细心。要勇于尝试(这个 D
题的做法我不是写出来过的吗?为什么不交??)。不要卡在一题上(这个 C
对中国人不是很友好吗?)。送给自己一段 Benq
代码里的注释:
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
CF1470A Strange Birthday Party
很明显的贪心思路:从大到小排序,如果可以买就买,否则给钱。
证明:把一个买的和给钱的互换,双方都多给钱。
CF1470B Strange Definition
场上大概 10min
就切了,没开 long long
见祖宗。
转化为 ({ m lcm}(x,y)gcd(x,y)=xy) 是平方数。
如果把所有数的平方因子筛尽,每个数变成一个质数集合,只有相同的数相乘是平方数。
然后如果同个数有偶数个,一轮后会变成 (1);否则永远都不会变。
然后随便模拟就好了。
CF1470C Strange Shuffle
我好 naive
啊,其实这题挺可做的。
先打个表,发现几轮后大概是这样:
1000 1625 1375 1125 1063 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 937 875 625 375
分析以下:(p) 上始终是 (k)。对于前 (frac n2) 轮,然后是一段轮数长度的 (>k),然后再是一段 (k),然后再是一段轮数长度的 (<k)。
然后看到这个 (1000) 步想到 (sqrt n):
-
先浪费 (sqrt n) 步,使满足一个特定位置上每个 (sqrt n) 块中存在 (>k) 和 (<k)。
-
用 (sqrt n) 步,找到一个 ( eq k)。不妨设为 (>k)。
-
用 (Theta(1)) 步,每次往左跳 (sqrt n),直到不能再跳。
-
用 (sqrt n) 步,往左跳 (1),找到 (p)。
(sqrt n) 最好取 (sqrt n-1),要不然 (n=4) 的时候会挂的。
CF1470D Strange Housing
首先要看清题目的两个条件:老师不相邻,老师周围的通道联通节点。
如果图不联通就 NO
了,否则一定是 YES
。
构造方案:先随意钦定一个点住老师,然后周围的点住学生。
把所有当前住学生的点扔进队列。每次拿出一个学生,把周围没住人的房间住老师,然后老师周围没住人再住学生,扔进队列。
最后住好的图一定满足要求,证明:
-
老师不相邻,因为老师一放上去周围就都放了学生了,所以别的老师也来不及偷袭马老师。
-
联通:每个点都是从 起点连过来的,都有到起点的路径。