ZOJ Monthly, February 2011 (ZOJ3467~3476) 【lack of 3472】

月赛时必须回宿舍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