Myspace和Google Reader提醒我，某猪的万年blog终于更新了。
post的标题是TOKYO DOME 3 CONSECUTIVE SHOWS
跟正文相差无几的PS。。。-_____-bbb

这篇post的中心思想如下

1. TOKYO DOME 3 DAY SHOWS
广大的人民群众早就悟出来了。。。您真是太后知后觉了。。。-_________-bbb

2. Health Problem
比较让人注意的是这一段

And the day before yesterday, one of the doctors put some kind of heated cups on my back to suck my muscles up….. That felt very weird. And now I have bruises on my back….. hmmmm looks funny! Ha ha ha…..

我十分怀疑这就是传说中的拔火罐。。。-________-bbb

3. 冰激淋果然是王道阿~~~

Guess what….. I just ate one of the best ICE CREAMS I’ve ever had, and it’s low carb….. I don’t think life is that bad…..

Or I should say life is fucking wonderful !!!!!!!

read comments (7)

Andrew Stankevich’s Contest #1, ZOJ 2313-2320

Review

code量不大，有些有意思的题目，题目类型多样，难度适中

两道有点意思的数学题(2313, 2316)
两道有点意思的图论(2314, 2318)
三道不同类型的DP(树状、拼接型状态压缩、经典DP)(2315, 2317, 2319)
一道模线性方程组(2320)

Highlight

2313 Chinese Girls’ Amusement(数论)(new)
2314 Reactor Cooling(经典题)
2317 Nice Patterns Strike Back(经典题)
2318 Get Out!(图论)(new)

Detail

2313 Chinese Girls’ Amusement
Description: n(3<=n<=10^2000)个数围成一圈，从第一个数开始，每隔k(1<=k<=n/2)个数mark下，问能把n个数mark掉的最大的k是多少
Solution: 数论题
当k与n互质时，方程kx + ny = 1有解，则kx + ny = d(1<=d<=n)有解。所以要找的是与n互质的最大的k。通过找规律得出，当n为奇数时，k = n / 2，当n为偶数时，k = (n / 4 – 1) * 2 + 1。这个结论可以用手动欧几里德证明。
对于奇数：
gcd(2t + 1, t) = gcd(t, 1) = 1
对于偶数：
gcd(4t, 2t – 1) = gcd(2t – 1, 2t + 1) = gcd(2t + 1, 2) = 1
gcd(4t + 2, 2t – 1) = gcd(2t – 1, 2t + 3) = gcd(2t + 3, 4) = 1

2314 Reactor Cooling
Description: 带上下界的环形流
Solution: 经典题。
添加源点和汇点S, T，若存在边(u, v)，则添加边(S, v), (u, T)，容量为l，(u, v)的容量改为c – l。看S, T的最大流是否为sigma(li)

2315 New Year Bonus Grant
Description: 一棵有n(<=500000)个结点的树，每个结点可以分配给它的某一个子结点1000，或者被它的父结点分配1000，两者最多只能发生一种，求最大的分配方案
Solution: 树状DP。
f(i, none) = sigma(max{f(j, assign), f(j, assigned)})
f(i, assign) = max{f(k, assigned) + max{f(j, assign), f(j, none)}}
f(i, assigned) = 1000 + sigma(max{f(j, none), f(j, assign)})

2316 Matrix Multiplication
Description: 给定一个N*M的矩阵A，其中元素等于0或1，其中1有2 * M个，求T(A)*A中所有元素的和
Solution: 数学题
读入时统计出A中第i列1的个数tot(i)，则：
Sum = sigma(tot(i) * tot(i)) (1<=n<=i)
时间复杂度为O(3 * M)

2317 Nice Patterns Strike Back
Description: 求构造满足任意一个2×2矩阵中不同色的N*M(N<=10^100, M<=5)的黑白矩阵的方案数
Solution: 经典拼接型状态压缩DP
长度为2^k, 起始状态和结束状态为s1, s2的方案数为：
f(2^k, s1, s2) = f(2^(k – 1), s1, s3) * f(2^(k – 1), s4, s2)，其中s3, s4为满足要求状态对
计算出长度为2^k的方案数，然后拼起来
时间复杂度为O(log(N) * 2^5 * 2^5 * P)，其中p为预处理满足要求的状态对的个数，时限5s

