2016-E39-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run ID||Time||Size||Problem||Language||Result||Failed test||
||48||5:25:50||1645||H||g++0x||Wrong answer||7||
||47||4:56:43||1768||H||g++0x||Wrong answer||16||
||46||4:54:53||1767||H||g++0x||Wrong answer||1||
||45||4:52:20||1729||H||g++0x||Time-limit exceeded||31||
||44||4:48:43||1638||H||g++0x||Memory limit exceeded||31||
||43||4:47:16||1638||H||g++0x||Memory limit exceeded||31||
||42||4:22:22||983||E||g++0x||OK||N/A||
||41||3:46:25||3598||D||g++0x||OK||N/A||
||40||1:59:44||1775||A||g++0x||OK||N/A||
||39||1:41:33||1460||C||g++0x||OK||N/A||
||38||1:19:16||1592||G||g++0x||OK||N/A||
||37||1:14:28||1589||G||g++0x||Wrong answer||1||
||36||1:02:35||1319||G||g++0x||Wrong answer||9||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006284
start at 17:15
== 流水账 ==
== 总结 ==
== 题解 ==
=== A. Matryoshka [JTJL] ===
原问题等价于在 x >= Ai, y <= Bi 的区域内查询最长的链pi，对任意的i < j, 有-xpi <= -xpj && ypi <= ypj。离散化后按照y为第一关键字，-x为第二关键字，是否为询问为第三关键字排序，可以用x坐标上的线段树维护当前x坐标下最长的链的长度，只需要用一维线段树维护即可。复杂度为 O((N+Q)log(N+Q))
=== C. Employment [sfiction] ===
连续段数量等于序列中相邻两数与Bi大小关系不同的位置数。设相邻两数为l<=r，则它们对[l+1,r]的Bi都有1的贡献。因此用线段树维护即可。O(nlogn+qlogn)。
=== D. Sandwich [JTJL, sfiction] ===
考虑枚举目标块，如果选择先取走上方的三角形，则它依赖于直角边所对的两个三角形，这两个三角形又各自依赖于斜边所对三角形，这样递归即可，复杂度为O(n^4^)。仔细观察可以发现每步都只是一个三角形加一条禁止边，用dp[i][j][k]表示当前处理格子i,j中哪个三角形，哪一条边被禁止，因为会有重复点，所以记忆化必须存下所有bitset，会MLE。因此考虑将每个状态抽象为点，除去图上所有强连通分量以及依赖其的点后得到一个DAG，在DAG上进行求解即可。DAG上可以在点出队时回收bitset，减少空间使用。O(n^4^/bitset)。
=== E. Toilets [JTJL, sfiction] ===
当女生比男生少时无解。设女生数量为x，男生数量为y，任意前缀中，女生数量不能多于男生数量diff=x-y+1以上，否则后面部分连FM组合都无法完成。为了保证有解，只需要将男生向前移动，于是对于每个女生，计算会被多少个男生超过。设分别有x和y人，则至少有x-diff-y人超过她。考虑每个循环段，如果循环段中男生较多，那么后续段中结果会逐渐变小，反之结果会逐渐变大。因此只需考虑每个循环段的第一段和最后一段。O(S)。
=== G. Telegraph [JTJL, sfiction] ===
首先对于以环上点为根的树，树中每个点只需保留代价最大的儿子即可。环上可以判断指向u的边和仍然与u相连的子树哪一个代价更高，保留代价更高的点。特例是环上边均大于子树边，此时应该选择差最小的一处环上边断开。O(n)。
=== H. Dangerous Skating [JTJL, Akalm] ===
考虑使用优先队列+dij求起点到每个点的最短路。对于点(x, y)，在原图上往四个方向走到尽头，然后更新直线上各点的最短路；假设我们某点(x2, y2)是由(x2, y1), y1 < y2更新而来的，现在尝试更新(x2, y3), y3 < y2：虽然穿过(x2, y1)不合法，但一定有dist(x2, y2) + cost(y2, y3) >= dist(x2, y1) + cost(y1, y3)，因此可以无视初始局面后产生的障碍。 观察更新过程可知每个方向只需更新最远点和距离为1的点。
=== I. Worst Reporter 2 [Akalm] ===
把2h组的元素从高到低贪心处理，并将可用的5h组加入，线段树维护每个5h组加入的时间点里有多少个5h组可以任意改国籍。| Run ID | Time | Size | Problem | Language | Result | Failed test |
| 48 | 5:25:50 | 1645 | H | g++0x | Wrong answer | 7 |
| 47 | 4:56:43 | 1768 | H | g++0x | Wrong answer | 16 |
| 46 | 4:54:53 | 1767 | H | g++0x | Wrong answer | 1 |
| 45 | 4:52:20 | 1729 | H | g++0x | Time-limit exceeded | 31 |
| 44 | 4:48:43 | 1638 | H | g++0x | Memory limit exceeded | 31 |
| 43 | 4:47:16 | 1638 | H | g++0x | Memory limit exceeded | 31 |
| 42 | 4:22:22 | 983 | E | g++0x | OK | N/A |
| 41 | 3:46:25 | 3598 | D | g++0x | OK | N/A |
| 40 | 1:59:44 | 1775 | A | g++0x | OK | N/A |
| 39 | 1:41:33 | 1460 | C | g++0x | OK | N/A |
| 38 | 1:19:16 | 1592 | G | g++0x | OK | N/A |
| 37 | 1:14:28 | 1589 | G | g++0x | Wrong answer | 1 |
| 36 | 1:02:35 | 1319 | G | g++0x | Wrong answer | 9 |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006284
start at 17:15
流水账
总结
题解
A. Matryoshka [JTJL]
原问题等价于在 x >= Ai, y <= Bi 的区域内查询最长的链pi，对任意的i < j, 有-xpi <= -xpj && ypi <= ypj。离散化后按照y为第一关键字，-x为第二关键字，是否为询问为第三关键字排序，可以用x坐标上的线段树维护当前x坐标下最长的链的长度，只需要用一维线段树维护即可。复杂度为 O((N+Q)log(N+Q))
C. Employment [sfiction]
连续段数量等于序列中相邻两数与Bi大小关系不同的位置数。设相邻两数为l<=r，则它们对[l+1,r]的Bi都有1的贡献。因此用线段树维护即可。O(nlogn+qlogn)。
D. Sandwich [JTJL, sfiction]
考虑枚举目标块，如果选择先取走上方的三角形，则它依赖于直角边所对的两个三角形，这两个三角形又各自依赖于斜边所对三角形，这样递归即可，复杂度为O(n4)。仔细观察可以发现每步都只是一个三角形加一条禁止边，用dp[i][j][k]表示当前处理格子i,j中哪个三角形，哪一条边被禁止，因为会有重复点，所以记忆化必须存下所有bitset，会MLE。因此考虑将每个状态抽象为点，除去图上所有强连通分量以及依赖其的点后得到一个DAG，在DAG上进行求解即可。DAG上可以在点出队时回收bitset，减少空间使用。O(n4/bitset)。
E. Toilets [JTJL, sfiction]
当女生比男生少时无解。设女生数量为x，男生数量为y，任意前缀中，女生数量不能多于男生数量diff=x-y+1以上，否则后面部分连FM组合都无法完成。为了保证有解，只需要将男生向前移动，于是对于每个女生，计算会被多少个男生超过。设分别有x和y人，则至少有x-diff-y人超过她。考虑每个循环段，如果循环段中男生较多，那么后续段中结果会逐渐变小，反之结果会逐渐变大。因此只需考虑每个循环段的第一段和最后一段。O(S)。
G. Telegraph [JTJL, sfiction]
首先对于以环上点为根的树，树中每个点只需保留代价最大的儿子即可。环上可以判断指向u的边和仍然与u相连的子树哪一个代价更高，保留代价更高的点。特例是环上边均大于子树边，此时应该选择差最小的一处环上边断开。O(n)。
H. Dangerous Skating [JTJL, Akalm]
考虑使用优先队列+dij求起点到每个点的最短路。对于点(x, y)，在原图上往四个方向走到尽头，然后更新直线上各点的最短路；假设我们某点(x2, y2)是由(x2, y1), y1 < y2更新而来的，现在尝试更新(x2, y3), y3 < y2：虽然穿过(x2, y1)不合法，但一定有dist(x2, y2) + cost(y2, y3) >= dist(x2, y1) + cost(y1, y3)，因此可以无视初始局面后产生的障碍。 观察更新过程可知每个方向只需更新最远点和距离为1的点。
I. Worst Reporter 2 [Akalm]
把2h组的元素从高到低贪心处理，并将可用的5h组加入，线段树维护每个5h组加入的时间点里有多少个5h组可以任意改国籍。