好久没写了 鸽了三次训练赛以及swerc的记录…慢慢补
这是牛客多校训练的第一场，感觉难度接近区域赛？稍微比区域赛难一些？
D
LYF签到
B
ZRC 初中几何 仅利用相似三角形和勾股定理就能做出来
A
LYF 博弈
题意：两堆石子，一堆n个一堆m个，每次在一堆中拿走x(>0)个，同时在另一堆拿走k(>=0)*x个，问必胜情况。1e4组 n m 5e3
解：
设win[x][y]表示一堆x个一堆y个时的必胜情况，不妨假设x<=y。
显然
win[0][0]=false
win[0][x]=true
win[1][x]=true
win[2][3]=false
win[2][!=3]=true
win[3][x]=true
win[4][x]=true
可以找到一些规律：
- 如果win[x][y]=false，那么win[x][>y]必然true，因此每个x最多对应一个false的y，比如2对应3，3对应2
- 别的某些规律
但是貌似没啥用处
我们观察数据范围 nm5000，很可能是n^2预处理一个胜负情况表
那么就暴力预处理试试（类似素数筛法，从小往大搞，如果当前位置不能win，那么能到达当前位置的状态都能win）
显然能做 就A了
F
WD ZRC辅助
题意：给定L和R，问之间有多少数包含是3的倍数的子串(0算作3的倍数)
解：
WD一眼看到就是数位dp，然而大家A得太快 有点不敢相信
重新思考后显然任意连续三个数一定能找到是3的倍数的子串，所以大于99的都在答案内。
H
WD
题意：给定一个数列a，有一个哈希函数，仅仅是对m取个模，问最小的能让哈希函数完美哈希的m是多少。n5e5，a值域5e5
解：
如果对m取模会导致冲突，那么就说明a中两个数的差是m的倍数
因此，只要对a中每两个数的差的集合取“不包含0的mex”即可
怎么在比n^2更优的时间里跑出来呢？FFT。把每个数都看成多项式的指数即可。指数是负的怎么办？全都加五十万
补I
暂时还没学会 待补
补K
题意：
给定值域0~n-1的b数组，使其与0~n-1这n个数一一匹配，使得
$$
\sum \sqrt{|b[i]-j|}
$$
与最小值的差距不超过百分之四。保证数据随机生成，每组数据内含一百组以上的子数据（其中保证有一半多是小数据），百分之四取所有数据差异值的平均值。
解：
比赛时一直在退火坑里出不去，也没有在本地试验满数据范围的收敛情况，白白浪费许多时间。但是积累了经验。
首先显然题目可以转化成带权二分图匹配问题。KM算法可以做到$O(n^3)$复杂度，因此对于小数据可以使用KM算法直接算出最优值，将误差值平摊下去。
对于大数据，考虑贪心和随机化算法并用本地随机数据验证可行性。结论就是这道题贪心是可以做到很优的。