某岛

… : "…アッカリ～ン . .. . " .. .

September 30, 2012

ZOJ Monthly, September 2012

Problem A. Kitty’s Game
有一只喵身上有个记分牌，每个点上有一个全值 pi，她每沿着边走一步，记分牌上的数字就会变为这两个数字的 lcm。
问从起点S走到终点T，最后记分牌上数字为 k 的方案有多少种。（要求每一步记分牌上的数字都必须发生变化。
Tags: DP
略。( .. 注意到 lcm 单调递增，用这个值划分阶段即可。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711276

Problem B. BiliBili
。略。。类似 [JSOI2008]球形空间产生器sphere。。
做差后消去二次项，转换成线性方程组高斯消元即可。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709071

Problem C. Matrix Transformer
。。开始认为任意行或者列都有 1 就行，反例是 1 全部集中在某行某列的情况。。
。。。（然后发现其实就是求是否有完备匹配吧。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709215

Problem D. Gao the Grid
好像就是 Codeforces #136 DIV 1 的 Problem D。。(。的弱化。。
http://codeforces.com/contest/220/problem/D
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=711104

Problem E. Gao the Grid II
只计数锐角三角形。。。
。。（。。实际上数据弱成狗。。使用点积然后 O（n4）暴力也能过。。。
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=711141
（唔。。这类问题有待总结。。要不比赛时还是跪成 SB 啊。。

Problem F. Social Net
Sub Task 1: 最大生成树。（略。。
Sub Task 2: 给定一颗点权树，权值记为 ai，每次询问 x -> y 的路径上，
max(aj – ai), j >= i 的值是多少。。（将路径展开看成链。。
Tags: 倍增祖先
对于链上的问题，可以用 O(n) 解决。（动态规划。。
。树上结构则先用倍增祖先压缩结点信息。。再跑链上算法即可。。
（注意另一条要取反序，另外 lca 位置上的元素和谐起见最好一边各取一次。。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711497

Problem G. Toy Blocks
在数轴上给定若干多米诺骨牌，问至少几次可以放倒所有骨牌。
Tags: 动态规划，zkw 线段树
略）。。预处理和 DP 的过程都需要使用数据结构优化。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=713189

Problem H. Cipher LockCipher Lock
一个环, 环上每个点有 a, b 两个属性。。（a <= P, b <= Q.. 要求相邻两个环至少有一个属性是相同的。。其中一些位置要求是给定的 ai, bi.. 问方案总数。。 Tags: 状态压缩 DP, 矩阵乘法 http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711038

先根据每个已确定的位置拆环。（本题中已确定位置至少存在一个。。。
。。然后暴力 DP 。。然后发现状态只与是否和起始位置相同有关。。
。。有两个属性压缩后就是 2 位。。。
。。人工制出转移矩阵即可。。。

Problem I. Maze
。。比较裸的 mask bfs 。。没什么好说的。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=710689

Problem J. Sleeper’s Schedule
睡眠分配问题。。（区间调度问题 Power up，
。。一次醒来后必须在 [t, t+l] 之间再次睡眠。。
。如果在 t 小时之后睡眠，则会有相应的惩罚分数，且本次睡眠的时间相应延长。。。
。。(。。越往后单位时间的惩罚越高。。也就是超过 t 的部分平方。。很科学。。
最终得分为 [区间调度得分] – [熬夜惩罚]。。

Analysis:
。DP[i][j] 表示时刻 i 已经熬了 j 时间的最大收益。。转移分三种情况讨论即可。(睁眼，睡觉，取区间。。
注意边界等细节。（另外 dp[] 中间值有可能从负值转移，初始化要设置成 -oo。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=710322

ZOJ 3654 Letty’s Math Class
。。。麻烦的地方似乎只在高精度表达式解析的那块。。
。。Python 的话直接 input() 进来就行了。（Ruby 的对应的写法好像是 eval gets ?。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709304