赛时：\(60+50+0+0\)
A. bookstore
题意： \(m\) 套书， \(n\) 本书。要求选出两个交集为空的套书的集合，使得两集合中出现的书的种类相同。
见到二元组，显然考虑连边。然后发现若有偶环必定有解，01交替染色即可。然后发现剩下来没环和奇环都无法成功。
难点在于判偶环。显然可以搞出搜索树，一种直接有经过一条非树边的偶环。否则两个奇环套在一起也可以。比较麻烦的分讨。
实际上可以变成二分图 \(u\space ->\space v+n,v \space -> \space u+n\) 此时只要判环。此时出现了一个问题，若两条路径是对称的，有可能也会被算入答案（见下图）。此时需要异或哈希的科技，也就是每条边随机权值，用异或判断两条路径是否一模一样。最后找出环会发现两集合或集合内可能有重边，直接去重即可。
直接判环的反例：
建图会变成这样
此时会找到1->8->6->3->7->1这个环
但是你会发现经过的边实际上是1->3->2->1->3->2->1。这不就是把1->3->2->1这个环走了两边么，通过判断路径一模一样来给它排除掉就行了。
B. kasane
题意：给定一个字符串求有多少子串满足能被 \(k\) 个 \(A+rev(A)+A+...\) 拼接得到。\(rev(A)\) 指的是翻转串。当 \(k=3\) 时也就是\(A+rev(A)+A\)。
比第一题友善很多。
显然当 \(k=1\) 时为子串个数， \(k=2\) 为回文串个数。
考虑 \(k=3\) 。令第 \(i\) 个空隙回文半径为 \(d_i\) 。考虑两个分界点 \(x,y\) 发现需要满足 \(min(d_x,d_y) \ge y-x\) 二维数点即可。
接下来把 \(k=3\) 的做法推广。
- 若 \(k\) 为偶数则取第 \(\frac{k}{2}-1\) 和 \(\frac{k}{2}\) 个分界点 \(x,y\) ，需要满足 \(d_x \ge (\frac{k}{2}-1)(y-x)\) 并且 \(d_y \ge \frac{k}{2}(y-x)\) 。
- 若 \(k\) 为奇数则取第 \(\lfloor\frac{k}{2} \rfloor\) 和 \(\lceil\frac{k}{2} \rceil\) 个分界点 \(x,y\) 需要满足 \(min(d_x,d_y) \ge \lfloor\frac{k}{2} \rfloor(y-x)\)。
同样搞个二维数点就做完了。
C. starch
题意：定义一个无根树 \(T2\) 为有根树 \(T1\) 的点分树当且仅当\(T1\)的根在两树中的度数相同且根的每个子树 \(T2\) 也分别 \(T1\) 的子树。每次给 \(T1\) 和\(T2\)。每次操作可删掉 \(T1\) 任意一条边再给断开的两个连通块任连一条边。求最少多少次操作使得可以指定 \(T1\) 的根让 \(T2\) 是 \(T1\) 的点分树。
首先观察 \(T2\) 是 \(T1\) 的点分树的条件。令 \(T2\) 的根和 \(T1\) 相同，条件相当于对于 \(T2\) 的每条边 \(u->v\)（ \(u\) 为 \(v\) 父亲）在 \(T1\) 中 \(u\) 都至少有一条连向 \(v\) 子树的边。进而发现若确定了根那么只要判断对于每条边计不满足上述条件的边的数量即可。
直接在 \(T2\) 上做换根 \(dp\) 。注意到每个限制转化为 \(T1\) 上 \(u\) 向 \([l,r]\) 的 \(dfs\) 序区间内有连边。这个玩意可以通过二分 \(log_{2}n\) 计算。换根的时候只有\(u->v\)这条边发生了变化变成了 \(v\) 有向 \(u\) 子树外有连边，也可轻松计算。于是就做完了。
D. orz
史
标签：2024.10,20,题意,space,T2,T1,ge,做题,frac From： https://www.cnblogs.com/IANYE/p/18493842