2020-team2-022

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: 6/12

 rank: 35 校内：2

= 流水账 =

开场读了会题后跟榜'''K1Y26''',之后yyc想了会D，pb问了题意有觉得不应该往三元环方向想，说了一下最小生成树后yyc发现结论，pb上机'''D1Y65''',cxt讲了H题意后yyc说了说做法，cxt修一修细节上机'''H1Y77'''，之后yyc写J,'''J2Y127'''，之后pb由A的网络流想出可以用数据结构模拟,'''A2Y174'''，最后cxt写G，T了一会后优化下写法'''G3Y271'''

= 总结 =

=== pb： ===
这场发挥貌似还不错，做出了感觉很熟悉的题目，但是F这种没见过的类型做的就很慢。即使知道了建图的方法之后，非常Traditional的优化方法并没有想出来，还是对图论算法不够熟悉。感觉队伍的图论水平确实一般，推荐大家都练练。

=== Creatix： ===
一句话，好好补题。

G的代码时长直接反映出了现在的题感和代码感不够强。

upd1: 补了一下E，就一数据结构嘛。。。然而并不会做，看完题解才会。
 4k代码，连敲带调一共1hour，wa了一次，因为有一个出边入边的顺序写反了，会对答案有些微的影响。

upd2：会C了。终于看到题目要用到ear-decomposition了。
 口胡AC。

=== yyc： ===

前期输出还挺高的，后期题就开不动了，可能这就是菜吧（

= 题解 =

 * A：考虑网络流模型，从大到小排序贪心就不会产生退流，然后用线段树模拟网络流，修改可以O(log)

 * B：

 * C：用ear-decompositioin，dp[s][x][y]中，s是以及完成的ear和正在构造的ear的并集，x是ear的端点1，y是ear的端点2，dp值是此时的最小定向代价

 * D：把边从大到小加入，那么三元环的限制不断迭代就变成了两点间的边要等于两点间边权最小值，合并两个连通块的时候可以统计贡献，最后对非树边判断一下不合法情况即可

 * E：题意：问有多少区间，构成一个环。环定义为，存在一个排列p，使得仅在p(i)和p(i+1)之间有边。将原条件转化为三个限制：
   * [l, r] 每个点度数不超过二（这部分，我们可以直接two-pointers）
   * [l, r] 无环              （这部分，我们同样two-pointers，但是记得用LCT维护树边)
   * [l, r] E = V - 1          (这部分，令E[l][r]表示（r - l + 1 - [完全被包含在l, r中的边数])，则边(x, y)的效果是使E[1..x][y..n]全部减一。因此E[l]和E[l+1]只差一个区间加，线段树即可。记得不需要维护1的个数，而只需要维护最小值的个数，因为E[l][r] >= 1）

 * F：直接跑费用流。对每个区间(l, r), 让 l 向 r + 1 连一条容量为 1，费用为 -val 的边。

 然而注意到网格图也是dag，即出题人可以构造网格图来卡掉spfa。

 所以我们必须用zkw的方法写dij。实现方法见队伍模板。

 * G：推一些性质，发现合法的dp情况很少。于是写 dp 套 dp。

 * H：二分答案

 * I：

 * J：找到第一次撞到(0,0)的操作是第几次和操作的方向，后面的操作可以预处理

 * K：按照坐标排序构造

 * L：

 * M：

[/wiki/2020-team2 返回]

概述

solved: 6/12

rank: 35 校内：2

流水账

开场读了会题后跟榜K1Y26,之后yyc想了会D，pb问了题意有觉得不应该往三元环方向想，说了一下最小生成树后yyc发现结论，pb上机D1Y65,cxt讲了H题意后yyc说了说做法，cxt修一修细节上机H1Y77，之后yyc写J,J2Y127，之后pb由A的网络流想出可以用数据结构模拟,A2Y174，最后cxt写G，T了一会后优化下写法G3Y271

总结

pb：

这场发挥貌似还不错，做出了感觉很熟悉的题目，但是F这种没见过的类型做的就很慢。即使知道了建图的方法之后，非常Traditional的优化方法并没有想出来，还是对图论算法不够熟悉。感觉队伍的图论水平确实一般，推荐大家都练练。

Creatix：

一句话，好好补题。

G的代码时长直接反映出了现在的题感和代码感不够强。

upd1: 补了一下E，就一数据结构嘛。。。然而并不会做，看完题解才会。

4k代码，连敲带调一共1hour，wa了一次，因为有一个出边入边的顺序写反了，会对答案有些微的影响。

upd2：会C了。终于看到题目要用到ear-decomposition了。

口胡AC。

yyc：

前期输出还挺高的，后期题就开不动了，可能这就是菜吧（

题解

  • A：考虑网络流模型，从大到小排序贪心就不会产生退流，然后用线段树模拟网络流，修改可以O(log)
  • B：
  • C：用ear-decompositioin，dp[s][x][y]中，s是以及完成的ear和正在构造的ear的并集，x是ear的端点1，y是ear的端点2，dp值是此时的最小定向代价
  • D：把边从大到小加入，那么三元环的限制不断迭代就变成了两点间的边要等于两点间边权最小值，合并两个连通块的时候可以统计贡献，最后对非树边判断一下不合法情况即可
  • E：题意：问有多少区间，构成一个环。环定义为，存在一个排列p，使得仅在p(i)和p(i+1)之间有边。将原条件转化为三个限制：
    • [l, r] 每个点度数不超过二（这部分，我们可以直接two-pointers）
    • [l, r] 无环 （这部分，我们同样two-pointers，但是记得用LCT维护树边)
    • [l, r] E = V - 1 (这部分，令E[l][r]表示（r - l + 1 - [完全被包含在l, r中的边数])，则边(x, y)的效果是使E[1..x][y..n]全部减一。因此E[l]和E[l+1]只差一个区间加，线段树即可。记得不需要维护1的个数，而只需要维护最小值的个数，因为E[l][r] >= 1）
  • F：直接跑费用流。对每个区间(l, r), 让 l 向 r + 1 连一条容量为 1，费用为 -val 的边。

然而注意到网格图也是dag，即出题人可以构造网格图来卡掉spfa。

所以我们必须用zkw的方法写dij。实现方法见队伍模板。

  • G：推一些性质，发现合法的dp情况很少。于是写 dp 套 dp。
  • H：二分答案
  • I：
  • J：找到第一次撞到(0,0)的操作是第几次和操作的方向，后面的操作可以预处理
  • K：按照坐标排序构造
  • L：
  • M：
附加文件