ARC184 A ~ D

A

注意到 \(950=1000\times\dfrac{19}{20}\)，考虑把序列按 \(B=20\) 分块。

每次对于一块 \([l,r]\)，考虑把每个数和 \(l\) 问一遍，可以把 \(B\) 个数划分为两个集合。如果两个集合大小不同，那么其中大小较小的就是假币；否则所有假币都在某个集合中，再问一次即可确定哪个集合为假币。

注意一个边界是在最后一块两个集合大小相同时，再问一次会多一次询问，一个办法是把 \([l,n-1]\) 都和 \(1\) 问，然后根据当前假币个数确定 \(n\)。

https://atcoder.jp/contests/arc184/submissions/58110108

B

如果两个数 \(x,y\) 在忽略 \(2,3\) 质因子后不同，那么 \(x,y\) 是独立的，可以分开算。

那么现在只需要考虑形如 \(2^a3^b\) 的数了，把 \(2^a3^b\) 对应到网格上的 \((a,b)\) 位置，那么操作一次 \(2^a3^b\) 相当于覆盖了 \((a,b),(a+1,b),(a,b+1)\)。令其中的关键点为 \((a+1,b)\)。

考虑状压 dp，\(f_{i,S}\) 表示从下往上考虑到第 \(i\) 行，这一行关键点的集合为 \(S\) 的最少操作次数。转移就是做一个高维前缀 \(\min\)。这样做一次就是 \(2^{\log_3n}\log n\) 的。整除分块一下可过。

https://atcoder.jp/contests/arc184/submissions/58105316

C

令 \(1\) 代表山折，\(0\) 代表谷折，\(f_i\) 表示第 \(i\) 条折痕的种类。

一个重要的观察是 \(f_{2i}=f_i\)，\(f_{2i+1}=i\bmod2\)。前一个可以考虑忽略最后一次折叠；后面一个考虑在最后一次折叠前，相邻折痕之间的纸带一定是正反交替的，这个可以归纳证明。

不妨把 \(f\) 改写成更简单的形式：\(f_i=\lfloor\dfrac{i}{2\operatorname{lowbit}(i)}\rfloor\bmod 2\)。

注意到把 \(A\) 整体加 \(k\) 后，其相对大小不变。考虑钦定 \(A_x+k\) 有最大的 \(\operatorname{lowbit}\)，设为 \(2^b\)，那么其它的 \(A_i+k\) 的 \(\operatorname{lowbit}\) 已经确定，再钦定 \(A_x+k\) 的第 \(b+1\) 位即可推出所有 \(f_{A_i+k}\)。直接暴力就是 \(n^2\log V\)。

https://atcoder.jp/contests/arc184/submissions/58107838

D

首先把两个排列看成平面上 \(n\) 个点 \((X_i,Y_i)\)。方便起见，再添加两个虚点 \((0,n+1)\)，\((n+1,0)\)。

不难发现，无论如何操作，最终保留的范围一定是若干个左上往右下的矩形，且相邻两个共一个顶点。

于是考虑从左往右 dp，\(f_i\) 表示当前矩形的右下角为点 \(i\) 方案数。

转移直接枚举上一个点 \(j\)，但是这样会算重，再钦定中间没有点能在不删点的情况下修改范围即可。

https://atcoder.jp/contests/arc184/submissions/58120346