2024/02/06(#13)：一点思考

摘要：不知道写点什么。

思考少了。

好奇怪啊。

[Ptz 2022 Day 2] Ternary Search

我们只需要考虑单谷。

谷的值是可以确定的。如果我们将谷左边的数全部取相反数，那么答案就是全局的逆序对数。

也就是说，我们通过是否取相反数来确定其应该是在谷值的左边还是右边。如果取相反数，那么它在左边，它对答案的贡献是在它左边比其小的个数 $L_i$ ；如果不取相反数，那么其对答案的贡献就是正常计入逆序对统计了。

也就是说，我们可以正常求逆序对的个数，当其走到左边的时候，我们就在树状数组上撤销它的贡献。何时它会跑到左边？当在它左边有 $x$ 个比它小的数，右边有 $x$ 个比它小的数的时候，就会切换，此时直接继承原来的贡献即可。树状数组上倍增即可。代码。

[Ptz 2022 Day 2] Floor Tiles in a Park

Portal.

大分讨题。

$k=1$ 时答案是 $1$ ， $k=2$ 时答案是 $w+h-1$ 。 $k=3,k=4$ 方式和 $k=5$ 一样。

$k=5$ 时可以有三条横线穿过去，方案数如下：

可以有两条横线，两条竖线穿过去，对照样例即可找到系数。代码。

[CF1924C] Fractal Origami

Portal.

挺有趣的。

折一折就知道了 $M=\sum_{i=0}^{n-2} 2\sqrt{2}^i,V=2\sqrt{2}+\sum_{i=0}^{n-2} 2\sqrt{2}^i$ 。

然和随便合一合就行了。代码。

[CF1924E] Paper Cutting Again

Portal.

考虑随机出一个操作序列 $p$ ，是一个 $1\sim n + m - 2$ 的排列。枚举所有切的位置称为答案的最后一步，考虑计算其概率。

应该满足 $[1,i-1]$ 的行， $[1,k/i]$ 的列都在 $i$ 行后就出现，概率可以直接计算为 $\frac 1 m$ ，然后加上当前这一步的 $1$ ，即可求出答案。代码。

[CF1924F] Anti-Proxy Attendance

Portal.

Joking 基本上和这道题一致。

实际上询问告诉我们的是，不管是真是假，我们可以知道缺席的学生在某一个集合里。

允许我们猜测两次的原因是明显的：在只剩两个人的时候我们没有办法得知谁是缺席的。因此，我们看看怎么在只剩三个人的时候排除一个人。

由于这道题是对于连续三次询问的情况有限制，情况非常复杂。因此我们先一点一点来：

先问一手 $Q(1,2)$ ？确实，无论回答是什么，都没什么意义。那不如假定它的回答就是 $1$ ，剩下的应该是对称的。
再问一手 $Q(1,1)$ $Q (1, 1)$ ？
- 如果它回答了一个 $1$ ，那么我们只需要再问一个 $Q(1,3)$ ，如果它的回答也是 $1$ ，那么 $1$ 就一定不是缺席的，否则连续三次回答都是真的了；如果 $Q(1,3)$ 回答了一个 $0$ ，那么这是一个假的，前两问 $Q(1,2)$ 和 $Q(1,1)$ 一定不能都是假的，如果它们都是假的，那么就证明了 $3$ 是缺席的，也就是说， $3$ 一定不是缺席的。
- 如果它回答了一个 $0$ ，就相当于 $Q(2,3)$ 回答了 $1$ 。那么这时候再问一手 $Q(1,2)$ ，如果此时回答的是 $1$ ，那么三次回答不能都为真， $2$ 就一定不是缺席的；如果 $Q(1,2)$ 回答了 $0$ ，就相当于 $Q(3,3)$ 回答了 $1$ 。此时能确定什么吗？还真不能，只好在问一次 $Q(1,3)$ ，就回到了上一种情况。

即使我们排除了中间的 $2$ ，其并不会影响接下来的询问的答案，因此我们可以直接三分，每次使用四次询问来排除掉 $1/3$ 的答案，大约会使用 $112$ 次询问，而题目只允许我们使用 $102$ 次询问！好像废掉了！

但是我们真的每次必须用 $4$ 次询问吗？我们观察一下需要使用四次询问的情况，发现它们有一个特点：排除的一定不是 $2$ 。

也就是说我们让 $2$ 分的小一点就可以了！我们可以使用 DP 来求解 $2$ 分多少。设 $f_n$ 代表问题规模为 $n$ 的时候，至少使用多少次询问，枚举 $2$ 分的个数 $j$ ，那么 $f_n=\min_{j=1}^{n-2}\{\max\{f_{n-j}+3,f_{n-(n-j)/2}+4\}\}$ ，跑不动。

但是我们可以观测转移点！跑 $n=10^4$ ，转移点的平均值是 $0.3n$ ，于是直接按照比例分就行了。代码。

[CF1056H] Detect Robots

Portal.

就是要判断是否出现过 $x\rightarrow a\rightarrow \cdots\rightarrow y,x\rightarrow b\rightarrow \cdots\rightarrow y$ 的情况。

根号分治。对于小串，对于每个终点 $y$ 开一个 vector，push_back 所有的起点对应的 $(x,t)$ 对，总个数是 $O(n\sqrt{n})$ 的。对于大串，记录所有点的出现位置，对于每个串从后往前扫，记录当前最大的终点位置然后判断即可。代码。

水一下 Div.3，给小号上上分！

完蛋，大意了😅