2016-E02-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run ID||Time||Size||Problem||Language||Result||
||1321||3:19:06||2096||C||g++0x||OK||
||1320||3:18:26||2096||C||g++||Compilation error||
||1319||2:25:11||2789||H||g++||OK||
||1318||2:20:39||2783||H||g++||Memory limit exceeded||
||1317||1:56:01||2715||D||g++||OK||
||1316||1:41:51||1714||A||g++||OK||
||1315||1:24:33||3142||F||g++||OK||
||1314||0:16:24||433||B||g++||OK||
||1313||0:13:47||425||B||g++||Wrong answer||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010271
== 流水账 ==
== 总结 ==
=== sfiction ===
* I 题状态的修改并不罕见……却一直没有进展
== 题解 ==
A 略去不表。
=== B. Compare Continued Fractions [sfiction] ===
注意大小关系的变换。
=== C. Graph Coloring [Akalm] ===
先将所有点按度数从小到大加入扩展队列。[[BR]]
每次将队头的颜色确定，再检查一下直连点中是否有要重新染色的（至多一个）。队列长度只增不减，而且需要重染色的情况很少。设置一个入队次数上限作为卡时阈值处理无解的情况。[[BR]]
=== D. Convolution [JTJL] ===
裸FWT[[BR]]
=== F. Pentagon [JTJL] ===
三角剖分，DP或者枚举即可[[BR]]
=== H. Removing Vertices [Akalm] ===
将与0直接相连的点涂黑，再移除顶点0及相关边，就变成了求在几棵树中移除最少的点使得所有黑点都相互不连通。树上dp即可。[[BR]]
=== I. Two Paths [sfiction] ===
给定一个 DAG(n<=5e3,m<=2e4)，求总长最小的两条边不相交路径 A-B C-D。
用 dp[i][j] 表示路径 A-B 到达 i，路径 C-D 到达 j 的最小代价，其中 ij 为点的拓扑序标号。因为需要处理 dp[i][i]-dp[i][j]-dp[j][j] 的非法转移，需要将状态修改为 dp[i][j][type] 来表示边 i-j 是否被使用。由于边集共出现 n 次，复杂度为 O(nm)。
需要检查 i-B j-D 是否可行来减少转移量，否则会超时。
=== J. Two Rectangles [JTJL] ===
感受一下，可以得到两个矩形一定是一个很大的类正方形和一个很小的矩形。小的矩形的边长大概在500以内，枚举大的矩形的一边长乱搞即可[[BR]]
== 补题 ==
EG ~~I~~ ~~J~~
=== JTJL ===
* Unaccepted: J
=== sfiction ===
* Unaccepted: I| Run ID | Time | Size | Problem | Language | Result |
| 1321 | 3:19:06 | 2096 | C | g++0x | OK |
| 1320 | 3:18:26 | 2096 | C | g++ | Compilation error |
| 1319 | 2:25:11 | 2789 | H | g++ | OK |
| 1318 | 2:20:39 | 2783 | H | g++ | Memory limit exceeded |
| 1317 | 1:56:01 | 2715 | D | g++ | OK |
| 1316 | 1:41:51 | 1714 | A | g++ | OK |
| 1315 | 1:24:33 | 3142 | F | g++ | OK |
| 1314 | 0:16:24 | 433 | B | g++ | OK |
| 1313 | 0:13:47 | 425 | B | g++ | Wrong answer |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010271
流水账
总结
sfiction
- I 题状态的修改并不罕见……却一直没有进展
题解
A 略去不表。
B. Compare Continued Fractions [sfiction]
注意大小关系的变换。
C. Graph Coloring [Akalm]
先将所有点按度数从小到大加入扩展队列。
每次将队头的颜色确定，再检查一下直连点中是否有要重新染色的（至多一个）。队列长度只增不减，而且需要重染色的情况很少。设置一个入队次数上限作为卡时阈值处理无解的情况。
D. Convolution [JTJL]
裸FWT
F. Pentagon [JTJL]
三角剖分，DP或者枚举即可
H. Removing Vertices [Akalm]
将与0直接相连的点涂黑，再移除顶点0及相关边，就变成了求在几棵树中移除最少的点使得所有黑点都相互不连通。树上dp即可。
I. Two Paths [sfiction]
给定一个 DAG(n<=5e3,m<=2e4)，求总长最小的两条边不相交路径 A-B C-D。
用 dp[i][j] 表示路径 A-B 到达 i，路径 C-D 到达 j 的最小代价，其中 ij 为点的拓扑序标号。因为需要处理 dp[i][i]-dp[i][j]-dp[j][j] 的非法转移，需要将状态修改为 dp[i][j][type] 来表示边 i-j 是否被使用。由于边集共出现 n 次，复杂度为 O(nm)。
需要检查 i-B j-D 是否可行来减少转移量，否则会超时。
J. Two Rectangles [JTJL]
感受一下，可以得到两个矩形一定是一个很大的类正方形和一个很小的矩形。小的矩形的边长大概在500以内，枚举大的矩形的一边长乱搞即可
补题
EG I J
JTJL
- Unaccepted: J
sfiction
- Unaccepted: I