The Sun Also Rises

歌手:五月天
歌名:倔强

当我和世界不一样那就让我不一样
坚持对我来说就是以刚克刚
我如果对自己不行如果对自己说谎
即使你不原谅我也不能原谅
最美的愿望一定最疯狂
我就是我自己的神在我活的地方
我和我最后的倔强握紧双手绝对不放
下一站是不是天堂就算失望不能绝望
我和我骄傲的倔强我在风中大声的唱
这一次为自己疯狂就这一次我和我的倔强

对爱我的人别紧张我的固执很善良
我的手越肮脏眼神越是发光
你不在乎我的过往看到了我的翅膀
你说被火烧过才能出现凤凰
逆风的方向更适合飞翔
我不怕千万人阻挡只怕自己投降
我和我最后的倔强握紧双手绝对不放
下一站是不是天堂就算失望不能绝望
我和我骄傲的倔强我在风中大声的唱
这一次为自己疯狂就这一次我和我的倔强
就这一次让我大声唱
lalalala...
就算失望不能绝望...
lalalalala...
就这一次我和我的倔强

Final结束，期中应付掉，GRE开始，和一群同学吃饭联络感情。。。
这周很巧合的发生了太多事情，今晚统计了下，这周大概总共fb了5次。。。一方面有同学google intern归来要bg，一方面有各种各样的活动，然后某同学的本本又很是时机的出问题了跑来找我 plus bg我。。。～～～


收到邮件问关于实验室的。。。心想最近一直是最后时刻把事情赶掉，sigh。。。不知道怎么办中。。。怀念预科的时光。。。。
感觉我的性格真的不太适合赶事情。。。

感觉还是比较容易浮躁。。。
比如今晚边背GRE边不小心在那想代数结构的作业还没写。。。
算是一直困扰我的问题。。。
我很喜欢我的某个状态，
记得预科的时候，没什么事情的时候，一个人躲在3109A，安静的看着本数分书（当然。。。换现在的的话，可能会在那安静的看着《数学：确定性的丧失》或者《实践理性批判》之类。。。～）
但，我知道，即使是事情多的时候，我确实可以做到，忙而不乱，
很专注的做着当前应该作的事情，
虽然有很多很多事情，但可以有条不紊的安排好，
然后冷静的放弃一些相对不重要的事情（或者降低相应的标准）
保持好心情，与必要的休息～

可惜，很多时候，还是容易乱掉呢。
忘了去作很多必须作的事情（例如 保持运动、保持心情与休息～），
或者是，拼命想把所有的事情，都能够作掉。。。
一般说来，由于没有安排好休息，所以可能会发生，一段时间做了120%的事情。
接下来一段时间，什么事情都作不了，只能作40%的事情。。。

anyway...我猜。。。总是可以不断进步的吧。
人生么，总不可能，都是没什么事情的么，
总归长大了，会有无穷多的事情，而永远不可能做完。


5.25 还有个TC华东地区摸鱼大赛～～～按照初赛的成绩发奖就赚大了～～～。。。
不想参加今年baidu了，分精力啊。。。

---

另外。
其实我猜，摄影，是记录感动的方式呢。
所以。。。我其实还是比较喜欢拍风景的。。。
恩，如果说，我拍风景，更像随便拍拍的话。
我猜，是你和我，对于生活的体验，
不一样呢。

--翻出banff镇的某幢房子的照片后记。。。～

最终整理完成～～～注释注入～～～
比较伤感的是照片seems乱序了。。。所以有些前两天的照片跑到后面去了，最后2天的照片跑到前面去了～～～

感觉比较奇怪的电影。。。

p.s. 其实我个人觉得比较怪的是那个罪犯怎么会预先知道mills很容易愤怒。。。
而且我觉得罪犯居然还自称只是犯了envy的罪。。。不晓得他圣经怎么读的。。。你看不是说“免我们的罪，如同我们免了人的罪”，此人一定不会背主祷文～～～你看他的diary，完全就没有一点abide的成分。。。

。。。而且。。。我记得好像有说只有上帝才能judge人。。。
还是他自认是上帝的某一个“四位一体”的神。。。所以他可以选择judge人？。。。恩。。。理论上还是能说通的，你看先跑来一个上帝的某个reference之耶稣，用自己的来替世人赎罪。。。然后跑来另一个reference，用血腥的行为来使世人警醒？。。。
可惜。。。他最后还是犯了envy的罪。。。所以他不可能是上帝的第四位一体。。。

