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】    [email protected]

围观了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

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。