2318 Get Out!
Description: 给定n(<=300)个点的位置(xi, yi)，以及圆半径ri，求某一个半径为r0的圆(x0, y0)是否能到达距离这个点无穷远的地方。
Solution: 暂缓发表

2319 Beautiful People
Description: 给定n(100000)个二元组(si, bi)，找出最多的二元组，使得对于任意两个二元组(si, bi), (sj, bj)有si > sj && bi > bj或者相反
Solution: DP
先按照si从小到大，然后找出这个新序列中以bk为keyword的最长上升序列。
时间复杂度O(n * log(n))

2320 Cracking’ RSA
Description: 给定m(<=100)个由前t(<=100)个质数乘出的数，问所有数的组合的乘积中完全平方数的个数
Solution: 求解模线性方程组解的个数
分解质因数，求解一个mod 2的线性方程组的解的个数。注意去掉全为0的解

read comments (0)

BAPC2007, ZOJ 2912-2121

Review

比较简单的题:
2915, 2918, 2920, 2921
有一定code量的题:
2913, 2919
有点意思的题:
2912, 2914, 2916, 2917, 2919

Highlight
2912 Average distance(经典题)
2914 Cutting Banknotes(数论)(new)
2916 Lingo(容斥原理)(new)
2917 Splitting the Loot(二分+Huffman Tree)
2919 Hiking(几何+最短路)(new)

Detail

2912 Average distance
Description: 计算一棵树上所有点对的平均距离
Solution: 经典题。
遍历整棵树，统计一条边两边的顶点数，这条边经过的次数就是两边顶点数之积。

2913 Bus Pass
Description: 给定一个无权连通图中G(V, E)(V <= 9999, E <= 99990)的m(<=200)个点，求一个中心点，使得距离这个中心点最远的点的距离最短。
Solution: BFS
将每个Bus Pass的Zone一同进行BFS，直到某一个点能到达所有的Zone为止。
时间复杂度为O(V * 10 * m)，5s时限

2914 Cutting Banknotes
Description: 给定一些面值的note，可以不断细分为两部分，问能否组成一个值X，其中X带两位小数
Solution: 数论题（没想出来这个题。。。-____-bbb）

考虑一般化的问题。设可以将note细分为K份，面值为b1, b2 … bn的note的公约数为d，则可以证明当N足够大时，对于任意的M > N，均存在:
Md = b1×1 + b2×2 + b3×3 + … + bnxn
令Y = K^T * X，只要T足够大，则只要d | Y，则Y能由这些note组成
令d2 = d / K^R，其中d2为整数且不能被K整除，如果X能被d整除，则X能被note表示出来。

本题可以先将X乘以4变成整数，然后考虑K=2的情况即可

2915 Dice Password Security
Description: 给定m(<=7776)个word(3<=len(word)<=10)，从中选出n(<=5)个word，回答q(<=20)个询问：使得words总长度为li(<=50)的组成方法有多少种？
Solution: DP题。

