構造
本頁面將簡要介紹構造題這類題型。
引入
構造題是比賽中常見的一類題型。
從形式上來看，問題的答案往往具有某種規律性，使得在問題規模迅速增大的時候，仍然有機會比較容易地得到答案。
這要求解題時要思考問題規模增長對答案的影響，這種影響是否可以推廣。例如，在設計動態規劃方法的時候，要考慮從一個狀態到後繼狀態的轉移會造成什麼影響。
特點
構造題一個很顯著的特點就是高自由度，也就是説一道題的構造方式可能有很多種，但是會有一種較為簡單的構造方式滿足題意。看起來是放寬了要求，讓題目變的簡單了，但很多時候，正是這種高自由度導致題目沒有明確思路而無從下手。
構造題另一個特點就是形式靈活，變化多樣。並不存在一個通用解法或套路可以解決所有構造題，甚至很難找出解題思路的共性。
例題
下面將列舉一些例題幫助讀者體會構造題的一些思想內涵，給予思路上的啓發。建議大家深入思考後再查看題解，也歡迎大家參與分享有趣的構造題。
例題 1
Codeforces Round #384 (Div. 2) C.Vladik and fractions
構造一組 \(x,y,z\)，使得對於給定的 \(n\)，滿足 \(\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}\)
解題思路
從樣例二可以看出本題的構造方法。
顯然 \(n,n+1,n(n+1)\) 為一組合法解。特殊地，當 \(n=1\) 時，無解，這是因為 \(n+1\) 與 \(n(n+1)\) 此時相等。
至於構造思路是怎麼產生的，大概就是觀察樣例加上一點點數感了吧。此題對於數學直覺較強的人來説並不難。
例題 2
Luogu P3599 Koishi Loves Construction
Task1：試判斷能否構造並構造一個長度為 \(n\) 的 \(1\dots n\) 的排列，滿足其 \(n\) 個前綴和在模 \(n\) 的意義下互不相同
Task2：試判斷能否構造並構造一個長度為 \(n\) 的 \(1\dots n\) 的排列，滿足其 \(n\) 個前綴積在模 \(n\) 的意義下互不相同
解題思路
對於 task1：
當 \(n\) 為奇數時，無法構造出合法解；
當 \(n\) 為偶數時，可以構造一個形如 \(n,1,n-2,3,\cdots\) 這樣的數列。
首先，我們可以發現 \(n\) 必定出現在數列的第一位，否則 \(n\) 出現前後的兩個前綴和必然會陷入模意義下相等的尷尬境地；
然後，我們考慮構造出整個序列的方式：
考慮通過構造前綴和序列的方式來獲得原數列，可以發現前綴和序列兩兩之間的差在模意義下不能相等，因為前綴和序列的差分序列對應着原來的排列。
因此我們嘗試以前綴和數列在模意義下為
這樣的形式來構造這個序列，不難發現它完美地滿足所有限制條件。
對於 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 \pmod 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\)，因此各不相同，此題得解。
例題 3
AtCoder Grand Contest 032 B
給定一個整數 \(N\)，試構造一個節點數為 \(N\) 無向圖。令節點編號為 \(1\ldots N\)，要求其滿足以下條件：
- 這是一個簡單連通圖。
- 存在一個整數 \(S\) 使得對於任意節點，與其相鄰節點的下標和為 \(S\)。
保證輸入數據有解。
解題思路
通過分析 \(n=3,4,5\) 的情況，我們可以找到一個構造思路。
構造一個完全 \(k\) 分圖，保證這 \(k\) 部分和相等。則每個點的 \(S\) 均相等，為 \(\dfrac{(k-1)\sum_{i=1}^{n}i}{k}\)。
如果 \(n\) 為偶數，那麼我們可以前後兩兩配對，即 \(\{1,n\},\{2,n-1\}\cdots\)
如果 \(n\) 為奇數，那麼我們可以把 \(n\) 單拿出來作為一組，剩餘的 \(n-1\) 個兩兩配對，即 \(\{n\},\{1,n-1\},\{2,n-2\}\cdots\)
這樣構造出的圖在 \(n\ge 3\) 時連通性易證，在此不加贅述。
此題得解。
例題 4
BZOJ 4971「Lydsy1708 月賽」記憶中的揹包
經過一天辛苦的工作，小 Q 進入了夢鄉。他腦海中浮現出了剛進大學時學 01 揹包的情景，那時還是大一萌新的小 Q 解決了一道簡單的 01 揹包問題。這個問題是這樣的：
給定 \(n\) 個物品，每個物品的體積分別為 \(v_1,v_2,…,v_n\)，請計算從中選擇一些物品（也可以不選），使得總體積恰好為 \(w\) 的方案數。因為答案可能非常大，你只需要輸出答案對 \(P\) 取模的結果。
因為長期熬夜刷題，他只看到樣例輸入中的 \(w\) 和 \(P\)，以及樣例輸出是 \(k\)，看不清到底有幾個物品，也看不清每個物品的體積是多少。直到夢醒，小 Q 也沒有看清 \(n\) 和 \(v\)，請寫一個程序，幫助小 Q 一起回憶曾經的樣例輸入。
解題思路
這道題是自由度最高的構造題之一了。這就導致了沒有頭緒，難以入手的情況。
首先，不難發現模數是假的。由於我們自由構造數據，我們一定可以讓方案數不超過模數。
通過奇怪的方式，我們想到可以通過構造 \(n\) 個 代價為 \(1\) 的小物品和幾個代價大於 \(\dfrac{w}{2}\) 的大物品。
由於大物品只能取一件，所以每個代價為 \(x\) 的大物品對方案數的貢獻為 \(\dbinom{n}{w-x}\)。
令 \(f_{i,j}\) 表示有 \(i\) 個 \(1\)，方案數為 \(j\) 的最小大物品數。
用 dp 預處理出 \(f\)，通過計算可知只需預處理 \(i\le 20\) 的所有值即可。
此題得解。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：leoleoasd, yzxoi
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用