某岛

… : "…アッカリ~ン . .. . " .. .
October 18, 2012

Codeforces Round #145

Live:
A [统计。。] B[动态规划。。] C[SB 构造。。] 。。D。。[adhoc]。。E [问至少修复多少条边可以使得图变为指定源点的树形图。。]。。F [疑似26棵线段树乱搞?。]。。

D. 有向图,保证两点之间不会有两个方向的边。。边分为实边和虚边。。
。。问至少修复多少条虚边可以使得该图,变为指定源点的树形图。。。

。现场生一直纠结于要不要拍树形图,(但是发现其实已经不会了。。树形图也是可过的。。参见 CLJ 的代码。。
。。。之后发现强连通缩点之后贪心也是可以做的。。
方法是先进行缩点(实边)。然后只需要考察那些引向入度为 0 的点的虚边。。
。。最后把这两类边放在一起执行一次 bfs() 即可。

http://codeforces.com/contest/240/submission/2381649

E. 给定一个字符串,每次操作 (l, r),将该串的 (l, r) 位置重排,
形成一个字典序最小的回文串(如果无法形成则忽略)。。问最后字符串变成什么样了。

。。其实算法很简单。就是 26 棵线段树暴力维护。。
现场生一直纠结于有没有一种比较简单的实现。。结果最后连拍都没拍完。。
(读了一下 rng_58 的代码。。然后发现因为每个点只有 0/1 两种状态,所以可以直接用累和的数组简化标记下放。。Orz。。

http://codeforces.com/contest/240/submission/2381889

。还有那么多解题报告没补怎么办。。(救命呀。。>_<

External link:

http://codeforces.com/blog/entry/5531
http://blog.renren.com/blog/271960376/876328651