结论是读bible还是很有必要的。。。你看要我是mills我一定和他discuss holy bible去了。。。恩。。。～～～



最后是Seven Sins from wikipeida
链接应该是invalid的，大家细节不要太在意。

Listed in the same order used by both Pope Gregory the Great in the 6th Century AD, and later by Dante Alighieri in his epic poem The Divine Comedy, the seven deadly sins are as follows: Luxuria (extravagance, later lust), Gula (gluttony), Avaritia (greed), Acedia (sloth), Ira (wrath), Invidia (envy), and Superbia (pride). Each of the seven deadly sins has an opposite among the corresponding seven holy virtues (sometimes also referred to as the contrary virtues). In parallel order to the sins they oppose, the seven holy virtues are chastity, abstinence, temperance, diligence, patience, kindness, and humility.

Retrospect only, some algorithms may be wrong...
Warning : 剧透慎入...

Andrew Stankevich's Contest #1
Chinese Girls' Amusement
推结论直接算
Reactor Cooling
有上下界的环形流
New Year Bonus Grant
经典的树形DP
Matrix Multiplication
化简一下推结论
Nice Patterns Strike Back  (Recommend)
状态压缩DP后用matrix来优化，或者用上次monthly时LK的方法。
Get Out! (Recommend)
可以用那个生成环的基的DFS,类似japan那道题。
Beautiful People
最长虾米序列，8过稍微有个细节要想
Cracking' RSA (Recommend)
求bool方程组的解数。。。也就是求下自由变量个数


Andrew Stankevich's Contest #2
Non Absorbing DFA
记得是个很正常的DP。
The Towers of Hanoi Revisited
经典的n个塔的hanoi，记得要DP...
Hyperhuffman
就是huffman问题吧，已经排好序，可以O(n)的。
Little Jumper (Recommend)
不错的物理题
首先可以想象成两只青蛙一起从两边跳。
主要问题就是计算给定一个v后的青蛙可达区间。
取到最值只有3种情况：从上面擦过，从下面擦过，45度起跳（如果可以）
Quantization Problem
又是一个正常的DP...
Roads
经典问题了。
生成树上的权值必定是减少，其他边上的权值必定增大，设其分别为ai, bj
然后对任意一条不在生成树上的边，加入到生成树上形成一个环，然后这条边的权值应当>=环上所有边的权值。
然后我们可以列出一堆形如ai + bj >= 一个正数的不等式。。。然后。。。km算法的标顶~~~
详情可以看km算法的证明~~~
Robbers
首先令k[i] = m * x[i] / y，取下整，然后可能k[i]的和不到m，要增加一些k[i]，当然是，每次找增大后delta最小的~~~
主要是，似乎可以用heap优化为O(nlogn)。。。
Toral Tickets (Recommended)
比较神奇的Polya

Andrew Stankevich's Contest #3
Areas (Recommended)
我的做法是基于半平面交的，对每条直线，枚举使用它左边的半平面还是右边的半平面，最后如果是一个有限平面则返回。。。
注意搜索过程中当半平面被切空后就可以return，由于最后只有O(n^2)块，所以复杂度是O(n^4)的（使用O(n^2)的半平面交）
SGU上时限很宽，ZJU上这么做时间有点紧（我0.95s AC的-_-bbbbbbb）
Beloved Sons
按偏爱程度从大到小找增广路跑max_match就可以了。。。
Strange Counter
构造
维护这么一个性质两个2之间至少有一个0。。。然后。。。讨论。。。
Data Transmission (In List)
据说是预流 + 使劲优化...(by Lunarmony)
Strong Defence
嗯，首先颜色数不会超过任何一条路的长度是把。。。所以颜色数至多就是最短路的长度。
然后我们跑dijstra的时候把边着上颜色就是了。。。
Weird Dissimilarity
经典的DP
PL/Cool
据说是模拟(from oibh)。。。
Royal Federation (In List)
据说是构造, not AC yet.
Two Cylinders
写出积分式后romberg.

