构造题练习笔记

例一 hdu7393 ：

题意：

​ 有 \(n\) 个人，每个人头上有个 \(1...m\) 之间中的某个数字，每个人都能看到其他所有人的数字，但是看不到自己的数字，求一种整体策略，使得至少 \(\lfloor \dfrac{n}{m} \rfloor\) 个人猜对自己头上的数字。

​ \(m\le n\)

解答：

​ 如果直接在 \([1,m]\) 中猜的话概率期望 \(E=\dfrac{n}{m}\) 看样子是符合的，但是太不稳定了，我们要想一种方法使其稳定（让自己知道哪些一定对）。可以发现，答案的总和 \(S\) 始终不变，所以我们可以想到对 \(S\) 进行猜测，因为 \(S\) 太大了，每次猜测每个数字不用这么大，所以可以对 $S\bmod m $ 进行猜测（原因在后面）。对于第 \(i\) 个人，我们猜测 $S\bmod m=i \bmod m $ 因为知道了其他人的数字总和，所以只需要找到数字 \(x\) 使其满足前面的式子，这个 \(x\) 就是我们猜测的值，并且在 \([1,m]\) 中只会存在一个 \(x\)。可以发现，我们一定会猜到 \(\lfloor \dfrac{n}{m} \rfloor\) 次正确的 $S\bmod m $ ，也就是猜对 \(\lfloor \dfrac{n}{m} \rfloor\) 个人头顶的数字。

总结：

​ 这道题通过对猜测进行分组，来使不确定的事确定，让猜测更加稳定。

例二 CF1672E 交互题：

题意：

​ 给你 \(n\) 个单词，每个单词有一个长度 \(l_i\)，你最多可以查询 \(n+30\) 次，每次给出一个宽度 \(w\) ,交互器会告诉你需要多少行宽度为 \(w\) 才可以放下所有单词，要求找到使用面积最小的方案，其中一行内放 \(l_1...l_k\) 需要的长度至少是 \(l_1+l_2+..+l_k+(k-1)\) 。

​ \(n,l_i\le2000\)

解答：

​ 分析查询次数可以发现近似是 \(n+log n\)，可以想到是一次二分加上一次遍历。考虑怎么处理，首先我们需要二分出把单词都放在一行时的长度，也就是 $单词总长+n-1 $ 设此值为 \(S\) ，再考虑高度大于一的情况，我们可以发现当 \(w_i\cdot h_i \le S\) 也就是 \(w_i \le \lfloor \frac{S}{h_i} \rfloor\) 时才会有更佳的情况产生。同时因为 \(w_i\cdot h_i\ge 单词总长\) 所以 \(w_i \ge \lfloor \frac{S}{h_i} \rfloor\)。神奇的发现只有 \(w_i=\lfloor \frac{S}{h_i} \rfloor\) 才会出现更佳的情况，所以我们直接遍历 \(h_i,n \ge h_i\ge 2\) 运算每一个对应的 \(w_i\) 询问，看其返回的 \(h'\cdot w_i\) 是否是更佳。

例三 CF1887E ：

题意：

Alice和你玩游戏，有一个 \(n\cdot n\) 的网格，最开始Alice会在其中 \(2n\) 个格子涂上从 \(1\) 到 \(2n\) 不一样的颜色，接着你可以选择一个未涂有颜色的格子让Alice在 \(2n\) 个颜色里选择一个颜色并涂上并返回她涂的颜色，你最多进行 \(10\) 次操作并且构造出存在四个方格拥有不同颜色且在一个平行于网格边的矩形上。

\(n\le 1000\)

解答：

将在 \((x,y)\) 涂上颜色 \(c\) 可以看作在点 \(x\) 和 \(y\) 中间连了一条权值为 \(c\) 的边，那么就变成了一个 \(2n\) 节点的二分图，现在我们的操作就是在 x,y 之间连一条权值未知的边，目标变成了构造出一个循环长度为4且边权不一样的环。由于存在了 \(2n\) 个点，连了 \(2n\) 条边，因为二分图没有奇环，所以会出现一个偶数环，我们可以在其中间划一条边，并且端点不是同一颜色，将这个环的大小从 \(l\) 分成大小约是 \(\frac{l}{2}+1\) 的两个小环。因为对于这个环上的边颜色互不一样，所以划了一条边之后至少会有一个小环上的边颜色互不一样。一直划下去就会出现目标情况。

例四 CF1270G ：

题意：

给你 \(n\) 个整数的序列 \(a\) 对于 \(a_i\) 满足 \(i-n\le a_i \le i-1\) 。找出一个非空子集，使其和为 \(0\)，输出这个子集每个元素的对应位置。

解答：

因为 \(i-n\le a_i \le i-1\) 所以可以转换成 \(1\le i-a_i \le n\) 。我们可以发现，对于一个非空子集 \(S\) ，使其和为 \(0\)。所以说 \(i-a_i\) 肯定有一个对应的点。如果形成一个环，对于环上的点 \(i\) 我们会发现，在环内指向 \(i\) 的点的值是 \(i-a_i-a_{i-a_i}-a_{i-a_{i-a_i}}...\) 由上面的式子可知 \(i=i-a_i-a_{i-a_i}-a_{i-a_{i-a_i}}...\) 也就是 \(a_i+a_{i-a_i}+a_{i-a_{i-a_i}}...=0\) 因为\(i-a_i\) 肯定有一个对应的点，一个环内节点号不相同，所以这个序列就是满足条件的集合，输出其节点编号就是答案。