2017-Sp93-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
 * D2y21
 * E2y50
 * H1y57
 * K1y104
 * C4y193
 * 疯狂做F和I无果，原地爆炸升天。
== 总结 ==
=== chenjb ===
很生气，很恼火....菜是原罪.jpg 去你妈的数组维度调换！感觉如果不是被这个数组顺序搞，我们F和I都能过，B也能搞tmd
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：dp[i][j]代表在i-1和j+1已经剪出的情况下，剪出i到j这些边需要的最小代价。枚举中间点k既可。最后枚举第一条边即可。

 * B：按度数从大到小排序，显然一个极大的符合条件的点集肯定是把所有度数>=k的点都取了，二分找到极大值，检验是否合法。然后考虑两种情况，一种是把极大中扔掉一个点，另一种是把没加进来的点换一个进来，两个都需要满足非常严格的size-1度数限制，扫一遍就能得到答案了，时间复杂度和答案都是O(N)级别的。

 * C：从小到大枚举答案，每个时刻的按的按钮视为一个物品，背包即可。

 * D：贪心归并。

 * E：建个trie，标个号，然后把询问串在trie上跑，跑出序列，搜一遍排列组合统计答案。

 * F：先二分答案在右边界或上边界的位置，把询问缩小到底边长为1，高度为10^6^的三角形内，大力用exgcd下一个位置扫描整个三角形。

 * G：

 * H：先全填1，不满足的行和列取出来，先填多余的行获列最左或最上的位置，剩下的每对行和列填交叉位。

 * I：瞎jb树型dp，由于内存空间的限制，需要动态使用空间。

 * J：显然如果有一条边在多于一个简单环上就GG了，所以判完之后相当于在仙人掌上dp。f[i][mask]表示对于i点，除父亲外所有相邻边染色种类为mask的最小代价，转移的时候如果是边就直接处理，如果是环，还需要ff[i][j][k]表示环上前i条边，第i条边为j，奇偶性为k的最小代价，环尾和头特殊处理，最后update到f里即可，注意原图可能不连通。

 * K：rmq维护区间最值和下标，枚举删掉的点是x或y的某个最值，拿出下标，利用前缀后缀最值得到边长，取最优即可。
== 补题 ==

流水账

  • D2y21
  • E2y50
  • H1y57
  • K1y104
  • C4y193
  • 疯狂做F和I无果，原地爆炸升天。

总结

chenjb

很生气，很恼火....菜是原罪.jpg 去你妈的数组维度调换！感觉如果不是被这个数组顺序搞，我们F和I都能过，B也能搞tmd

oipotato

subconscious

题解

  • A：dp[i][j]代表在i-1和j+1已经剪出的情况下，剪出i到j这些边需要的最小代价。枚举中间点k既可。最后枚举第一条边即可。
  • B：按度数从大到小排序，显然一个极大的符合条件的点集肯定是把所有度数>=k的点都取了，二分找到极大值，检验是否合法。然后考虑两种情况，一种是把极大中扔掉一个点，另一种是把没加进来的点换一个进来，两个都需要满足非常严格的size-1度数限制，扫一遍就能得到答案了，时间复杂度和答案都是O(N)级别的。
  • C：从小到大枚举答案，每个时刻的按的按钮视为一个物品，背包即可。
  • D：贪心归并。
  • E：建个trie，标个号，然后把询问串在trie上跑，跑出序列，搜一遍排列组合统计答案。
  • F：先二分答案在右边界或上边界的位置，把询问缩小到底边长为1，高度为106的三角形内，大力用exgcd下一个位置扫描整个三角形。
  • G：
  • H：先全填1，不满足的行和列取出来，先填多余的行获列最左或最上的位置，剩下的每对行和列填交叉位。
  • I：瞎jb树型dp，由于内存空间的限制，需要动态使用空间。
  • J：显然如果有一条边在多于一个简单环上就GG了，所以判完之后相当于在仙人掌上dp。f[i][mask]表示对于i点，除父亲外所有相邻边染色种类为mask的最小代价，转移的时候如果是边就直接处理，如果是环，还需要ff[i][j][k]表示环上前i条边，第i条边为j，奇偶性为k的最小代价，环尾和头特殊处理，最后update到f里即可，注意原图可能不连通。
  • K：rmq维护区间最值和下标，枚举删掉的点是x或y的某个最值，拿出下标，利用前缀后缀最值得到边长，取最优即可。

补题

附加文件