停课记录 2020.10.21
想不到吧两篇一块写的。
模拟赛内容
A. 蛋爆爆
叠词词，恶心心
手玩一下第二个样例可以找到规律：对于每个点按照 \(height\) 把儿子排序，求出 \(dfs\) 序，对于 \(dfs\) 序上相邻的两个点 \(d_i,d_{i+1}\)，答案就是 \(min(dis(d_i,d_{i+1}),dep(d_{i+1}))\)。加起来即可。
当然也可以树形 \(dp\)，开一维 \(0/1\) 表示回不回到 \(i\)，就很方便转移了。
代码-规律 （众所周知 $n\log $ 过不去 \(1e6\)，自闭了qaq）
C. 底垫垫
两题放一块是我今天比赛情况 o(╥﹏╥)o
这题是 戴言题
有一个题解的 pdf，又是不知道咋上传的一天。
自主做题
今天板刷 CF 的一天。由于我是限难度板刷，然后就恰好刷到了同一个比赛（1427）的三题
C. The Hard Work of Paparazzi
一个 \(R\times R\) 的矩形上有 \(n\) 个点，你初始在 \((1,1)\)。每个点 \(P_i\) 除了给你位置外还有一个时间 \(t\)，当你在 \(t\) 时刻到这个点的时候，你就可以给小青蛙+1s。问你能给小青蛙加几秒。 \(R\le 500,n\le 1e5\)
你走路方式是上下左右四个相邻的走（也就是曼哈顿距离）。可以停下来。保证给定的 \(t\) 是 严格单增 的。
看到 严格单增 我想到的是去年普及 T2。这题其实也有类似的性质，设 \(dp[i]\) 表示到第 \(i\) 个点最多续几秒。然后对于 \(i-2R\) 前面的所有 \(dp\) 值就都可以直接继承了（在这个矩形上走 \(2R\) 步哪里都能到，显然）
然后中间这些 \(dp\) 需要判断一下，假设转移点为 \(j\)，是否 \(dis(P_i,p_j)\le t_i-t_j\)。如果是的话，就可以多续一秒。
我们发现这样的复杂度从 \(n^2\) 降到了 \(nR\) ，就可以过了。注意一个细节就是你其实是可以从 \((1,1)\) 这个点开始转移的，为了方便可以令它为 \(P_0\)，转移的时候考虑一下 \(j=0\)。
D. Unshuffling a Deck
傻逼构造
E. Xum
构造好题。
你有一个 \(x\)，为奇数，\(\le 1e5\)。初始时黑板上写着 \(x\)。每次你可以选择两个数 \(a,b\)，满足它们都在黑板上并且不同，然后你可以写下 a+b 或 a^b 在黑板上，你的目标是写上一个 \(1\) 。构造方案。操作数不能超过 \(10^5\)。
首先明确几个显然的事实。
- 可以实现左移（自己加自己即可）
- 可以实现乘法 \(a\times k\)，其中 \(a\) 在黑板上有，\(k\) 任意 （这个就先把 \(a\) 不断的左移，然后把 \(k\) 二进制拆分，累加即可）
- 如果 \(x\) 是偶数，那么
x^(x+1)==1，这个够显然吧
然后我们发现 \(x\) 一定和 \(2^k\) 互质，因为它是奇数。那么我们只要写上一个 \(2^k\)，求一遍 \(exgcd\)，做俩乘法得到一个 \(x\) 多少倍和一个 \(2^k\) 多少倍，差为 \(1\)。俩异或起来就得到 \(1\) 了。
关键是如何写出这个 \(2^k\)。
注意到这样一个事情。如果我们能把 \(x\) 的最后一位删掉，然后让它和 \(x\) 异或一下，就能得到一个 \(1\)。
对于一个 \(x\times 2^k\)，我们如果能把它最后一位删掉，再和 \(x\times 2^k\) 以后一下，就能得到一个 \(2^k\)。
如何删掉呢？我们把 \(x\) 不断左移，使得它的最后一位和 \(x\) 最高位对齐，设这时候为 \(x_2\)。然后 \(x_2\) 异或一下 \(x\)，得到 \(x_3\)。你就会发现它原来的最后一位的 \(0\) 没了。
但离 \(2^k\) 还差得远。
令 \(x_2+x_3\) 得到 \(x_4\)。我们发现高的几位它们都相同，这一段相当于左移了。然后上一次说变成 \(0\) 的那一位，因为加了 \(x_2\)，又变成了 \(1\)。
我们发现这东西长度正好两半，前面是 \(x-1\)，后面是 \(x\)。
接下来就好办了，把 \(x\) 左移过去（其实就是 \(x2\) 左移一个），和它异或一下；再让它异或一下 \(x\)，它就只剩一位，变成了 \(2^k\)。
举个例子，\(x=100110110111\)，二进制。
100110110111 x2
100110110111 x1
10011011011000110110111 x3
100110110110100110110111 x4
↑ 这是我在小本本上打的草稿qaq
我们发现 \(x_4\) 这个玩意就是前面是 \(x-1\) 后面是 \(x\) 了，两次异或即可。
然后这个做法似乎在 \(x\) 全 \(1\) 的时候有锅？我可能没想明白，反正特判了一下。
关于操作数，实际上只有做乘法暴力拆二进制的时候带一个 \(\log\)，所以操作数的规模是 \(\log\) 的。但是好像我写的麻烦，要做很多遍。反正 \(1e5\)，问题不大。
PS：最开始先搞一个 x^x 得到 \(0\)，方便累加和