2017-Sp119-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub丢了J给yzc，yzc上机写了一会儿感觉不对，下机和sub理论，cjb冲上机想大力收获D一血，获得wa，yzc上机'''J1y45'''，然后发现cjb离散化写错了，'''D2y49'''，痛失一血。cjb和sub发现C是PAM模板题，cjb抄了一个，sub上机'''C1y81'''。cjb上机写H，'''H1y102'''。yzc思考好了G，上机'''G1y126'''。cjb和sub理论了F，sub上机先后wa了两发。之后三人一起开B，cjb刚了结论，yzc上机大力哈希，'''B1y201'''。之后cjb提出了F的最终模型，sub上机搞了一会儿，'''F4y280'''。
== 总结 ==
=== chenjb ===
离散化失败痛失一血呜呜呜，yzc发型真丑啊woc。
=== oipotato ===
我发型好丑啊woc
=== subconscious  ===
楼上发型真丑啊woc
== 题解 ==
 * A：'''迷之构造'''

 * B：可以证明，每个连通块里度数最大的点一定是连了所有的点，此时这个块要不是个团，要不一定不会在答案里，重复这个操作直到每个块都是团，答案显然就是把size乘起来。具体实现时每个点邻接表的集合哈希值，如果要删掉的点连着的点哈希值都相同则为团。

 * C：在两个回文自动机上同时dfs即可。

 * D：块是左边的点，不同的宽度是右边的点，跑最大费用可行流即可。

 * E：'''迷之置换dp'''

 * F：答案显然只有2n-3和2n-2，2n-2就是生成树计数，2n-3是树形结构加一个核心(三元环share一条边叠加的东西)，dp求得方案数即可。

 * G：离线，把一条边的添加和删除视为在一个时间上添加这条边，遍历线段树时维护可持久化并查集即可。

 * H：f[l][r][k]表示[l,r]子串去掉k个之后剩下回文串时长度为k的字典序最小的删除序列，f[l][r][k]=min(s[l]+f[l+1][r][k-1],f[l][r-1][k-1]+s[r])，如果s[l]==s[r]则f[l][r][k]=min(f[l][r][k],f[l+1][r-1][k])，注意初始态。

 * I：'''迷之博弈'''

 * J：四维dp分别表示四个方向上能走的步数，按bfs的顺序转移即可。

流水账

开场各自看题，sub丢了J给yzc，yzc上机写了一会儿感觉不对，下机和sub理论，cjb冲上机想大力收获D一血，获得wa，yzc上机J1y45，然后发现cjb离散化写错了，D2y49，痛失一血。cjb和sub发现C是PAM模板题，cjb抄了一个，sub上机C1y81。cjb上机写H，H1y102。yzc思考好了G，上机G1y126。cjb和sub理论了F，sub上机先后wa了两发。之后三人一起开B，cjb刚了结论，yzc上机大力哈希，B1y201。之后cjb提出了F的最终模型，sub上机搞了一会儿，F4y280。

总结

chenjb

离散化失败痛失一血呜呜呜，yzc发型真丑啊woc。

oipotato

我发型好丑啊woc

subconscious

楼上发型真丑啊woc

题解

• A：迷之构造
• B：可以证明，每个连通块里度数最大的点一定是连了所有的点，此时这个块要不是个团，要不一定不会在答案里，重复这个操作直到每个块都是团，答案显然就是把size乘起来。具体实现时每个点邻接表的集合哈希值，如果要删掉的点连着的点哈希值都相同则为团。
• C：在两个回文自动机上同时dfs即可。
• D：块是左边的点，不同的宽度是右边的点，跑最大费用可行流即可。
• E：迷之置换dp
• F：答案显然只有2n-3和2n-2，2n-2就是生成树计数，2n-3是树形结构加一个核心(三元环share一条边叠加的东西)，dp求得方案数即可。
• G：离线，把一条边的添加和删除视为在一个时间上添加这条边，遍历线段树时维护可持久化并查集即可。
• H：f[l][r][k]表示[l,r]子串去掉k个之后剩下回文串时长度为k的字典序最小的删除序列，f[l][r][k]=min(s[l]+f[l+1][r][k-1],f[l][r-1][k-1]+s[r])，如果s[l]==s[r]则f[l][r][k]=min(f[l][r][k],f[l+1][r-1][k])，注意初始态。
• I：迷之博弈
• J：四维dp分别表示四个方向上能走的步数，按bfs的顺序转移即可。

附加文件

• 1.png by chenjb