Andrew Stankevich's Contest #4
The Smart Bomb
简单的推一下。
I Just Called ...
模拟，要用Trie树。
Order-Preserving Codes
模仿huffman那样，只是每次merge相邻的。
More Divisors
经典的DP, f[i][j]用前i个素数得到j个约数的最小数。。。
Long Dominoes
状态压缩DP
The Magic Wheel
应该选择第一个点，然后寻找下一层的两个方向最近的都试一下就行了。O(N)
Cracking SSH
DP...
Periodic Tilings
好像某年final有类似的题。应该有结论的说。
Not AC yet
Trade (In List)
Not AC yet, 可以看看
Counting Triangulations (Recommended)
一道还算不错的DP题，8过题目描述好像有点不清我记得。
Unfair Contest
搜索+模拟


Andrew Stankevich's Contest #5
Unique Attack (Recommended)
判断最小割是否唯一的题，就是用两种方法构造是否一样。
Burning Bridges
ms是很经典的用桥来作的题
Circles
经典的平面图欧拉公式题
Linear Programming Dual
好象是线性规划，Not AC yet
DVD (In List)
相当容易写错的DP题。
Think Positive
记得可以O(n)扫描的。
Ranking
麻烦的模拟题。
Driving Straight
也是很经典的思路了，先DP(或曰BFS)。然后走一遍，在满足有解的前提下尽量往那个方向走。

Andrew Stankevich's Contest #6
Ackerman's Function (Recommended)
可以认为是找规律
The Minimal Angle
记得要O(n)，取平均数还是什么都可以。
Yellow Code
我记得还是比较容易YY一个构造的。。。
Yet Another Digit
DP吧。
Graduated Lexicographical Ordering (In List)
类似于vietnam的那道题。。。相当麻烦。。。建议实现下。。。
GSM
高精度开方题。或者打表～
Warehouse Keeper (In List)
KM,8过我记得容易T?
Don't Go Left
记得又是一个状态机的BFS题
Railroad Sort
很有意思的构造，大体思路是每经过一个station，留住后一半，放行前一半。。。n个正好给2^n个数排序。

Andrew Stankevich's Contest #7
Little Brackets
经典的dp, NOI陨石的秘密简化版。。。
f[n][k] = n对括号，<=k层
f[n][k] = sigma(f[m][k] * f[n - m - 1][k - 1])，输出f[n][k] - f[n][k - 1]
就是每次添加一整个括号块。
Under Control (In List)
转换坐标离散化吧
类似思路有道超级复杂版Soldier
Holidays (In List)
Not AC Yet
Laboratory
记得列出式子调整下就行了。时限吓人的～
Maps
Crazy Painter
Puzzle
没记错的话BFS一下吧。。。
Quest
经典的状态压缩BFS，输方案有点麻烦。。。
Stable Sets

[Solution] Tokyo 2007

And Then There Was One
经典题，递推。

Prime Gap
简单题

Minimal Backgammon
DP

Lowest Pyramid
比较麻烦的题目，大体做法是枚举一个点，根据距离相等可以枚举另一个点（这些点很少了），然后确定下最后一个点，check.

Geometric Map
比较麻烦的预处理 + dijstra

Slim Span
经典问题了，按边大小排序，每次加一条边，如果形成环去掉环上最小的边。check

The Morning after Halloween
BFS，最后用A*过掉的。用max(当前位置到目标位置)估价

Bug Hunt
简单模拟

Most Distant Point from the Sea
可以用二分＋半平面交。
但也可以想象所有边朝里面挤压，这样最后要么是两条边压到一起，要么三条边压成一个点。O(n^3)枚举。

The Teacher's Side of Math
注意到p,q都是质数，所以答案是0必须是所有其他项系数全为0，这样就可以解方程了。
用long double + 最大主元法可以过。

[Solution] SWERC 2007 Southwestern Europe
比较简单，有些题读题比较郁闷。

BEATBIT
两DFA是否同构，bfs or 判断树是否同构都可以（因为保证了可以终止所以没有环存在）

Prester John
题意没说清，走路的方式类似于NFA, BFS就行了。
不过可以出个数据让所有程序T...

Robotruck
O(N*C)的DP

Jumping Hero
BFS，最多300 * 300 * 5000 * 5种状态，当然实际上远远不到。

Board Game
Bellman-Ford

The Bridges of Kolsberg
经典DP

