dottle的月赛
1 | |
很有感觉。
第一步判断有没有解：我个人觉得这步十分有技术，我真的没想到拿二分图描述他。
首先考虑 \(\mathrm{popcount}\) 的奇偶性。
那么必然是交错的走，所以 \(|\mathrm{odd-even}|\le 1\)。
然后如果这个图不连通的话，也无解。就是说： \([l,2^k-1]\) 平移后与 \([2^k,r]\) 无交必然无解。
然后我们就来构造。
part1
首先感觉来说，我们必然是要找到一个分界点 \(p\)，然后从 \(p\) 走到 \(p+2^k\)，然后分别周游 \([l,2^k-1]\),\([2^k,r]\)。
我们希望从 \(p\) 周游 \([l,r]\)。
首先，若 \(p=r\) 这是容易构造的，我们可以发现按二进制拆分后，当在 \(2^k\) 小的地方。可以直接走入相邻的 \(2^k\) 大的地方。
否则有点困难。
我们始终是不希望，如果存在一个分界点，屡次跨过分界点的。
所以考虑如果我们先从 \(p\) 周游 \([l,\mathrm{lim}]\) 结束于 \(q\)，然后从 \(q\) 将后半部分走完。
直接构造原问题困难时，不妨想想简单情况，看简单情况的构造能给我们什么启示。
是的我们要去构造如果 \(r=2^k-1\) 情况的周游方案。
part2
一步转化是 \(p\to q\Longleftrightarrow 0\to (p\mathrm{\ xor\ }q)\)
记 \(p=(p\mathrm{\ xor\ }q)\)
如果 \(p\ge 2^{k-1}\) 的话可以暴力环游右边后转为子问题
否则，考虑我们先直走左面，然后将相邻的 \(u_i\to u_{i+1}\) 变成 \(u_i\to (u_i+2^{k-1})\leadsto (u_{i+1}+2^{k-1})\to u_{i+1}\)。
这样上半也是子问题。（从 \(0\to 1\)）
part3
这个第二种构造是很有启示性的。我们大概已经解决了这个周游的问题。
我们每次只看 \(p\) 所在的块，然后只构造这个块内的答案，断掉一条边转成上一个块的子问题。
然后只需要解决后半部分，从 \(q\) 周游后面那些部分。
这其实可以先从最后面走到 \(p\) 所在块内任意一个点，把这个点当成 \(q\)，然后进行上述构造即可。
我们只需要保证 \(p\not=q\) ，这也是必然的，因为如果，\(p=q\) 并且后半的终止颜色符合条件的话，那么只能说明前半的颜色都不对了，这与有解矛盾。
那么大概就完成了，这个做法实际上极其冗余。不如多老师的构造。
因为这个遍历 \(k\) 维超立方不管终点啥样实际上几乎都是同构的。
多老师直接给出了更简洁的part2做法。
描述计数对象是解决计数题第一步，也是最重要的一步。
为了更好地刻画性质，我们通常会尝试，构造双射。
我们发现，最simple的dp会算重，原因是 \(0\) 会随便跑。那么我们就很套路的将 \(0\) 钦定放到最前。
为了方便刻画，现在可以把这个整数序列映射到一个颜色序列上。
一共三种颜色 \(\mathrm{x,y,z}\)。
\(\mathrm{x}\) 代表是前缀最大值，\(\mathrm{z}\) 是紧紧跟着 \(\mathrm{x}\) 的那些删去 \(\mathrm{x}\) 会变成前缀最大值的数。
\(\mathrm{y}\) 则是我们认为他们啥用没有，摆烂的那些值。
想一想，一共限制如下：
- 如果前面是 \(\mathrm{yxz}\) 那么这一位必定不能填 \(\mathrm{z,x}\) 因为这样产生 \(0\) 但是不是最靠前的。
- 如果前面出现过 \(\mathrm{yy}\) 那就不能出现 \(\mathrm{xzx,xzy}\) 了。理由同上
特别的我们需要记录出没出现过 \(-1\) 。
所以我们可以很蠢的设 \(\mathrm{3\times 3\times 3\times 2\times 2}=108\) 种状态，暴力转移。可以通过。
多老师压成了 \(11\) 个状态，据他说是花了30min写出来的。。很强大。
兔子有个多项式做法，可是很可惜我只看到了刻画组合性质就结束了。