因为有的题代码没写 所以统一不给出代码了。

感觉题目整体还是很提高组的 就是我 12 天比赛放在 3h 打就死了

比赛地址

COVID19

直接枚举第一个感染的是谁 模拟一下就好了。按照实现情况 $O(n^2)/O(n\log n)$

CORUS

按照题意贪心模拟一下就好了。

TRPLSRT

首先把排列拆成若干个轮换,轮换是有顺序的($i \to p_i$)目标是拆成 $n$ 个轮换。

对于每个长度 $>3$ 的轮换 任意找三个连续的点 按照轮换的顺序的逆方向指定 就可以让两个点变成大小为 $1$ 的轮换,这也是最优方案。

对于长度 $=3$ 的轮换,按照轮换反方向操作可以直接变成三个大小为 $1$ 的轮换。

对于长度 $=2$ 的轮换,只能和另一个 $=2$ 的轮换配对后 $2$ 步一起消去。

按照大小从大到小排序 挨个处理就行了。如果无法完成 $2$ 之间的配对就无解。

CHANDF

如果没有上下界限制和最小化限制的话 显然全填 $1$ 最优。

如果没有上下界限制 要求最小化答案的话 如果一个位 $X,Y$ 都是 $0$ 的话那么这个位就没必要填 $1$ 了。

如果只有上界限制的话 可以枚举卡到上界哪一位 相当于后面可以随便选。

如果上下界都有限制的话 需要枚举是否上下界都卡这一位 只卡上界 只卡下界 都不卡 分别暴力枚举就行了。

Bouns1:按位或

只有两边全是 $1$ 才要填 $0$ 否则都填 $1$ (正好反过来)

Bouns2:按位异或

我也不会 求评论区大佬教我(或者直接私聊我 QQ)

SORTVS

先入为主地想错了这题。

这个题目相当于要求你把排列 $p$ 排序。

首先我们将免费交换看成边建一个图

引理1:发现同一个连通块里的位置可以任意安排不需要花费任何代价。

只需要证明树可以调整好就能证明上述结论是对的。观察一个点连续在一条链上交换 相当于只是这个点和链的末尾交换。所以我们考虑从根开始 肯定有偶数个点满足自己的目标点和自己不在一个子树里(显然)所以就交换一下 递归做即可。

我们考虑将 $(i,p_i)$ 看成原图中的有向边。我们发现如果这两个点在同一个连通块里就不用担心了。只需要考虑这两个点在不同连通块的情况 所以我们对每个连通块内部缩点 用$(i,p_i)$ 这些边建一个新图。

引理 2:如果将边配对成若干环 答案就是边的数量减去环的数量

我们每次交换只能找出一个环然后消掉。不如考虑我们每次找出一个简单环 这样就能省下 $1$ 的代价 这也是最优的方案。具体操作还是考虑每交换相邻的两个点就会将一个点清出环 这样只需要环长-1 次就可以了。

于是我们相当于要给这些边配对 使得环尽量多。这里各种贪心其实都是错的(并且题目都这么小范围直接状压不好么)

我们考虑状压 dp:设 $f_S$ 表示 $S$ 集合内的边最多能凑成多少个环。初始化如果 $T$ 构成一个简单环 那么 $f_T = 1$。

转移直接枚举一个集合分开就好了。这样复杂度是 $O(3^n)$ 的。

其实可以通过每次枚举一个环转移做到更优。

NBOTS

竟然是 Challenge 题 那么说明我肯定不会。

题解说搞个估价函数随机化就能拿到很高的分,我也不清楚。

但还是讲一下如果计算快速消去一行的代价吧:这是个区间 dp 设 $f[i][j]$ 表示剩下 $[i,j]$ 的代价 枚举下一次如何操作即可。

NRWP

每个点可以选择正负 并且只有 $200$ 个点 想到最小割。

如果两个点在不同集合内就会产生 $p_ip_j$ 的代价。如果某个点在某个集合内会产生某些代价。网络流板子拉一拉就好啦。

TWOSTRS

考虑答案只有可能是 $A$ 的前缀和 $B$ 的后缀组成。

所以我们去枚举所有可能的情况 接下来是去考虑如何快速计算。

分为三段:

  • 只在 $A$ 里面,可以预处理
  • 跨过了 $A$ 和 $B$ 的拼接点,可以考虑先对所有小串建出 AC 自动机 AC 自动机上当前位置对应的点是一段后缀 所以我们直接定位到 $A$ 当前前缀对应的点 然后扫过去 $B$ 的最多 $25$ 个字符 统计一下每个点的子串的和就好了(fail 树上到祖先的和)
  • 注意到这样会把 $B$ 算掉一部分 要去掉这一部分。

还是对 AC 自动机理解不深(忘了) 实际上每个点对应的是一段最长可接受的后缀。


版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/1179/

转载时须注明出处及本声明

Last modification:May 19th, 2020 at 02:05 pm
如果觉得我的文章对你有用,请随意赞赏