构造

Vision271 · 2022-09-14 19:53:44 · 个人记录

概述

• 先空着。

例题

CF1599A

• 题意：现有 n 个砝码，求一种放置方案，使得每次放置后天平较重的一边符合给出的字符串。

• 数据范围：

• 首先有一个很美妙的结论：将砝码按重量升序排序，然后按奇偶性放到对应盘上（先放左盘），每次放完之后一定是刚放完的一边更重。

  • 如果恰放了偶数个，显然 w_{2i}>w_{2i-1}，故 \sum w_{2i}>\sum w_{2i-1}。

  • 如果恰放了奇数个，考虑除 w_1 外的其他砝码，有 w_{2i+1}>w_{2i}，故 \sum w_{2i+1}>\sum w_{2i}。

• 从这里我们有三个推论：

  • 对一个放了 i 个砝码的天平，将一个绝对重于任何一个已放砝码的砝码放到和最重砝码不同的盘，重盘改变。

  • 对一个放了 i 个砝码的天平，将一个绝对轻于任何一个已放砝码的砝码放到和最轻砝码不同的盘，重盘不变。

  • 以上两种变换后，天平仍然符合上面结论的形式，称为“合法天平”。

• 接下来给出一种构造。

  • 定义 cnt 为重盘改变的次数。

  • 不妨将 w_{n-cnt} 放在左盘。如果对应字符串不以 L 起始，不妨将字符串反转，输出的时候再反转回来。

  • 维护两个指针 l,r，初始时分别指向 n-cnt-1 和 n-cnt+1。

  • 接下来对于每个 i>1，分类讨论：

    • 如果 s_i\neq s_{i-1}，将右指针所指的砝码放到 s_i 盘上。然后++右指针。

    • 如果 s_i=s_{i-1}，将左指针所指的砝码放到和上次左指针所放的盘不同的盘上，然后--左指针。

    • 特别地，这个“和上次左指针所放的盘不同的盘”初始时认为是和 w_{cnt} 所在的盘不同的盘。

• 这个构造乍一看和上面的结论同构，但事实上我们还是得严谨地证一下。

  • 连同 w_{n-cnt} 在内的“右指针砝码”显然构成了一个合法天平，这里的合法天平指的是符合那个结论的天平。

  • “左指针砝码”显然也构成了一个合法天平。

  • 现在尝试把两者拼到一起，看看是否仍然合法。

    • 都放了偶数个：显然合法。

    • 上（右指针砝码）奇下（左指针砝码）偶：可以认为是从都是偶数个的情况又放了一个右指针砝码转移来的。显然，加合天平的重盘一定改变，符合对应右指针砝码的要求，故本加合天平是从合法天平做合法转移得到的，同样合法。

    • 上偶下奇：不妨将孤立考虑上天平时的重盘记为 chosen，注意到 chosen 恰不是 w_{n-cnt} 所在盘。然后孤立考虑下天平，发现奇数编号的左指针砝码在 chosen 盘上，故 chosen 盘比非 chosen 盘的砝码数多 1 且重量交替出现，符合合法天平的定义。事实上，这也可以递推证明，下同，但我们也用一用直接证明的方式。

    • 上奇下奇：同上，此时上天平 chosen 多一个，下天平非 chosen 多一个，适当编号可以发现，chosen 上的砝码总是编号较大即较重的，符合合法天平定义。

[AGC007B] Construct Sequences

• 题意：给出 1\sim n 的排列 p_n，试构造 a_{1\sim n},b_{1\sim n}，使其满足如下条件：

• 数据范围：n\leqslant 2\times 10^4。

• 一个简单的想法是，如果我们保证了一开始 \forall(i,j) a_i+b_i=a_j+b_j，譬如 a_i=i,b_i=n-i(+1)（这个 +1 可以不要），那么我们可以令 b_{p_i}+=i。

• 但这会破坏 b 的性质。解决办法：反正增量 \leqslant n，给初始构造的 a,b 乘一个 >n 的系数就好了。给它留够调整的空间。

• 复杂度 O(n)。

CF1495C Garden of the Sun

• 题意略。

• 观察到每个 X 在其所在九宫格中都是唯一的，考虑用暴力一点的方式，即先把一些行填满。

• 发现奇偶填还是会有环，故按 \bmod 3 分组填。但可能不连通，于是向上/下搞“梁”，注意两个满行之间必须有一个“梁”，但若最后一行恰与上个满行距离为 2，则其必须有所有“梁”。

• 处理一下细节就可以解决，O(\sum n\times m)。