The Finest Chef
最优权匹配

IP-TV
MST

Ladies' Choice
稳定婚姻

[Solution] Dhaka 2007

Bachelor Arithmetic
秒杀题

Nested Squares
模拟题

The Dumb Grocer
首先要有1是吧。。。然后我们按照1的个数来分类，我们来计算恰有k个1的方案数。
我们在k个1的基础上加入新的数，显然第一个数只能是k+1
然后加入的数只能是k + 1 or 2 * (k + 1)
如法炮制。。。发现非1的数都具有(k + 1) * t的形式。。。设其依次为(k + 1) * ti
则{ti}这些数也满足题目的性质。。。共有f((n - k) / (k + 1))种方案。

设f(n)是要求的函数，则f(n) = sigma(f((n - k) / (k + 1)), (k + 1) | (n + 1) , k>=1
f(0) = 1
这样直接做会T...
我们令g(n) = f(n - 1)
则g(n) = f(n - 1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n / (k + 1)), (k + 1) | n, k >= 1
设n = p1^a1 * p2^a2 * ... * pr*ar
令h(p1, p2,.., pr, a1, a2...ar) = g(n)
= h(p1,p2, ...pr, b1, b2, ...br),
0<=bi <= ai, bi不全=ai
注意对于一个确定的n，h()中的p1, p2...pr在计算过程中始终不变。。。所以。。。计算结果与pi无关,只与ai有关
这样状态数就大大减少了。。。直接因式分解后dp就行了。。。

ACM Puzzles
状态压缩dp

Inspector's Dilemma、The Bells are Ringing、 Photographic Tour
这三题好像当时没写summary。。。所以我们假设比较简单～～～

You are around me ...
首先旋转坐标，变成平行与xy轴的椭圆，然后坐标伸缩。。。变成圆。。。最近点对。。。贴模板。。。
ZJU2107 Quoit Design 一道测最近点对的题。

Infinite Matrix
显然，对于固定的j, Ri, j是一个关于i的多项式。
注意到数列Ri, j的差分序列R(i + 1, j) - R(i, j)是可以求出来的（利用Mj, k <= 10的条件，可以在O(10*n^2)的时间内算出）
然后有了差分序列求通项就是O(n^2)的事情。
然后记S(p, j)(n) = Sigma(i^p * R(i, j)) i <= n
继续利用差分序列之类的方法求这个，最后再求一个Sum_S(p, j)
预处理复杂度大致是O(10*n^3)的。
后面的就好办了，对每个询问，把(i + 1)^p二项式展开，最多10项，然后利用公式直接计算。
处理询问复杂度O(p*q*n)
POJ3529 Matrix Analysis，类似的思想，更简单～

Magnetic Train Tracks
给定n个点，求可以构成多少个锐角三角形。
n <= 1200
话说求锐角三角形不太好算是吧。。。补集转换，我们来求钝角/直角三角形 <=> 求钝角/直角个数。。。
后面的事情就简单了，是对每个点，将其他点按照极角排序 + 扫描。
Dhaka 2005 Counting Triangles 也是一道补集转换的题～（转化成求三点共线的个数）
Shanghai 2004 Amphiphilic Carbon Molecules 也是一道极角排序+扫描的题。

朽木露琪亚果然很帅啊。。传说中冰雪系最PP的斩破刃。
（冰雪系最强的ms是小白的）

始解第三式
「叄舞・白刃」
当剑被敌人斩开，分成两段而不能攻击，此招式能使剑刃再生，回复原状。曾在被第9十刃刺穿身体时，以此招还击并成功击败对方。

感觉有一种即使断裂，依然可以重生的感觉哈。

我觉得我应该有一段时间，已经很少说这个词了吧。

不过，毕竟发生了太多的事情。
Final结束，CSAPP && 代数结构考掉，GRE还完全没开始，一些过去的事情纠结，未来的事情谜茫。
A little pain.



不过我想，
我毕竟不仅仅是为了舒服或者开心而活着。（虽然开心是很重要的事情）



p.s.
请学会宽容和原谅，包括别人、自己，客观环境，外在事物，以及内在想法。
如果一下子感觉很难产生那份空间，将其容纳进来，
至少我，可以选择停止那些批判，并，暂时遗忘这件事。