1001
ZRC&WD 签到
主要是考虑全所有情况。尽量还是考虑周全了再写代码…在纸上把情况都写全吧
1005
“签到”
题意：
把1~n分进m个集合，并使得第i个集合的中位数（偶数大小集合的中位数是较小的那个）是给定的bi。问是否可行。
LYF解(即题解做法)：
首先，bi一定被分别分进各个集合中。对于其它数，可以看作是m+1(或者少一点)个连续段。对于每两个不同的连续段，显然可以将其中的元素一一消去(放进介于两段之间的任意bi代表的集合中)。
若最长的段不长于其它所有段之和，显然有解。
否则，考虑最长段中多出来的元素是可以被分别加入到比最长段更小的中位数的集合中去(一段放一个)，因此判断最长段长度-其他段长度和是否大于比最长段小的中位数数量即可判断是否有解。
补1004
题意：
n1000个点(多组数据，总数4e6)的完全图，给定l数组，li表示需要选出并删除完全图中li条边组成的简单路径，保证l的和为完全图的边数，且单个l<=n-3。求方案。
解：
首先可以明显地看出，题目即为在完全图中找到(构造？)一条欧拉回路，使得其中任意n-3长度的子路径中无环。注意到n-3，这个限制耐人寻味。然而还是想不出来。
题解给出的方案是，(为了方便叙述)将出发点看作中间点，其余点均匀摆放在以中间点为圆心的圆上。将从中心点出发并回到中心点的过程称作一次构造的话，那么在每一次构造中都将周围点分成两个部分，在两个部分对应点中左右横跳。在完成一次构造后，旋转一个角度。
这样的构造方法可以保证欧拉回路中任意长度为n-2子路径中无环。
补1009
题意：
n100个人可选，每个人都有两个属性s和f。如果选中了其中k个人，第i个人的成绩会是$s_i\cdot(1-f_if_1-f_if_2-\cdots-f_if_{i-1}-f_if_{i-2}-\cdots-f_if_k)$。现在可以从n个人中选出任意个人参赛，问最终最好的成绩和是多少。(s是整数1e12，f是0到1之间、两位小数，答案要求九位小数精度)
多组数据，对于n的总量有所限制：$\sum n<1.2\times 10^4,\sum n^2<2.4\times 10^5,\sum n^3<1.2\times 10^7,\sum n^4<9\times 10^8$
解：
首先发现，精度要求很高，那么显然可以先把式子乘上10000，最后再除掉。这样，每一个选手的成绩式子就是$s_i\cdot(10000-f_i\cdot(\sum f_j-f_i))$。对于i选手而言，影响他的成绩的仅仅只有$\sum f_j$一项。又由于f的值域只有1到100，n只有100，因此$\sum f_j$的取值总共只有10000种。考虑一个枚举sum的暴力。
考虑若已经确定了sum，实际上就转化成了一个01背包问题。重量即选手的f，价值即成绩。
这样的暴力的复杂度为$O(10000\cdot n \cdot 10000)$，第一个10000为sum枚举的复杂度，第二个10000为01背包中状态的容量这一维。
01背包本就不具有优化空间了…吗？之前有过一些数据范围很奇怪的背包题，有各种巧妙的方法啊。也就是说，考虑10000的数据范围是否能不取满？
这道题，我们可以感受到，sum较大的时候基本上不可能有最优解。到什么程度才能保证不可能呢？列列式子试试看吧！
$$
Ans=\sum _ { i } s_i\cdot(10000+f_i^2-f_i\cdot sum)
$$
显然当右式不为正数时不会选当前的同学。
$$
10000+f_i^2-f_i\cdot sum>0\\
对上式求和，n\cdot 10000+\sum f_i^2-\sum f_i\cdot\sum f_j>0\\
sum^2-n\cdot 10000<\sum f_i^2\\
由1式得，10000f_i+f_i^3-f_i^2\cdot sum>0\\
对上式求和，10000\cdot sum+\sum f_i^3-sum\cdot\sum f_i^2>0\\
整理，\sum f_i^2<\frac{\sum f_i^3}{sum}+10000\le20000\\
将两个涉及\sum f_i^2的不等式联立得sum<100\sqrt{n+2}
$$
由此，我们在做01背包时可以只将sum枚举到$100\sqrt{n+2}$，那么01背包过程中状态数也变得与根号有关。总复杂度变成了$O(10000n^2)$，评测机快就能过了。
但是谁能想到这样推式子？…可能是经验吧？我还需要再琢磨一下…
补1011
博弈 看出来(i+1,j-1)和(i,j)胜负状态相同之后就可以记忆化搜索了 待仔细研究