7
2018
http://codeforces.com/gym/100491——pjy
H
最小割
-----------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------
7
2018
http://codeforces.com/gym/100956
J
DP.
-----------------------------------------------------------------------------------------------------------------------
I
猜猜也是随机。。。
可以用抽屉原理+不等式(?)证明随机一对成功的概率>=1/(n+1)，所以期望随机O(n)次。O(n^2/32)
28
2018
https://codeforces.com/gym/100959
http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204
E
签到题.
L
直接DP，需要用到观察.
J
prufer.
B
套用prim，用set维护.
C
BFS.
I
最短路.priority_queue用成了大根堆调了一晚上
F
[x/i]只有sqrt种，暴力.
H
根据期望的线性性每个格子独立.对于(i,j)算出第k步的概率.把每个格子的加起来一起算，暴力容斥就行了.
G
省选cbh讲过然而没听,不过挺简单的.
考虑枚举最后有多少段极长的黑块.
然后考虑每段是k条里的哪几条涂成的，容斥即可(DP算容斥系数，状态用map存).
于是转化为每段黑块的长度有个上界和下界，求铺在长度为n的链上的方案数.经典容斥.
O(挺快的).
D
DP状态很显然.f[i][j]表示第一个串前i个数第二个串前j个数形成的本质不同方案数.a[i]!=b[j]时候很容易转移.当a[i]=b[j]时候，为了不重不漏，考虑枚举往前移直到不同的那个地方的数谁在前，分别枚举是在另一个串到哪个数时候被加入的，后面那个形式的方案数可以预处理.
-----------------------------------------------------------------------------------------------------------------------
A
LJOJ4990.当时NOIP模拟赛时候其实不太会。。。
感觉这种题挺××的.
从小到大枚举质因子，如果一个数现在已经不行了，再乘上之后的质因子还是不行的(显然).不断乘新的质因子扩展即可.
O(很快).
M
感觉需要提高一下构造水平。
考虑把这东西弄得尽量均匀，所以把n个点按顺序放在圆上。
考虑这样子构造会比较均匀：每在圆上放一个三角形，就把这个三角形循环位移的所有三角形也放上，即n个n个放。
然后就转化成了相同多数量的1~n-1，要三个三个拎出来，每次拎出来的和%n=0。
不妨试试1~n-1都3个，那么总和=3n*(n-1)/2，n是奇数才有希望。举个例子n=7
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
注意到1+1，2+2，3+3，，，6+6 % 7 互不相同且!=0，所以直接拎{i,i,n-i-i}就OK了。
至此我们已经解决了n为奇数。
对于偶数，我们发现很难像奇数一样直接构造。
考虑构造题的一般套路，除了直接构造外，还可以把问题（递归）转化为子问题或是已经能解决的问题。
考虑化偶数为奇数，先把特殊点n拎出来。仍然考虑比较均匀地构造，比方说n向圆上所有距离为x的点对搞了个三角形，那么n与圆上所有点连了2条，圆上所有距离为x的连了一条。于是我们发现，圆上少拎一次，少拎的那3个与特殊点n去搞三角形，就做完了。
K
坐等方尤乐秒题。。。
