2022/07/16 做题记录

Posted on Disqus:

2022.7.15 模拟赛 T1

http://47.92.197.167:5283/contest/241/problem/1

考虑在序列上怎么做，对于每一个数 x 设 viv_i 表示 i 是否在 x 左面出现，存在一组解的条件显然就是存在一个 a 使得 vx−a≠vx+av_{x-a} \neq v_{x+a}，这个不太好处理，于是考虑没有界的条件，就是不存在一个 a 满足上述条件，也就是原串以 x 为中心回文，而回文串可以用正反哈希相等来判断，于是可以线段树维护 vv 的区间哈希值。

而在树上，枚举 y，考虑两种情况：

  1. x,z 一个在子树内，一个在子树外

    这样的话可以直接把 v 的定义改为 viv_i 表示 i 是否在 x 子树内出现，因为两个长度相等的串相减的哈希值等于它们的哈希值相减，于是可以直接离线，进入子树时求一次，退出子树时求一次。

  2. x,z 都在子树内，且它们的 lca 是 y
    我们枚举所有轻儿子子树内的所有点，如果存在一个 x，满足 y∗2−xy*2-x 未在子树内出现，那么找到一组解，如果没有的话，因为 x,z 分属两个子树，那么 2 情况就不存在。
    复杂度分析就是每个点只会被是它的祖先，且连向它所在的子树的那条边为轻边的点统计，每个点只会被统计 log 次。

时间复杂度 O(nlog⁡n)\mathrm{O}(n \log n)，稍微卡常。

code: http://47.92.197.167:5283/submission/101343

CF1705F

听说洛谷有加强版，不过没去看。

675 大约是 23n\frac{2}{3}n,于是我们把前 23\frac{2}{3} 的数每两个相邻的一起处理。

我们先问出全是 T 的值，每次询问把这两个改为 F，于是我们知道了它们之中有几个 T。

如果有 2 个或者 0 个的话可以唯一确认，否则还需要确认。

于是我们先问出 FTFTFT… 的值，每次如果遇到这种情况的话就把这两位的 TF 反转再问一次，发现它们的差只能是 -2 或 2，这样不仅能确定这两个数是什么，如果我们把后 13\frac{1}{3} 中还没有被确定的数拿出来一个把它的位反转，它对答案的影响就是 ±1\pm 1，这样是不妨碍我们确定前面的数的，而且同时也可以确定它是什么。

至于剩下的一个一个问就行，因为它们剩下肯定就是前面问的时候遇到两位相同，是有多余的询问的。

看起来确实可以更小，因为第一步问的时候答案只能是 −2,0,2-2,0,2，有点浪费。

code: https://codeforces.com/contest/1705/submission/164433213