2016-E20-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||Run ID||Submit Time||Problem||Language||Result||Time||Memory||
||22054119||2016-11-05 13:52:55||H - Hockey Cup||GNU C++11||Accepted||30 ms||0 KB||
||22054002||2016-11-05 13:47:30||H - Hockey Cup||GNU C++11||Wrong answer on test 12||15 ms||0 KB||
||22053753||2016-11-05 13:34:13||H - Hockey Cup||GNU C++11||Wrong answer on test 12||15 ms||0 KB||
||22053067||2016-11-05 12:56:49||F - Format||GNU C++11||Accepted||15 ms||100 KB||
||22052984||2016-11-05 12:52:34||F - Format||GNU C++11||Wrong answer on test 20||15 ms||100 KB||
||22052031||2016-11-05 12:00:55||K - Knights of the Old Republic||GNU C++11||Accepted||295 ms||30500 KB||
||22051724||2016-11-05 11:44:29||E - Economy Printing||GNU C++11||Accepted||140 ms||27200 KB||
||22050588||2016-11-05 10:44:03||G - Great Guest Gathering||GNU C++11||Accepted||30 ms||24400 KB||
||22049948||2016-11-05 10:06:02||G - Great Guest Gathering||GNU C++11||Wrong answer on test 1||0 ms||20000 KB||
||22049878||2016-11-05 10:03:05||G - Great Guest Gathering||GNU C++11||Runtime error on test 1||0 ms||19900 KB||
||22049686||2016-11-05 09:48:23||L - Lazy Coordinator||GNU C++11||Accepted||202 ms||11700 KB||
||22049596||2016-11-05 09:39:44||B - Blocking Buffer||GNU C++11||Accepted||15 ms||0 KB||
||22049527||2016-11-05 09:33:11||A - Altitude||GNU C++11||Accepted||46 ms||1400 KB||

start at 13:00

比赛链接: http://codeforces.com/gym/101137

== 流水账 ==

== 总结 ==

== 题解 ==


=== A. Altitude [sfiction] ===

按aj从大到小枚举j，用一个循环双端链表维护前驱后继。

=== B. Blocking Buffer [JTJL] ===

let x = gcd(w, r), check whether (r/x-1)*x>l-w

=== E. Economy Printing [sfiction] ===

首先排序。dp[i][s1][s2]表示前i个数，i-1状态s1，i状态s2的最小长度。其中s1,s2=0..2，分别表示独立、+1连续、+2连续。枚举i+1状态进行转移即可。

=== F. Format [JTJL] ===

打牌，注意non-empty

=== G. Great Guest Gathering [JTJL] ===

欧拉回路

=== H. Hockey Cup [sfiction] ===

枚举得分然后模拟。0.100应该能覆盖3&4关键字。注意得分不能相同，OT时要保证分差为1。

=== K. Knights of the Old Republic [Akalm] ===

一开始先把所有点视为孤立并计算局面代价，然后像做mst那样将边从小到大逐一加进图里动态维护答案。

=== L. Lazy Coordinator [Akalm] ===

倒着算一遍每个时间点存活长度期望就好。

== 补题 ==

CDIJ

Run ID	Submit Time	Problem	Language	Result	Time	Memory
22054119	2016-11-05 13:52:55	H - Hockey Cup	GNU C++11	Accepted	30 ms	0 KB
22054002	2016-11-05 13:47:30	H - Hockey Cup	GNU C++11	Wrong answer on test 12	15 ms	0 KB
22053753	2016-11-05 13:34:13	H - Hockey Cup	GNU C++11	Wrong answer on test 12	15 ms	0 KB
22053067	2016-11-05 12:56:49	F - Format	GNU C++11	Accepted	15 ms	100 KB
22052984	2016-11-05 12:52:34	F - Format	GNU C++11	Wrong answer on test 20	15 ms	100 KB
22052031	2016-11-05 12:00:55	K - Knights of the Old Republic	GNU C++11	Accepted	295 ms	30500 KB
22051724	2016-11-05 11:44:29	E - Economy Printing	GNU C++11	Accepted	140 ms	27200 KB
22050588	2016-11-05 10:44:03	G - Great Guest Gathering	GNU C++11	Accepted	30 ms	24400 KB
22049948	2016-11-05 10:06:02	G - Great Guest Gathering	GNU C++11	Wrong answer on test 1	0 ms	20000 KB
22049878	2016-11-05 10:03:05	G - Great Guest Gathering	GNU C++11	Runtime error on test 1	0 ms	19900 KB
22049686	2016-11-05 09:48:23	L - Lazy Coordinator	GNU C++11	Accepted	202 ms	11700 KB
22049596	2016-11-05 09:39:44	B - Blocking Buffer	GNU C++11	Accepted	15 ms	0 KB
22049527	2016-11-05 09:33:11	A - Altitude	GNU C++11	Accepted	46 ms	1400 KB

start at 13:00

比赛链接: http://codeforces.com/gym/101137

流水账

总结

题解

A. Altitude [sfiction]

按aj从大到小枚举j，用一个循环双端链表维护前驱后继。

B. Blocking Buffer [JTJL]

let x = gcd(w, r), check whether (r/x-1)*x>l-w

E. Economy Printing [sfiction]

首先排序。dp[i][s1][s2]表示前i个数，i-1状态s1，i状态s2的最小长度。其中s1,s2=0..2，分别表示独立、+1连续、+2连续。枚举i+1状态进行转移即可。

F. Format [JTJL]

打牌，注意non-empty

G. Great Guest Gathering [JTJL]

欧拉回路

H. Hockey Cup [sfiction]

枚举得分然后模拟。0.100应该能覆盖3&4关键字。注意得分不能相同，OT时要保证分差为1。

K. Knights of the Old Republic [Akalm]

一开始先把所有点视为孤立并计算局面代价，然后像做mst那样将边从小到大逐一加进图里动态维护答案。

L. Lazy Coordinator [Akalm]

倒着算一遍每个时间点存活长度期望就好。

补题

CDIJ