【AC_LCC_CWJ第五场】ZOJ Monthly, January 2011(ZOJ3457~ZOJ3466)

……这场比较久了，只记得当时被屠了。

【ZOJ3457】

模拟题，主要是模拟1/x的这个除法。细节比较多，比较繁琐……

最后打表搞之。

【ZOJ3458】

题目大意：计算floor((sqrt(a)+sqrt(b))^n) % 2(a+b)    保证 0 < b-a < 1+2sqrt(a) 且 n%2==0

算法分析：

师父当时告诉偶们一个结论 (sqrt(a)+sqrt(b))^(2n) + (sqrt(a)-sqrt(b))^(2n)是整数。

把^(2n)里的2放进去，变成     （题目保证了n%2==0，所以可以这样变形……）

令A=       B=

然后求该数列的母函数：1 , A^1+B^1 , A^2+B^2 , A^3+B^3 ……   ————————令这个数列第i项为Z[i]

G(x)=1 + (A^1+B^1)x + (A^2 + B^2)x^2 + (A^3+B^3)x^3  ……

G(x)=

然后把两个分母乘起来(1-Ax)(1-Bx)得到1 -(A+B)x +ABx^2

∴Z[n] – (A+B)Z[n-1] + (A*B)Z[n-2]=0

然后A+B=2*(a+b),A*B=(a-b)^2

移项即得到递推式。然后用矩阵乘法可以很轻易得到Z[n]。

回归到原题，0 < b-a < 1+2sqrt(a)，那么容易得到0

然后题目求floor((sqrt(a)+sqrt(b))^n) % 2(a+b) ，那么就等于求(Z[n/2]-1) % 2(a+b)

里面因为是% 2(a+b)，所以有点特殊性，最后的式子可以化简，不过矩阵暴力之也差不多……

【ZOJ3459】

题目大意：台上有4张牌，司马和张角都有一定数量的手牌(每个人的手牌数量∈[1,6]),司马先手，然后每个人轮流换台上的牌。如果某个人在这个回合选择不换牌，那么游戏结束，这时候如果台面上的4张牌可以组成算出24点，那么司马赢，否则张角赢。特别地，司马在第一回合即使不换牌，游戏也不会结束。

算法分析

先暴力求24点的所有可能。然后博弈树搜索之，基本上就是极大极小过程。

【ZOJ3460】

题目大意：在二维平面上m个导弹发射塔，和n个目标，发射塔发射一枚导弹需要T1这么多时间，然后发射完以后，发射塔就可以准备下一次发射，这个准备时间为T2，导弹发射以后会以速度V直线飞到目标处。问最少要多少时间将所有的目标摧毁。

算法分析

二分答案，然后将发射塔拆点，对于发射塔i他所拆出的第j个点就表示第j次发射，然后再看时间允不允许飞到目标进行连边。

然后二分图最大匹配之，看是否可行。

【ZOJ3461】

题目大意：每个人有一个钱数(有正有负)，保证所有人的钱数之和为0。接下来给定m条带权无向边，如果这条边一旦启用，那么就要付上面的费用。最后问最少用多少费用可以使得这些人能够分钱分到每个人身上的钱数都为0。

人数<=16。边数可以接近完全图。

算法分析

……比赛时一直把他当有向边，然后果断悲剧。做法就是枚举每一个权和为0的子集，然后作最小生成树。然后再dp枚举子集合并之。

>_<其实这个做法是很显然的哎。后面dp枚举子集合并的复杂度是C(n,1)*2^1+ C(n,2)*2^2 + C(n,3)*2^3 + ... + C(n,n)*2^16<=2097120，所以不会超时。另外此题后面dp直接用2^16 * 2^16判子集的方法合并也不会超时……因为数据好像没有全0的情况。

【ZOJ3462】

题目大意：给定n(n<=1024)个文件，每个文件有几个Tags和一个大小。然后有m(m<=8192)个询问，每个询问给出一些Tags，如果一个询问中的Tags是某个文件的Tags的子集，那么将这个文件的算进符合这个询问，最后输出对于每个询问，符合条件的文件大小之和是多少。

算法分析

本题我的复杂度很不靠谱，理论上根本过不了……= =，不知道是否有正解。

就是对于所有文件的Tags建一棵Tire树，然后每个Tags建立一个邻接表，表示包含这个Tags的文件有哪些。

然后对于一个询问，就把这些Tags对应的文件搞出来求个交……当然这里有优化，如果某个文件在前面处理到的某个Tags里没有出现，那么后面就不用再枚举它了。接着就这样就过掉了……

【ZOJ3463】

题目描述十分不靠谱。他说一只手可以弹9个键，我和lcc都认为是5个白键，4个黑键……，谁知道他根本忽略了黑键。

算法

很简单的dp。F[i,j,k]表示左手拇指在i，右手拇指在j，弹完第k个音符需要的最小费用，然后暴力转移。

计算量是：52*52*1000*16 （16是转移复杂度）

【ZOJ3464】

水题，尽量让速度快的接球就可以了。

【ZOJ3465】

体力模拟题。

【ZOJ3466】

插头dp，基本概念就看cdq的ppt吧。

这个题不需要判断连通性，所以接进这个点的插头只需要计算数量，而这个点可引申出去的插头也只需要记录是哪几个，这样就可以拓展了。特别地，边界要处理一下。然后这个题目比较恶心的地方就是轮廓线会变。所以要分奇列和偶列讨论。

对于图中红色的插头，由于比较特殊，我就多弄了两位专门用来存……然后就是2进制储存是否有插头伸出来，hash便行。

 

【CODE】

【3457 打表的……】https://ideone.com/GQd73

【3458】https://ideone.com/JjnTV

【3459】https://ideone.com/SUwZr

【3460】https://ideone.com/1OUbx

【3461】https://ideone.com/YD6rA

【3462】https://ideone.com/OAzw8

【3463】https://ideone.com/BdF0V

【3464】https://ideone.com/Xa2go

【3465】https://ideone.com/c4Boa

 【3466】https://ideone.com/gORz0    （注意代码地址，ORz ！！）

update@2011/2/12