网站管理与建设总结,潍坊专业企业营销策划有哪些,贵州省建设学校网站首页,泉州seo网站管理时间安排
7:30–7:50 看题#xff0c;怎么感觉三道构造#xff0c;T3 貌似有网络流背景。 7:50–8:30 T1,有一些简单的性质#xff0c;缩减两端点后枚举一下翻转的区间就可以了。然后花了一点时间写 spj 调试。 8:30–10:20 T2,比较纯粹的构造题。有网络流做法#xff0c;…时间安排
7:30–7:50 看题怎么感觉三道构造T3 貌似有网络流背景。 7:50–8:30 T1,有一些简单的性质缩减两端点后枚举一下翻转的区间就可以了。然后花了一点时间写 spj 调试。 8:30–10:20 T2,比较纯粹的构造题。有网络流做法但是复杂度过于紧空间也卡的很死估摸着也就比手玩多个 5 到10 分左右。考虑构造手玩一下没找到什么规律。琢磨样例发现有几个比较固定的方案于是把这些方案拼起来。细节一大堆写写写写到 10:20 。直接去看 T3 了。 10:20–11:30 T3,状压是好求的。考虑更高的部分分显然可以用网络流求个最大独立集什么的然后 dfs 一下发现不是二分图于是就不会了。想了想不可能裸上网络流应该是有性质什么的瞪了一会没瞪出来。 11:30–11:50 回头看了一眼 T2 ,随便玩了几个小样例发现好像有反例但是没什么规律性好像也没法变成系统的构造方案。
回顾反思
T2: 赛时一直在找规律的构造。 然而事实上赛后参考了一下同学的做法发现就没啥规律对小数据硬打表然后把小规模的方案拼起来。 还是要勤于动手去搜。 一个人类智慧的点是用单位长度为 4 的规模取拼的时候可能会遗留一些不够 4 的很小的空隙小的空隙不好归纳可以考虑牺牲一些已经拼好的位置将其规模扩大 4 然后做。 T3: 没有发现边的传递性。 发现边是传递闭包后可以钦定一个边的方向于是由无向图变为dag变成了求最小链覆盖问题。 于是就可以建出拆点二分图的模型了。 最小链覆盖的模型不太熟悉。这种性质的敏感度要加强一下。 这个可以网络流解决。不过需要优化。 一个神奇点是尽可能贪心的匹配后剩下的未匹配的点数量是 n\sqrt nn 级别的。这个题解里没有给出证明我也不太会证。 以匈牙利算法为例增广的过程中一个优化是对于一个点 x 有若干出边 y ,那么之后递归到点 z 时的增广无需再考虑出边 y 。因为传递闭包z 考虑出边 y ,不如 x 考虑出边 y 。于是一次増广中每个点的出边只被考虑一次。
