跳转至

构造

构造题是比赛中常见的一类题型。

从形式上来看,问题的答案往往具有某种规律性,使得在问题规模迅速增大的时候,仍然有机会比较容易地得到答案。

这要求我们在解题时,要思考问题规模增长对答案的影响,这种影响是否可以推广。(比如在设计动态规划方法的时候,要考虑从一个状态到后继状态的转移会造成什么影响)。

例题:

Example 1

Problem

Vladik and fractions

题目大意:构造一组 x,y,z,使得对于给定的 n,满足 \dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}

Solution

样例二已经暴露了此题的本质(复读机

显然 n,n-1,n(n-1)为一组合法解。特殊地,当 n=1时,无解。

至于构造思路是怎么产生的,大概就是观察样例加上一点点数感了吧。此题对于数学直觉较强的人来说并不难

Example 2

Problem

Luogu P3599 Koishi Loves Construction

Solution

对于 task1:

n为奇数时,无法构造出合法解;

n为偶数时,可以构造一个形如 n,1,n-2,3,\cdots这样的数列。

首先,我们可以发现 n必定出现在数列的第一位,否则 n出现前后的两个前缀和必然会陷入模意义下相等的尴尬境地;

然后,我们考虑构造出整个序列的方式:

考虑通过构造前缀和序列的方式来获得原数列,可以发现前缀和序列两两之间的差在模意义下不能相等,因为前缀和序列的差分序列对应着原来的排列。

因此我们尝试以前缀和数列在模意义下为

0,1,-1,2,-2,\cdots

这样的形式来构造这个序列,不难发现它完美地满足所有限制条件。

对于 task2:

n为除 4以外的合数时,无法构造出合法解

n为质数或 4时,可以构造一个形如 1,\dfrac{2}{1},\dfrac{3}{2},\cdots,\dfrac{n-1}{n-2},n这样的数列

先考虑什么时候有解:

显然,当 n为合数时无解。因为对于一个合数来说,存在两个比它小的数 p,q使得 p\times q \equiv 0 \,(mod\;n),如 (3\times6)\%9=0。那么,当 p,q均出现过后,数列的前缀积将一直为 0,故合数时无解。特殊地,我们可以发现 4=2\times 2,无满足条件的 p,q,因此存在合法解。

我们考虑如何构造这个数列:

和 task1 同样的思路,我们发现 1必定出现在数列的第一位,否则 1出现前后的两个前缀积必然相等;而 n必定出现在数列的最后一位,因为 n出现位置后的所有前缀积在模意义下都为 0。手玩几组样例以后发现,所有样例中均有一组合法解满足前缀积在模意义下为 1,2,3,\cdots,n,因此我们可以构造出上文所述的数列来满足这个条件。那么我们只需证明这 n个数互不相同即可。

我们发现这些数均为 1 \cdots n-2的逆元 +1,因此各不相同,此题得解。


评论