Record My Thoughts
淅沥的雨思
像那六弦琴
它叮叮咚咚
是那么动听
斑驳的树影
像梦的森林
引领我走进
五彩的神秘
满天的繁星
掩藏我点点的密秘
胡：夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜
满天的繁星
掩藏我点点的密秘
夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜
满天的繁星
掩藏我点点的密秘
夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜
Da da da da da……
有梦好甜蜜
跌跌撞撞地终于到了final前，终究是想写点什么。
距离上一次去St. Petersburg的VK Cup已经快一年了。当时我还是一个充满热血的大一小朋友，而现在已经是快要搬去玉泉的老家伙了，想想真是令人潸然泪下。记得当时看到WJMZBMR、shangjingbo、7k+、squark、tourist等等神牛真是内心激动，难以言表啊。嗯，我还记得玩那个开车的AI大赛WJMZBMR用那个轮胎道具的一箭双雕，简直是炸天。然后我写的AI策略是假如有两个人比我离那个道具更近，就果断放弃去吃别的道具。然后这样的逃兵流搞法竟然还赢了tourist一场……最后好像还水进了半决赛。XD
当时是第一次出国，看着外面的世界，越发觉得自己的渺小。手里的资本，大概就只有年轻了吧。
暑期校队选拔以后半推半就地被骗进了1队……于是也顺理成章地当了队长。这绝对是改变我人生轨迹的一件事情。在此之前，OI和ACM的界限其实并没有那么明显，至多是术业有专攻，技能可以互补这样子。但是自从当了队长……就深切感受到原来真的随时可以1+1+1 < 1。不应该再像以前那样只关注自己手上的事情，谁手上卡着什么东西得主动去了解，要根据每个人的状态和情况去想现在该干什么，必要时果断打断队友/自己手头上的事情。确切来说就是关注的点从自己手头上的事扩散到了队友和别的一些东西上。
有时候人和人之间的方法论和世界观的差异是巨大的，也正因为如此才有互补一说。当队长的判断和队员的判断不一致的时候，询问队员有多少把握往往是比较好的方法。但是一定要限定时间，因为只要是人，就可能有判断上的失误。如果一段时间以后感觉这样不对，就必须果断打断。
很多时候人会舍不得自己曾经付出过的努力，总觉得已经付出了这么多，就差一点了，然而其实这一点所耗费的时间其实很可能是不可接受的。甚至从一开始就完全错了。浪子回头，为时不晚。
其实据说我们是史上最圡的1队，因为别的1队从来没有在组队训练的时候被2队~5队都踩过:) (咱们这叫挥发度好吗T_T)
在中大和复旦出题的赛区都季军了，但是两个北大的赛区金牌都没拿到，再次被2队~5队都踩成狗了……(= =b幸好都打星了)。这大概说明了我们基本功和模板真的不够扎实吧……
也许我就是这么一个谨慎(又名想太多)的人，已经不知道多少次我觉得铁定TLE苦思冥想结果被prowindy用最简单的方法直接搞过……Regional成都那一站，有一道就是因为算错复杂度(应该用积分算的555)，自己骗自己，结果一个简单的枚举，搞得前面的队伍里面就我们到最后也没过。不然随便弄一个几行的枚举上去就亚军了，那一场其实是我们唯一一次可能夺冠的机会，因为我死磕磕出了一道冠亚军都没idea的字符串，但最后还是输给了胆量和基本功。
最后装下文艺青年：今当远离，临表涕零，不知所言。
gcj 必跪定律……
250pt
找规律……
比较瞎的是官方题解也是这么干的。
找规律，然后用数学归纳法证明这个规律的……
500pt
算期望的好题，用矩阵混过去的，2*10^7次double运算居然TLE了。
注意利用期望的累加性质和线性性质就好。
1000pt
经典的拆点网络流，题目给定了黑白格染色，然后再把白格按所在行的奇偶性再染色一次色，就可以流了。
-.-总之网络流或者最小割的关键还是于2这个数字。要么A要么B。
250pt
略，小心写就好。
500pt
给一个8 * 8的方格，某些格子为#要填东西。每次填一个格子，cost是已填格子里离本格子Manhattan distance最远的点的Manhattan distance。问填出给定的pattern最少需要的代价。
一个奇怪的技巧，Manhattan distance将坐标旋转45°((x,y) -> (x + y, x – y) ———— 记为(p, q))以后，就从
$$abs(x_1 – x_2) + abs(y_1 – y_2)$$ 变为 $$max(abs(p_1 – p_2), abs(q_1 – q_2))$$
因为从+变成了max，所以可以dp了……因为只需要记录已填区域的minx, maxx, miny, maxy就可以转移。
1000pt
给定一个pattern，某些地方要涂上颜色，每次可以用一横或者一竖将一系列没有被涂过颜色的点涂上色。问最少要涂多少笔。
-_-官方题解的建图看着真是太挫了……
关键就在于要给每个要涂色的点分一个状态Down或Right. 而如果我是Down，下面不是一个为Down的点(没有也不算是)，那么ans++，如果我是Right，但右边的点不是Right(没有也不算是)，ans++。
所以假设每个格子对应一个点，他被割在S一边表示Down的状态，割在T一边表示Right的状态，那么建边就像这样。
rep (i, m) rep (j, n) {
if (target[i][j] != '#') continue;
if (i + 1 < m && target[i + 1][j] == '#') {
addedge(id[i][j], id[i + 1][j], 1);
} else {
addedge(id[i][j], T, 1);
}
if (j + 1 < n && target[i][j + 1] == '#') {
addedge(id[i][j + 1], id[i][j], 1);
} else {
addedge(S, id[i][j], 1);
}
}
跑一遍最小割就可以得到答案。