「Summary」2022-07-23 做题记录

完，我怎么又是简单题调半天。。。

2022-07-21 AtCoder Beginner Contest 261

$\mathbb{A \ B \ C}$

笑死，$A$ 看了 $7min$ 没看懂题，还是在把 $E$ 过了之后才回来补的。
$B$, $C$ 都没啥好说的。

$\mathbb{D \ Flipping \ and \ Bonus}$

link
一眼 $DP$ ，然后写完死活过不了样例，发现题读错了，这个英文题面有歧义。
一个简单的思路，枚举断点，即是硬币朝上的某一次投掷，$dp_{i, 0 / 1}$ 表示第 $i$ 次朝上或朝下，可以平方级别直接转移。
然后调调调搞了半天。

$\mathbb{G \ Many \ Operations}$

link
开始想复杂了，以为是个什么高级玩意儿，可以直接合并位运算的操作，搞了半天，发现不行。
拆开看，哦，懂了，你需要分开考虑每一位的状态，只需要考虑初始值是 $0/1$ ，然后分别记录 $z_{i, j}, o_{i, j}$ ，表示如果初始时第 $j$ 位是 $0/1$ 在经过第 $i$ 次位运算之后的值为多少。
维护答案是，发现当前的答案是从上一层的答案转移下来的，把答案拆成每一位，分别加入贡献就行了。

$\mathbb{Ex}$

link
这个需要一点观察，发现是当键值相同且相邻的两个点可以压成一个，能用 tarjan 在 $\Theta(n)$ 的复杂度里面解决掉，之后需要考虑一个 $dp$ ， 定义 $dp_{i,j}$ 表示以当前的 $i$ 出发，走 $j$ 步最远到达的点，需要倍增优化。