2916 Lingo
Description: 给定一个NxN(<=8)的矩阵，上面有k个没有填的格子，问填m个格子时，有多少概率至少有一行或一列或两条对角线的中的一条被填满
Solution: 容斥原理。
枚举每条线是否被填满，然后计算方案数。注意搜索矩阵时，当前的矩阵状态可以时时维护。复杂度为O(2^18 *
相传还有DP的做法

2917 Splitting the Loot
Description: 给定一个长度为w(<=1000000)的loot，将其分成n(<=50)块，每块的长度不小于给定的wi，split的操作是将一块loot split成两块，且要损失掉p%。求最多剩下多少loot
Solution: 二分剩下的loot，然后用类似huffman的方法(最优的分割方法)求解可行性。注意剩下的为0的情况。

2918 Pachinko
Description: 一个球从一个HxW(<= 100)的矩阵顶端的某一列滚下来，碰到一个obstacle，则以50%的几率向左右两边的column继续下落，如果落到一个gate中，就有一定的winning值，求winning的期望值
Solution: DP题。

令f(c, i, j)为从第c列下落，在第i行，第j列的可能性，则有：

f(i, j) -> 0
g[i - 1][j] == ‘.’ -> f(i, j) += f(i – 1, j)
g[i - 1][j - 1] == ‘*’ -> f(i, j) += f(i – 1, j – 1) * 0.5
g[i - 1][j + 1] == ‘*’ -> f(i, j) += f(i – 1, j + 1) * 0.5

isgate(g[i][j]) -> expectedWinning += winningPoint(g[i][j]) * f(i, j)

时间复杂度为O(H * W * W)

2919 Hiking
Description: 给定半径为r的n(<=1000)个圆，求在圆的范围内的给定两点的最短路
Solution: 几何+最短路（圆内交点不计这一点没想到。。。-______-bbb）
求出所有圆的交点，最短路必定由经过这些交点的线段构成。注意在圆内的交点可以忽略不计，求最短路时用现生成的dijkstra

2920 Ranking
Descrition: 给定一些规则，模拟一个比赛的排名系统
Solution: 规则模拟题
需要注意的是在题目数和罚时相等的时候，the point of comparison between tied teams will be the last point in time where their scores differed。

2921 Stock
Description: 给定n天每天收到的stock xi，卖出价pi(0<=pi<=100)，以及最多可以卖出的stock mi，求最多的收益
Solution: 简单优值替换贪心题
从第一天开始，用一个heap维护一个卖出的价格集合，如果当天有卖出余量，且当天的价格比heap中最小的大，则将其替换掉。

read comments (0)

Saratov School Regional Contest 2007, SGU 358-366

Review

难度中档偏简单，而且大部分是DP和模拟。

4道非常简单的题：358，362，363，365
3道比较简单的题：359，361，367
3道稍为有点难度的题：360，364，366

Highlight
360. B++ Interpreter (模拟题)
364. Lemmings (DP)
366. Computer Game (DP)

Detail

358. Median of Medians
Description: 给定三个三元组，先求出每个元组的中位数，再求这三个元组的中位数

359. Pointers
Description: 模拟一组指针操作，包括赋值，指针指定为另一指针的值，指针指定为另一指针地址，输出指针所指的值。4个指针，30条命令。
Solution: 比较简单模拟题。

360. B++ Interpreter
Description: 写一个B++语言的解析器
Solution: 稍微麻烦一点的模拟题，注意function A中调用的function B的arg可能需要替换成输入function A的arg

361. National Flag
Description: 给定一个NxM的矩阵(3<=N, M<=200)，满足任意3×2或2×3的格子中有且仅有2个#，求需要填充的最少的#的任意一个方案
Solution: 注意到3×2的填法最多有C(6, 2) = 15种，且对于任意一种填法，能推出唯一的3×3方案。于是枚举左上角的3×2矩阵，填充整个矩阵，取最小的方案。时间复杂度为O(15 * N * M)

362. Robot-Annihilator
Description: 给定Robot在矩阵中的运动规则，求出Robot的路线
Solution: 简单模拟题

363. Baggage Room
Description: 给定一个有n个窗口的service系统及排队规则，求排队序列
Solution: 简单模拟题。不过题意有点不合常理。

364. Lemmings
Description: 平面中n(n <= 100)个lemming每隔s秒以v=1的速度从一个hole A(x, h)落下，平面中有m(m <= 100)个平板，落到平板上继续按原方向以v=1的速度走，直到落到无限深处或者到达home B(a, b)。当一个lemming在平板上运动时，可以设置它stop，此后遇到它的lemming将改变方向。要求在到达home的lemming最多的条件下，最后一只lemming达到home的时间最少。
Solution: DP题。
将有效的平板(即在home所在的平板及home上面的平板)按照从低到高排序，下落到平板i的lemming有左走和右走两种状态。用Sum(i, dir)表示需要stop的lemming的数目，则有
Sum(i, left) = max{Sum(k, left), Sum(k, right) + 1}
Sum(i, right) = max{Sum(k, right), Sum(k, left) + 1}
同样可以求出时间

365. Ships of the Desert
Description: 求满足先non-descending再non-ascending的位数为s(s <= 20)的数有多少个
Solution: DP题。
f(i, j)表示长度为i，当前数字为j的non-descending的数有多少个
Ans = f(i, j) * f(k, r)，其中i + k <= s, r < j

366. Computer Game
Description: 给定n(n <= 60000)个儿元组(ai, bi), 0 <= ai, bi <= 50，从中选取k(<= min(n, 20))个，令A=sigma(aki), B=sigma(bki)在满足min(|A – B|)的条件下，max |A + B|。
Solution: DP题。
注意到-50 <= ai – bi <= 50，将元组(ai, bi)按照ai – bi之差分成101种，用F(i, j, k)表示到标号为i的元组，总共选取j个，A – B为k时，最大的|A + B|。则
F(i, j, k) = F(i – 1, r, k – i * (j – r)) + S(i, j – r), r <= j
其中S(i, k)表示选取k个标号位i的元组所能获得的最大值

可能有复杂度更低的算法。

367. Contest
Description: 给定n(n <= 1000)个problem p，pi的解决需要时间为ti，且解决的时刻为罚时，problem之间有拓扑序关系，如果pa为pb的前继，则满足ta<tb，求在时间T内，最多能解决的问题数及相应的最少罚时。
Solution: 注意到如果确定要解决m个问题，则按照需要时间从少到多的顺序解决问题，罚时最少。维护一个heap，不断将没有前继问题的problem加入这个heap，每次弹出解决时间最少的problem，最后所得的就是结果。

read comments (0)

剧透，慎入

正文

所以说看国外影片还是要看原音的，首先那个长成奇怪模样的名字我就记不住。如果是英文的还好，翻成中文了之后完全是几个毫不相干的字拼在一起，而且又长，记起来异常困难。再加上这部电影的情节进展缓慢——人家是爱情文艺片么，于是我毫无悬念的睡着了——不过也就五分钟。

虽然说成为一个女作家在当时是件特立独行的事，不过就开场在一个礼拜类似会上，简给她的姐姐读的一篇自己创作的祝福类似物而言，简的写作确实是有些自以为是——好吧，我们应该以17世纪的眼光看待这篇东西。不过我一直是觉得女性作家总有些局限，一方面是女性的心理特点，一方面是女性的视野比较狭窄。女性作家能够驾驭的题材总感觉比较局限，而且境界普遍不高。一般能够跳出这些框框的女性作家，要不就是有什么异于常人的经历，要么就是天赋迥异——满足这一条的屈指可数。

让我们讲回电影。这部电影的主要情节一个是一位富婆的侄子追求简，一个就是简和一个小律师的爱情。那位侄子向简求婚的第一句话就让我雷住了—— “我一年（？不记得了）有2000英镑的收入。。。”，让我误以为这个人是坏人。直到最后当简私奔未果，而这位绅士尊重简的意愿没有和她结婚的时候，我才悟出来这个天真纯洁的好少年完全是被他的姑姑给教导残了。据猫猫的推论，这位天真纯洁的好少年后来非常可能成为简的长期资助人——那可是女作家被称为神经病的年代啊。泪，果然我没什么眼力，为什么猫猫第一眼就看出那位好少年的好人本质呢？

简的父母就是因为爱情而一起生活，但是拮据的生活让简的母亲不想让简重蹈覆辙。而小律师的舅舅是一个势利眼。于是他们两个除了私奔以外也就没有别的路可走了。正当他们高高兴兴私奔上路时，简偶然发现了小律师的父母给小律师的信件，原来小律师要靠舅舅的资助赡养家人。于是简乘车返回了家，连一句道别也没有。这种自以为是的做法，也不少见。都是自以为作了为当事人好的决定，完全没有考虑当事人的选择，也没有给当事人选择的机会。Remember, it is he who has the right to make the final decision and takes the responsibility, not you.

若干年后的见面，已是物是人非，爱已成往事了。故事中的男女，纵然有些规规矩矩的离经叛道，终究也不过是普通人而已。

read comments (0)

这套题比较水

Highlight

B 对称点解法
C 进制转换
G 中国剩余定理(new)
H 搜索

A CIVIC DILL MIX
罗马数字处理题

B A Foldy but a Goody
这 个题满有意思的。我的做法是求出fold(len, dir),即长度为len，初始方向为dir的点的偏移量和终点方向。然后由fold(len – 1)的对称拼一下。求答案的时候是以2^k一个一个接起来的，注意转角方向，一个初始为L的节点，是以L,U,L,U这样来变化的。
还有一种做法是求对称点

C Give Me an E
进制转换。注意septillion, sextillion两位不可行，要输出0

E Once Around the Lock
规则给的不甚清楚的模拟题。

D Lemmings, Lemmings Everywhere. But Not For Long
模拟题，我的T了，不想改

F A Puzzling problem
字符串+判断是否有割点(都是用的最土的字符串匹配和BFS)

G And Now, a Remainder from Our Sponsor
中国剩余定理

H Target Practice
判共线+搜索
搜索的剪枝第一是注意只过两个点的line是没有必要记下来的
第二是把状态压成long long表示(一个line穿过的points的个数)

read comments (1)

非常水的一套题

Highlight
H 1×2矩形拼4xn矩形的状态压缩DP
I 很麻烦的转dice的题

A Mispelling
Simple Problem

B Conversions
Simple Problem. 单位转换。

C Encoding
Simple Problem

D Decoding
Simple Problem. 是C的对偶题

E Flipping Burned Pancakes
简单题
随便构造一种解法就是了

F Monkey Vines
简单树上DP题
注意在一个数字后读入一个空行的写法

G Model Rocket Height
简单几何题

H Tiling a Grid With Dominoes
DP。注意可以将W的范围改到32-bit integer
这样的话只要求出f[2 ^ k][state1][state2]，就可以在log(W) * (2 ^ 4) ^ 2内做出来。

I Spatial Concepts Test
转dice的题，面的四个方向有标号。有点麻烦。

read comments (0)

这套题还蛮好的

Highlight

3953 – Strange Billboard(new)
二进制运算完成一些操作
3954 – Phone Cell
3955 – Hexagonal Parcels(new)
斯坦纳树
3958 – Weird Numbers(new)
负进制数转换
3959 – Rectangular Polygons(new)
用面积判断是否是clockwise
3962 – Tough Water Level(new)
补偿法算重心

Detail

3953 – Strange Billboard
枚举第一层状态，递推
注意状态和tap tile用二进制运算完成

3954 – Phone Cell
简单几何，给定半径为R的圆，算最多圈住多少个点
以每个点为圆心做圆，然后看与别的圆相交次数最多的面积

3955 – Hexagonal Parcels
斯坦纳树

3956 – Key Task
RxCx(1 << 4)的BFS

3957 – Gates of Logic
复杂的图像处理题
这个题没有仔细想。应该是将图形辨别出来，然后就很好做了

3958 – Weird Numbers
负数进制转换
对于n大于0的情况，将第i位的最大值与用第0~(i-1)位所能构成的最大值相加，如果能不小于n，则n的表示法中第i位不为0

3959 – Rectangular Polygons
简单几何
先按x排序，把所有平行于y的边找出来，再按y排，找出与x平行的边，把图形围出来。
然后用面积法判断是否是clockwise

3960 – Reaux! Sham! Beaux!
Simple Problem

3961 – Robotic Sort
块状链表

3962 – Tough Water Level
先把整个杯子当作实心的算出重心(就在中心)，然后把中间的那块当成密度为负的算重心，然后算出杯子的重心。
最后考虑加入水的重心

read comments (0)

非常水的一套题

Highlight
G Children of the Candy Corn

Details

A Rounders
简单题
B Q
简单题
C Enimatologically Cruciverbalistic
搜索。每次重新统计剩下的词中，possible word最少的一个枚举。
D Blue Jeans
字符串匹配
E Core Wars
麻烦的模拟题
F ‘Roid Rage
几何题。判断两个多边形是否重叠
G Children of the Candy Corn
迷宫(模拟?)题, T了
H Panic Room
最大流

read comments (2)

Highlight

3830 – John(new)
游戏论，nim游戏变种
3834 – Showstopper(new)
利用奇偶性求解
3835 – Highway
Greedy
3837 – The Stable Marriage Problem(new)
稳定婚姻问题

Details

3830 – John
不错的题，不过在Game Theory里面可以找到原题。
nim游戏的变种，具体做法不是很清楚。

3831 – Double Queue
Simple Problem. 要求加入一个priority为k的，弹出priority最大或者最小的item。

3832 – JBC
Simple Problem
转进制的题。

3833 – Loan Scheduling
把所有的app按照deadline先后排序。
加入一个app，如果deadline不变，那么加入是否超上限，如果没有，直接加入，如果不行，而且现有的最小的profit比这个小，就替换掉最小的。
如果deadline变了，把total app的上限加上l.

3834 – Showstopper
满有意思的题。
判totSum的奇偶性，二分区间，直到只剩下一个数为止

3835 – Highway
先把所有的区间找出来，离散掉，Greedy，每个区间看最晚能在什么地方被覆盖掉。

3836 – Computers
DP
f(i, j) = min{f(i, j – 1), f(i – 1, j – 1) + cost}

3837 – The Stable Marriage Problem
稳定婚姻问题

3838 – Arne Saknussemm
排版题。

read comments (0)