Problem E. Shaass the Great
Brief description:
。。。给定一颗边权树。。你可以移动任意一条边。。只要新图仍然是一颗树。。
。。。最小化。所有点对之间的距离的和。
(。。n = 5000。。。)
Analysis:
。。。枚举每一条要移动的边。。那么显然要接到这两棵子树的重心（所有结点到该点的距离和最小）上去。
http://codeforces.com/contest/294/submission/3501355
（。。。比赛时读完题目就想到了重心。。然后一直试图往并查集方面靠。。居然认为是不可做题我是多弱啊。。。
。。。虽然现在也没搞出 O(nlogn) 算法。。。sad。。。）
Problem D. Shaass and Painter Robot
Brief description:
..在一个 n*m 的格点上。。有一个在初始位置 (x, y)。。只会斜着走。。撞墙以后遵从反射定律的。。会把所有途径的格子染成黑色的机器人。。。
。。。问是否能将格点染成棋盘图案。。如果可以。问至少需要走多少步。。。
（..n,m = 10^5, 机器人初始位置一定是黑色格子。。且在边界上。。）
Analysis:
… 因为出发点是在边界上。（如果不是可以让机器人先退几步。。转化成在边界上的情况。。）。。容易想到一个结论。。。
。。只要所有边界格子都被染色。。那么所有格子就已经被染色。。。
http://codeforces.com/contest/294/submission/3500749
。。必要性显然。。充分性可以对格子归纳得到。。有解的情况下。每个边界格点至多进出两次。。于是就可以当成 O(n+m) 的大模拟来写了。。。
——————
当然和 DukeOnLargeChessBoard 相比这个实在是弱爆了。。（这题比赛时我能想出来？？
Problem C. Shaass and Painter Robot
Brief description:
。。给定一个 0/1 串。。表示灯泡。。。如果一个灯泡的相邻位置有一个亮着的那么可以点亮它。。。
。。计数点亮所有灯的方案数。。。
Analysis:
。。。唯一在比赛时动手写的题目。。很容易想到分解成。。0000/1111/000 … 0/1111/0000 。。。。 这样的 0/1 段。。
。。。那么除两侧以外 0000 每一步是要考虑从左边进发还是从右边进发的。。。此处的因子是 。。2^(s-1)，s 表示长度。。。
。。除此之外还要乘以一个总的多项式系数。。。
。。比赛时写了一个巨生的 Ocaml。。 而且天真的认为函数式语言会自动记忆 comb 这种递归函数。。。结果看了 Professor 的码发现他是预处理二项式系数的。。。-.-。。（那我为什么要用 Ocaml 啊。。。
http://codeforces.com/contest/294/submission/3485735
高下立判啊！。。
Postscript :
。。。blog 这个月一定要搬到 Linode 下去了。。。（。。其实上上个月就要搬了。。但是我各种不会。。。拖到现在。。每拖一个月我都要损失 9$ 要不要这样。。。。。。
。。。解题报告部分一直想搬运到 Github 上去。。然后 markdone。。。。特别是 TC/CF/CC 这些常规赛。。。。但是一直还没弄妥。。。。不知道要坑多久。。。
。。（。。所以现在找 TC/CF 解题报告请去看 AFAIK 吧。。。比我这边现在要良心多了。。我这边暂时就把 LYP 没写的几篇给补上好了、、。。。
以上。。。