CF1736D Equal Binary Subsequences

• 题意略。

• 我们设法只做有效操作，即置换环中相邻相异。于是问题变成交替取合计偶数个 0/1，取反它们。

• 考虑一个暴力构造：奇数位分给 sub_1。于是如果 s_i\neq s_{i+1}(i\equiv 0\pmod 2)，取其中和 lst 不同的一个加入置换环。

P8866 [NOIP2022] 喵了个喵

• 题意略。

• 首先看到 K=2n-2 的部分分。

  • 不妨称每个栈有两个“端口”，但下端口仅在还有至少一个空栈时可消去其上的元素。

  • 于是铺满前 n-1 个栈的 2n-2 个端口，然后无脑消即可。

• 考虑推广到 K=2n-1。首先手模小数据发现有时候需要磊三个，有时候需要占用那个空栈，较为复杂。

• 磊三个：

  • 不妨称 nxt_i 为第 i 张牌的后继，所谓后继，就是下一个和它相同的牌的位置。

  • 于是对于 nxt_{dw}<nxt_{up} 的栈，我们可以在上面再磊一个，因为中间那张牌必然不是第一个消掉的。

• 用空栈：

  • 当上面的情况不成立的时候，使用空栈一定合法。

  • 因为每个下端口都会变成上端口（其上端口更早消掉）。

  • 但如果上端口先消掉又放上去，使得 nxt_{dw}<nxt_{up} 了呢？

  • 发现好像如果又要放上去，不一定能放回原来的位置。从题目保证有解（体感上一定有解）出发，大力猜结论，我们盲猜放到 nxt_{dw} 最大的栈上就可以了。

  • 理由很简洁：

    • 在上面的逻辑中我们总是保持着相同的卡不会同时在栈中出现（换言之，奇数个放入，偶数个消掉）。

    • 又显然 n=1 没有讨论价值，于是可以认为 n\geqslant 2。

    • 于是我们放到 nxt_{dw} 最大的栈中，即使仍然有 nxt_{dw}<nxt_{up} 也不重要，因为总有至少一个栈的 siz<2，且对应的 nxt_{dw} 小于这个栈的 nxt_{dw}。

    • 于是那个栈会先空掉，在下端口所需的牌出现前我们会先得到一个空栈。

    • 推广到多轮情况看似不太严谨（可能先生成空栈又占用），故我们理一下逻辑顺便打个补丁，效果如下：

• 若有不满栈（即 siz=1）：放 nxt_{dw} 最大的不满栈。

• 否则，若有合法栈（即 nxt_{dw}<nxt_{up}）：放任意合法栈。

• 否则：放空栈。

• 发现此时生成空栈之后，空栈不会被堵上或堵上了也无所谓，因为上面的“放到 nxt_{dw} 最大的栈”上面要么构成合法栈（空栈不会被堵上），要么不依赖空栈（堵上了也无所谓）。

• 更严谨的证明我无法给出。不过实际上嘛，过了我能找到的数据。

• 这一思路是在线构建的。所谓在线，指的是扫到一张牌就把一张牌的决策定下来（毕竟它要预处理 nxt 的）。然而事实上输出格式要求先输出一个总操作数，故这实际上是我审题失误的产物（还因此挂过，幸亏我是 vp）。

• 另一种更妙的思路：反悔。

• 前 n-1 个栈的端口用完后，无脑放到最后的空栈上。

• 之后如果第 k 个栈需要用空栈，看看 k_{up} 和 emp_{up} 谁早：

• 可以证明，这种做法要么是有一个空栈，要么是有一个特殊栈。特殊栈的来源必定是空栈上直接放一个，而两种反悔操作都会回到有空栈的状态。

• 故其反悔操作一定合法，不存在叠放顺序不对的问题。

AGC059B Arrange Your Balls

• 题意略。

• 不妨设有 k 种颜色的球，容易证明，答案上界为 k，下界为 k-1。

  • 上界：直接排序可得。

  • 下界：将每种颜色的球视为一个点，则显然这张图需要连通。

• 发现这点之后考虑把放球过程抽象成一个类欧拉环游序。如果能成功，那么换言之这些点构成一棵树，从而答案为 k-1，否则为 k。

• 这里的所谓类欧拉环游序，指的是进入某个节点代表着放了对应颜色的 >0 个球。注意最后必须回到起点，否则相当于是在终点和起点之间连了一条边，不是树了。

• 从而我们意识到，一个点至多被进入 cnt_i 次，cnt_x 为颜色为 x 的球的数量。那么，至少呢？

