ZOJ Monthly, September 2011(2014省份赛练习)

ZOJ Monthly, September 2011(2014省赛练习)

比赛链接

A 转化为取石子问题，石子数为质因数的个数，    假如为胜还要输出第一步的选择，  假设亦或和为ret， 那么满足 （ret^a[i]) < a[i] 就能选择(选择的石子为剩下ret^a[i]个)

code

B貌似是贪心

D最短路

F分类讨论  

   1.先判一开始是否窗口是否越界

   2.种类一样的话直接哈弗曼距离移动

   3.算出能选择的合法区域(原来的矩形向内缩R = sqrt(a*a/4+b*b/4))， 判断合法区域是否存在

   4.对于起点和终点在合法区域矩形某条边的一侧(且是矩形的外侧)，那么距离必然会加上到矩形这条边距离的2倍

code

G自动机+dp    code

H分类讨论+几何+三分    code

   1.先判一开始是否窗口是否越界

   2.种类一样的话直接移动

   3.算出能选择的合法区域(原来的矩形向内缩R = sqrt(a*a/4+b*b/4))， 判断合法区域是否存在

   4.其中有一个点在合法区域内  或者     起点和终点的连线与矩形相交    那么就直接移动

   5.2个点都在合法区域外侧，  对合法区域的4条边分别三分，取其中最小的距离

I 凸包+区间dp  code

J 矩阵乘法分段优化