XDU_Truth 网络赛热身小结
6道百人水题+用随机算法YY出一道中档题。另外一到50人中档题卡那里了。
RANK83。
先出了全场较多的CIDF四题，I题在YY结论，开始思路错了，后来想到了正确的思路但是修改时引入了新的问题，没有检查出。
E题知道大概是DP求期望，没有掌握。A题，没有怎么去了解。
4题 - 8：16的罚时，RANK150；假如I题能出的话，15：16的罚时，RANK90+。
- 第一场
A - 水~
E - 做过的一道题目。第一次做还是花了不少功夫的。
J - 给x，求a-b=x，a,b都是素数。
打表可以发现，枚举a,b中较小的一个，很快就可以找到合适的。所以2重枚举就ok。
B - 水~
D - 给一些点，求构成的最小的三角形。
把==0的情况理解错了，贡献了2WA。
C - 水
G - 求一堆字符串里海明距离最小的一对。
正解不知道，CWK用随机抓几千次的算法跑过了，很神奇~
I - 把一棵树通过加边减边变成一个环，求最少的操作数。
把加边和拆边分开来考虑，拆边是要把树拆成k个环，怎么拆呢？对于一个结点u，度数d>2，那么随便拆掉d-2条就行。关键在于统计的时候不要重复（所以一般拆到父亲结点的边，便于计数）。
加边的条数 = k+1。合起来 就是答案。
- 第二场
C - 告诉一个正N边形内一个点到各个顶点的距离，求这个正N边形的面积。
二分枚举边长x，通过内角和=360来验证。最后算出面积。
I - 给定图，求与结点u有最多公共朋友的结点v。
枚举以结点k为公共朋友的结点(i,j)，更新com(i,j)。询问u，则枚举con(u,v)。数据是随机的，可以接受O(n^2)。
已经是朋友的就不能再推荐，开始没有考虑到，贡献1WA。
D - 给出最短路径长度dis(i,j)，求原图最少有多少条边？
考察的是对“松弛操作”的理解。
先假设每两个顶点i,j间存在一条边的长度为dis(i,j)，联想floyed和松弛操作。假设以k作为中间结点，dis(i,k)+dis(k,j)==dis(i,j), i != j != k，那么i,j间直接相连的边就没有必要存在。
F - 偏重模拟。
给一个物体的初速度，要能满足两个约束：
1. 能通过最高的山峰；
2. 在某些点的速度要>=v(k)；
用动能定理之类的就可以直接算出来了。但是中间要计算点的高度。
H - 一个序列x[i]，可以给某个数+1，或者添加一个新的1到序列，求M步操作能得到的最大序列积。
M很大，一个依赖结论的题。
结论是：在全为正的情况下，把<3的x[i]向3靠拢，全部都>=3之后，向序列中添加尽可能多的+3。
有奇数个负数的情况先把最大的负数变成0。
补题：
A -
E -
H题也值得注意，还有I、F中的strick。