2016-E18-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||
||814||4:59:42||1848||A||g++0x||Wrong answer||6||
||813||4:59:29||1849||A||g++0x||Time-limit exceeded||6||
||812||4:59:16||1849||A||g++0x||Time-limit exceeded||6||
||811||4:58:35||1849||A||g++0x||Time-limit exceeded||6||
||810||4:57:43||1848||A||g++0x||Wrong answer||6||
||809||4:56:36||1848||A||g++0x||Wrong answer||6||
||808||4:54:18||1760||A||g++0x||Time-limit exceeded||6||
||807||4:53:45||1761||A||g++0x||Memory limit exceeded||6||
||806||4:53:27||1760||A||g++0x||Memory limit exceeded||6||
||805||4:52:58||1760||A||g++0x||Time-limit exceeded||6||
||804||4:52:00||1763||A||g++0x||Time-limit exceeded||6||
||803||4:50:46||1763||A||g++0x||Time-limit exceeded||6||
||802||4:49:45||1764||A||g++0x||Memory limit exceeded||6||
||801||4:48:30||1769||A||g++0x||Memory limit exceeded||6||
||800||4:47:06||1727||A||g++0x||Memory limit exceeded||6||
||799||4:46:31||1735||A||g++0x||Time-limit exceeded||5||
||798||4:40:26||1722||A||g++0x||Wrong answer||5||
||797||4:38:08||1717||A||g++0x||Wrong answer||5||
||796||4:19:08||1420||B||g++0x||OK||N/A||
||795||4:06:01||1418||B||g++0x||Wrong answer||4||
||794||3:02:13||2523||J||g++0x||OK||N/A||
||793||2:39:58||3528||G||g++0x||OK||N/A||
||792||2:33:19||1671||D||g++0x||OK||N/A||
||791||2:17:46||3310||G||g++0x||Wrong answer||33||
||790||2:05:40||3279||G||g++0x||Wrong answer||33||
||789||1:51:29||847||J||g++0x||Time-limit exceeded||6||
||788||1:40:40||2808||G||g++0x||Wrong answer||25||
||787||1:06:50||976||C||g++0x||OK||N/A||
||786||0:55:10||1588||I||g++0x||OK||N/A||
||785||0:32:39||1298||E||g++0x||OK||N/A||
||784||0:22:18||847||F||g++0x||OK||N/A||
||783||0:15:33||825||F||g++0x||Wrong answer||5||
||782||0:11:51||817||F||g++0x||Wrong answer||5||

Start at 18:20

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006280

== 流水账 ==

== 总结 ==

=== sfiction ===

前期除了 F 之外还算顺利。中期 G 题因为各种细节卡了一个小时，J 则是因为读错题浪费了十分钟，并多等了一个小时。后期题目里，B 过得有点迷……K 题正确题意不难，基本上想到树分治就能做了，可能还是因为过的人少，没有细想。A 最后还差第二部分的 DP 不会处理……H 则是基本没什么想法。

=== JTJL ===

实名反对楼上，前期的F过得挺不顺利的…… ~~B也很科学的嘛~~，树分治的锅修好了真是太好了！

== 题解 ==

=== A. Fancy Antiques [Akalm] ===

把店看作点，商品看成边，抠掉sz有下限的带权最大团即可。

=== B. Alternative Bracket Notation [JTJL] ===

迭代。

=== C. Greetings! [sfiction] ===

暴力状压DP。

=== D. Programming Team [Akalm] ===

二分答案，设c[u] = a[u] - ans*b[u]，树dp找权值和最大子树。

=== E. K-Inversions [sfiction] ===

暴力NTT。

=== F. Mountain Scenes [JTJL] ===

DP。注意 n/w 和 h 的大小关系。

=== G. Symmetry [JTJL] ===

分类讨论，注意对称轴可能不是任意两点的中垂线。

=== H. Jewel Thief [Akalm] ===

按同种质量合并后dp，可以用单调队列优化。

sfiction: 首先合并同代价物品，显然同代价应该先取高收益，之后暴力DP可以得到O(K^2^logS)的做法。只考虑一个阶段，且假设s=1，设状态f[i]为大小为i的背包的最大收益，而不是恰好为i所得最大收益。转移函数f[i]=max(f[i-j]+sum(a[1..j]))。设g[j]=sum(a[1..j])，容易发现g是单调递增的凸函数。这类问题有一种通用的优化方法，可以将复杂度从O(n^2^)优化到O(nlogn)。考虑用一个单调队列来维护并选取最优决策，则对于队列中的两个决策点i<j，应该有f[i]<f[j]，否则因为g的单调性，i永远比j更优。队列中i当前比j更优，但随着当前状态k的增大，因为g的凸性，两个决策的差值会逐渐减小直到大小关系反转，此时就应该将i移出队列。注意到给定两个决策点，我们是可以通过二分计算出令他们大小关系反转的时间点k的。假如队列中存在三个决策点l1<l2<l3，(l1,l2)的反转时间要晚于(l2,l3)，则在l1被移出前，l2会先被移出，因此l2并不会被用来更新答案，于是也不需要加入队列。因此这个单调队列的单调性体现在f[i]关于i单调递增，相邻决策点的反转时间点关于i单调递增。队首保证反转时间点大于等于当前位置。

=== I. Tourists [Akalm] ===

暴力枚举两点计算距离即可。

=== J. Whiteboard [sfiction] ===

