[CF 294D]Shaass and Painter Robot解题报告

题意 有一个n*m的网格,有一个机器人初始在(x,y),面朝某个斜45°的方向。机器人会一直走,遇到墙就按弹性碰撞规则(就像台球碰到桌子边缘一样)反弹。机器人每走一格,就会将其所在格子染黑。问机器人走几格之后会将整张网格染成黑白相间(或判断这种情况永远不会发生)。 分析 首先有一个结论:边缘上所有该染黑的格子都已染黑,当且仅当整张网格已按要求染成黑白相间。 证法是归纳。假设第一行该染黑的格子都已染 … 继续阅读“[CF 294D]Shaass and Painter Robot解题报告”

[CF 329E]Evil题解翻译

题解翻译 这道题的解法实际上非常简单:http://codeforces.com/contest/329/submission/4122927 这道题要求我们证明一大堆东西(下面的证明超过80行)。 假设n>=4.显然nC,C->B,A->D,D->A。这里,点的配对是显然的,A和D配对,同样B和C配对。 首先,如果A+D为空或B+C为空,我们就一定能得到上述上界。我们可以简单地交替选择剩下两个配 … 继续阅读“[CF 329E]Evil题解翻译”

[CF 343E]Pumping Stations解题报告

题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1994 题解 首先,有一个东西叫Gomory-Hu(戈莫里-胡)树。就是说,对于一张题中这样的图可以建出来一棵树,使得图中s~t的最小割等于树中s~t路径上的最小边权。 那么问题来了:怎么建树呢? 有两篇资料: Wiki百科: http://en.wikipedia.org/wiki/Gomory … 继续阅读“[CF 343E]Pumping Stations解题报告”

CTSC&APIO2015游记

5.3 这天报道…… 下午和@Asm.Def @Chenyao @CJJ 跑去北海公园旅游 本来准备去上机的……结果走到人大门口地图处发现道路阻且长(要从人大的东南部越过山和大海到西北部),不如高卧且加餐……加餐……然后果断转身上地铁,北海公园走你┏ (゜ω゜)=☞ 当天风儿非常的喧嚣,被吹了一脸…… 看到了传说中的白塔……“四周环绕着绿树红墙”……以及奇怪的北京小学生作文展,还有约一个排的武警拿 … 继续阅读“CTSC&APIO2015游记”