月赛时必须回宿舍zzzzZZZZZZ，于是当时没怎么捉。
我太蒟蒻了T_T
3472暂时还没看题目
3476被虐了一早上，现在在死皮赖脸地看shi哥的题解
【ZOJ3467】
一只3D骑士给定他跳的方法(x,y,z)，问两点间点字典序最小的路径
就是双向BFS，但是那个字典序不太好搞。然后最近学了map就果断使用了
判重时就要注意不是重复就给删掉……而是先比较步数，如果步数一样，则和原来的解一起从父节点link回去比较一下是哪一个的字典序优，如果现在的比较优，那么就把map里的指针指向该结点(相当于把原来那个点删掉，当然是lazy delete)。
因为WA重写了几遍= =，已经疼了，于是直接把两边3步都搜完最后再来判……
于是得到悲壮的8700MS。
Code：https://ideone.com/fqVUE
【ZOJ3468】
送分题。直接dp或者爆搜 T_T。
Code：http://ideone.com/8VheC
【ZOJ3469】
一个一维的数轴上，一个人初始站在X处送外卖，他跑的速度为V^(-1)。然后每个客户由两个元素(x,b)来描述，分别表示其位置以及纠结指数增长率。一个人收到外卖时的纠结指数为增长率*时间。求所有客户的纠结指数之和最小能是多少。
初看题目好像是最小哈密顿回路>_<，其实不然，如果你从X向右最远跑到某个地方，中间的肯定已经顺便送过了。然后时间的增长会增加所有未收到外面的纠结指数……于是乎每一段可以看成是单独的，于是就可以dp了。当然先要把结点按x排个序。
F[i,j,0]表示最左跑到i，最右跑到j，最后停在i上时最小纠结指数之和是多少。
F[i,j,1]表示最左跑到i，最右跑到j，最后停在j上时最小纠结指数之和是多少。
令tmp=b[1]+b[2]+..+b[i-1] + b[j+1]+…+b[n] (这些顾客都是没送到的)
于是
F[i,j,0]=min( F[i+1,j,0]+(tmp+b[i])*(x[i+1]-x[i]) , F[i+1,j,1]+(tmp+b[i])*(x[j]-x[i]) )
F[i,j,1]=min( F[i,j-1,0]+(tmp+b[j])*(x[j]-x[i]) , F[i,j-1,1]+(tmp+b[i])*(x[j]-x[j-1]))
Code：http://ideone.com/IAF8Y
【ZOJ3470】
这个转圈圈很难描述>_<，反正就是找到他变化的规律以后可以得出一个等差数列，然后我二分了一下，利用等差数列求和，找出第几圈的，然后分类讨论。
看着挺复杂，没想到1Y了。
Code：http://ideone.com/mWWUc
【ZOJ3471】
有n个星球，n<=10，然后给出一个邻接矩阵，w[i,j]表示i把j撞爆以后获得w[i,j]这么多分。问最后最多能得多少分？
直接状态压缩dp。F[i]（i用2进制位表示，1表示该星球已经被撞爆，0表示还在）表示i这种状态下的最高得分。转移随意。
Code：http://ideone.com/uv9qP
【ZOJ3472】
T_T还没搞
【ZOJ3473】
F[1,1,1]=1
F[i,j,k]=max(F[i’,j’,k’])+1 其中(i’|i j’|j k’|k 但是i’,j’,k’不等全部等于i,j,k)
求Sum(F[i’,j’,k’)) i’<=i && j'<=j && k'<=k
实际上这个函数就是从1,1,1这个点每次将某位乘一个数，然后变成i,j,k的最长路嘛>_<。
于是F[i,j,k]=1+i分解成素因子的个数+j分解成素因子的个数+k分解成素因子的个数。
显然他们是单独的。令d[i]表示这个数字分解成素因子的个数(可以用筛法求得)，Sum[i]=d[1]+d[2]+…+d[i]
那么ans=
i*j*k（都+1的那一部分）
+Sum[i]*j*k
+Sum[j]*i*k
+Sum[k]*i*j
后面的YY一下就知道了= =
Code：http://ideone.com/wGe5T
【ZOJ3474】
dp一下以后变成这样的题意：有n个对手，你要将他们全部打败，打某个的条件是当前体力值>Limit[i]，打完以后体力-Limit[i]+R[i]。
这个其实和JSOI某题本质是一个样的。这里有师父之前的证明。
首先如果打完会加血的，顺序随意，每次打能打的就行了。
打完了这些以后，下处理打完减血的。
假如给定一个成功的顺序，对于相邻的两个(i,j)，我们围观限制 （S是之前打了一些累积的体力变化值）
init_energe + S > Limit[i] —————–1
init_energe + S – Limit[i] + R[i] > Limit[j] ——————2
如果说(i,j)可以交换成(j,i)那么需要
init_energe + S > Limit[j] //由于-Limit[i]+R[i]<0，所以由上面第二条不等式自动获得
init_engerge+ S -Limit[j]+R[j] > Limit[i] ——————–3
把左边移剩init_energe+S
init_energe+S > Limit[j]+Limit[i]-R[i] ——————-2
init_energe+S > Limit[i]+Limit[j]-R[j] ——————–3
于是令2式右边>=3式右边。(这样必然能满足条件，使得可以交换)
Limit[j]+Limit[i]-R[i] >= Limit[i]+Limit[j]-R[j]
化简后……R[j] >= R[i] 。
就是说原来的顺序，如果满足R[j]<=R[i]，就可以交换，所以任何一个满足的顺序都可以调成R[i]递减的顺序。
于是贪心即可。
Code：http://ideone.com/k8cok
【ZOJ3475】
对于NOIER来说= =，这种程度的最小割大概都是秒杀类型的吧。
一看除了隔开以外没有什么其它要求了，那就是最小割了……
顺便制作了sap的模板。
Code：http://ideone.com/yq3cN
【ZOJ3476】 update@2011.2.17
围观了shi哥的解题报告以后没看懂神马意思= =，后来又问了叉姐，终于懂了。
就是说我们这个包围圈最外围必然是一条轮廓线，然后这条轮廓线实际上就是一个环。然后这个环有没有包含一个点呢？实际上就是判断点是否在多边形内的方法，向上作射线，如果穿过这个环的次数为奇数，那么就在环的包围内。
然后我们枚举环的起点，尝试跑一个环回来，但是我们需要知道我们跑了这个环以后，有哪些点被包围在里面。
我们先对每个在输入中存在的国家向上作射线(包括入侵者国家)，假设，我们枚举的这条外围路径跑去和某条射线相交了，那么对应这条射线的国家的存在性就要xor一下(因为对应的奇偶性变了)。
那么设d[x][y][z]为跑到(x,y)这个格子，状态为z(z是一个2进制数，表示每个国家在不在这个包围圈里面)，这时的最短路径是多少。
然后就spfa转移跑来跑去就行了……最后当然要和起点闭合才能形成合法的包围圈，最后就用d[Start_x][Start_y][z]去更新dp[z]。
现在的dp[z]表示如果要用一个包围圈，把z这个集合中的点，都包围在内，那么至少需要多少代价。
然后dp[z]还不一定是就是对应包围z个国家的最小代价。因为不一定是一个包围圈把它们包起来就行了。
还有可能外面一个大圈，中间有几只入侵者，然后再把它们围起来
所以后面还要一个枚举子集的状态压缩动态规划，来挖空这些中间部分。
T_T，看着挺复杂，其实写起来很简单。1Y了。
Code：http://ideone.com/gAPv1
（题目保证了n%2==0，所以可以这样变形……）
B=