未经过的点必须为0。中断时间要晚于所有1的最后一次经过，并早于所有0的最后一次经过。因此只需处理出所有位置的最后一次经过时间。分四个方向离线处理，每行/列用一个优先队列维护当前事件最大值即可。

=== K. YATP [JTJL & sfiction] ===

单侧路径可以用(a_u,s(u,w))来表示，固定w，路径可以表示为a_u*a_v+s(u,w)+s(v,w)，是斜率优化的形式。路径处理用树分治即可。

== 补题 ==

~~A~~ ~~H~~ ~~K~~

=== JTJL ===

 * Unaccepted: K

Run ID	Time	Size	Problem	Language	Result
814	4:59:42	1848	A	g++0x	Wrong answer	6
813	4:59:29	1849	A	g++0x	Time-limit exceeded	6
812	4:59:16	1849	A	g++0x	Time-limit exceeded	6
811	4:58:35	1849	A	g++0x	Time-limit exceeded	6
810	4:57:43	1848	A	g++0x	Wrong answer	6
809	4:56:36	1848	A	g++0x	Wrong answer	6
808	4:54:18	1760	A	g++0x	Time-limit exceeded	6
807	4:53:45	1761	A	g++0x	Memory limit exceeded	6
806	4:53:27	1760	A	g++0x	Memory limit exceeded	6
805	4:52:58	1760	A	g++0x	Time-limit exceeded	6
804	4:52:00	1763	A	g++0x	Time-limit exceeded	6
803	4:50:46	1763	A	g++0x	Time-limit exceeded	6
802	4:49:45	1764	A	g++0x	Memory limit exceeded	6
801	4:48:30	1769	A	g++0x	Memory limit exceeded	6
800	4:47:06	1727	A	g++0x	Memory limit exceeded	6
799	4:46:31	1735	A	g++0x	Time-limit exceeded	5
798	4:40:26	1722	A	g++0x	Wrong answer	5
797	4:38:08	1717	A	g++0x	Wrong answer	5
796	4:19:08	1420	B	g++0x	OK	N/A
795	4:06:01	1418	B	g++0x	Wrong answer	4
794	3:02:13	2523	J	g++0x	OK	N/A
793	2:39:58	3528	G	g++0x	OK	N/A
792	2:33:19	1671	D	g++0x	OK	N/A
791	2:17:46	3310	G	g++0x	Wrong answer	33
790	2:05:40	3279	G	g++0x	Wrong answer	33
789	1:51:29	847	J	g++0x	Time-limit exceeded	6
788	1:40:40	2808	G	g++0x	Wrong answer	25
787	1:06:50	976	C	g++0x	OK	N/A
786	0:55:10	1588	I	g++0x	OK	N/A
785	0:32:39	1298	E	g++0x	OK	N/A
784	0:22:18	847	F	g++0x	OK	N/A
783	0:15:33	825	F	g++0x	Wrong answer	5
782	0:11:51	817	F	g++0x	Wrong answer	5

Start at 18:20

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006280

流水账

总结

sfiction

前期除了 F 之外还算顺利。中期 G 题因为各种细节卡了一个小时，J 则是因为读错题浪费了十分钟，并多等了一个小时。后期题目里，B 过得有点迷……K 题正确题意不难，基本上想到树分治就能做了，可能还是因为过的人少，没有细想。A 最后还差第二部分的 DP 不会处理……H 则是基本没什么想法。

JTJL

实名反对楼上，前期的F过得挺不顺利的…… B也很科学的嘛，树分治的锅修好了真是太好了！

题解

A. Fancy Antiques [Akalm]

把店看作点，商品看成边，抠掉sz有下限的带权最大团即可。

B. Alternative Bracket Notation [JTJL]

迭代。

C. Greetings! [sfiction]

暴力状压DP。

D. Programming Team [Akalm]

二分答案，设c[u] = a[u] - ans*b[u]，树dp找权值和最大子树。

E. K-Inversions [sfiction]

暴力NTT。

F. Mountain Scenes [JTJL]

DP。注意 n/w 和 h 的大小关系。

G. Symmetry [JTJL]

分类讨论，注意对称轴可能不是任意两点的中垂线。

H. Jewel Thief [Akalm]

按同种质量合并后dp，可以用单调队列优化。

sfiction: 首先合并同代价物品，显然同代价应该先取高收益，之后暴力DP可以得到O(K²logS)的做法。只考虑一个阶段，且假设s=1，设状态f[i]为大小为i的背包的最大收益，而不是恰好为i所得最大收益。转移函数f[i]=max(f[i-j]+sum(a[1..j]))。设g[j]=sum(a[1..j])，容易发现g是单调递增的凸函数。这类问题有一种通用的优化方法，可以将复杂度从O(n²)优化到O(nlogn)。考虑用一个单调队列来维护并选取最优决策，则对于队列中的两个决策点i

I. Tourists [Akalm]

暴力枚举两点计算距离即可。

J. Whiteboard [sfiction]

未经过的点必须为0。中断时间要晚于所有1的最后一次经过，并早于所有0的最后一次经过。因此只需处理出所有位置的最后一次经过时间。分四个方向离线处理，每行/列用一个优先队列维护当前事件最大值即可。

K. YATP [JTJL & sfiction]

单侧路径可以用(a_u,s(u,w))来表示，固定w，路径可以表示为a_u*a_v+s(u,w)+s(v,w)，是斜率优化的形式。路径处理用树分治即可。

补题

A H K

JTJL

• Unaccepted: K