Codeforces Round #409 交流贴

菜鸡目前只做了1AB..
1A 如果可以用x秒，显然小于x秒时也可使用。故考虑二分时间。
得到了时间，我们就可以算出p的贡献为p*t。
然后遍历每台机器，若cost[i]*t > stored[i], 说明这台机器需要分配资源。
所有机器分配完之后的总资源还大于等于0则说明可以运行到t。
需要注意的是，这题eps = -4， 二分上界为1e11才过= =..二分浮点还是老老实实for个百遍吧..
1B 考虑顶点i，若移动此点，则(i-1+n)%n, (i+1)%n也得动。
极限情况下这三点构成的三角形会退化成直线。
由于退化后这个三角形的周长其实是均摊到原图的，原图的周长不变，所以在纸上画一画发现其实就是原三角形把高一半处上方的三角形用高截成了两半，然后分到两边填充。
所以只需要算出这个高，答案就是所有高中最短的/2。
至于高的计算可以通过余弦定理算出cos，得到sin然后算出面积，除以底得到。

简单说下div1 C。我们将0到m的所有数按照与m的最大公约数划分为若干个集合。以m＝10为例，一共有4个集合1 2 5 10。把这些集合看成若干个点，根据整除关系建立一个DAG。每个节点的权值为属于这个集合，并且没在n个数中出现过的数的个数。在DAG上dp一遍，得到最大公约数的变化情况。显然，这个前缀积与m的最大公约数是非递减序列并且后者是前者的倍数。假设我们选择了1 2 10，那么我们先想办法构造出所有与m最大公约数为1的所有前缀积，这里用扩欧即可解决。如果构造出公约数为2的所有前缀积以此类推。