• 于是问题变成，对 n 个点求生成树，要求 deg_i\leqslant cnt_i，问是否可行。

• 直觉上这个问题是定态，即用什么方式来生成没啥区别。结论是这样的：n\geqslant 2k-2，因为每次会花 2 的 cnt。

• 我觉得我没有完全理解...

P5260 [JSOI2013] 超立方体

• 题意：

  • 判断给出的 n 个点的图是否与某一维的超立方体图同构。

  • 一个图是超立方体图，当且仅当 \forall u\leftrightarrow v,u\oplus v=2^k（超立方体图的点从 0 开始编号）。该命题是充要的。

  • 若是，输出任意重新编号的方案，使其是超立方体图。

• 数据范围：T\leqslant 3,n\leqslant 32768(2^{15}),m\leqslant 10^6。

• 首先容易想到，记 dim=\log_2 n，则必须有 n=2^{dim},deg=dim,m=2^{dim}\times \frac{dim}{2}=2^{dim-1}\times dim。

• 然后我们考虑如何构造方案。

• 容易证明，应该有很多种本质同构的构造方案，毕竟超立方体具有某种程度上的对称性，我不太好描述，但大概就是...把任意合法的编号方案在某一维上“转”一下，应该还是合法的。

• 故，随便选一个点为 0，出于方便我们选原图的 0 为 0。进一步地，把和 0 相连的 dim 个点随便编号一下，然后...

• 考虑画图，我们从 0 开始一步步地把这个图还原出来。灵机一动可以发现，这是一个类生成树（因为它不是树），dep 层的点的编号的 ppc=dep，有 dep 个父亲，dim-dep 个儿子。

• 那么很容易想到下一层的点是哪些，问题是点和编号的对应关系呢？注意到父节点到子节点是某一位上变成 1，遂意识到可以直接把一个点的所有父亲的编号或起来得到它的编号。

• 于是问题得解？并不，这样交了一发发现有些无解情况没有判出来，尽管维数很小的手造样例中似乎不存在这种可能。

• 重新审题。题目中的信息往往是有必要的，“该命题是充要的”，故考虑检查编号方案的合法性，就可以过了。

LOJ #3568.「COCI 2021.11」超方形

• 题意...原题意很清楚，自己看吧。注意超方形的点数应为 2^n，编号为 0\sim 2^n-1，这里题面笔误了。

• 做完上面那道题之后现在是不是觉得自己 Ad-hoc 上了？

• 注意到我们要放 2^{n-1}\times n=2^n\times \frac{n}{2} 条边，事实上就是要放满。另外每棵树 n+1 个点，故树点总共 2^{n-1}\times (n+1) 个，而超方形上总共只有 2^n 个点，故点大概是要相交的。

• 考虑我们上面的生成树，它的深度是多少？0\sim n，一共 n+1 层...那么每条链上有 n 条边。嘶...但是这个东西每两层之间的边数不等，没法直接取 2^{n-1} 条长为 n+1 的链出来，更进一步地，画图可以发现它是上下对称的枣核形。

• 有一个从直觉出发的，感性理解上正确的构造：

  • 既然生成树不能用，考虑找点别的性质，至少要数量相等的，毕竟树是同构的。

  • 将第 i 位取反所得到的边应当恰为 2^{n-1} 条。嗯？嗯嗯？？嗯嗯嗯？？？

  • 遂考虑每次搭一棵树，要求则是总是走没有走过的类型的边，这里类型就是按取反哪一位来分的。

  • 只要能实现就赢了。我们给出一种实现，并证明这种实现下，树边两两不交：

  • 首先对树 dfs 一遍，规定 u\to v 的边在超方形上应当是将 2^v 位取反（树的点也是从 0 开始编号的）。为了计算方便，我们可以转而记录是它的树上前缀异或和，这样只要用根的编号异或之就可以得到对应点了。

  • 于是容易证明不同树上的对位点不同，故如果相交，只可能是一对点在这两棵树上父子置换。

  • 考虑到点数非常小，以每个点为根都尝试一遍，不成功就撤销，复杂度在 O(2^n\times (n+1)) 左右，已经足够通过了。

  • 不过这道题是 EI 大神给我讲的，里面用了一个非常自信的写法：按 __builtin_parity() 分类，一半当根，另一半不当根。这非常妙：这代表着同深的点的 ppc 是相同的，故不可能这样父子置换，一定不合法！

  • p.s.这里的 dfs 必须以 n 为根，否则的话会认为要经过一条改动第 n 位的边，而显然不存在这样的边和其中至少一个端点。