什么是構(gòu)造？大家在日常做題中應(yīng)該遇到過，構(gòu)造題這一種題型，而且還是比賽中常見的一類題型。本篇將簡(jiǎn)要介紹構(gòu)造題這類題型以及兩個(gè)實(shí)例的展示。

一、什么是構(gòu)造？

構(gòu)造題是一種題型，而且還是比賽中常見的一類題型。

不同于其它的算法、數(shù)據(jù)結(jié)垢題，根據(jù)查詢輸出結(jié)果；構(gòu)造題是讓你給出一組方案，使得在一定限制內(nèi)符合條件。從形式上來看，問題的答案往往具有某種規(guī)律性，使得在問題規(guī)模迅速增大的時(shí)候，仍然有機(jī)會(huì)比較容易地得到答案。

這要求解題時(shí)要思考問題規(guī)模增長(zhǎng)對(duì)答案的影響，這種影響是否可以推廣。例如，在設(shè)計(jì)動(dòng)態(tài)規(guī)劃方法的時(shí)候，要考慮從一個(gè)狀態(tài)到后繼狀態(tài)的轉(zhuǎn)移會(huì)造成什么影響。

二、特點(diǎn)

構(gòu)造題一個(gè)很顯著的特點(diǎn)就是高自由度，也就是說一道題的構(gòu)造方式可能有很多種，但是會(huì)有一種較為簡(jiǎn)單的構(gòu)造方式滿足題意。看起來是放寬了要求，讓題目變的簡(jiǎn)單了，但很多時(shí)候，正是這種高自由度導(dǎo)致題目沒有明確思路而無從下手。

構(gòu)造題另一個(gè)特點(diǎn)就是形式靈活，變化多樣。并不存在一個(gè)通用解法或套路可以解決所有構(gòu)造題，甚至很難找出解題思路的共性。

三、構(gòu)造題的解法

構(gòu)造題的經(jīng)典算法有二分、分治、排序、圖論算法如網(wǎng)絡(luò)流，2-SAT，最短路等等。也會(huì)用到一些數(shù)學(xué)公式推導(dǎo)求出構(gòu)造方法。

考慮問題時(shí)，我們往往從小情況入手，再構(gòu)造大的情況。

有時(shí)我們也會(huì)考慮特殊情況，自己添加條件限制范圍。

四、舉例說明

（1）構(gòu)造一組，使得對(duì)于給定的n，滿足 

分析：n,(n+1),n(n+1) 為一組合法解。特殊地，當(dāng) n=1 時(shí)，無解，因?yàn)榇藭r(shí) n+1 與 n(n+1) 相等（也可以證明沒有其他形式的解）。至于構(gòu)造思路是怎么產(chǎn)生的，大概就是觀察樣例加上一點(diǎn)點(diǎn)數(shù)感了吧。此題對(duì)于數(shù)學(xué)直覺較強(qiáng)的人來說并不難。

代碼如下：

#include<bits/stdc++.h>
using namespace std;

int n;

int main()
{
    scanf("%d", &n);
    if(n == 1)  printf("-1\n");
    else  printf("%d %d %d\n", n, n+1, n*(n+1));
    return 0;
}

（2）經(jīng)過一天辛苦的工作，小Q進(jìn)入了夢(mèng)鄉(xiāng)。他腦海中浮現(xiàn)出了剛進(jìn)大學(xué)時(shí)學(xué)01背包的情景，那時(shí)還是大一萌新的小Q解決了一道簡(jiǎn)單的01背包問題。這個(gè)問題是這樣的：

給定n個(gè)物品，每個(gè)物品的體積分別為v1,v2,… vn，請(qǐng)計(jì)算從中選擇一些物品（也可以不選），使得總體積恰好為w的方案數(shù)。因?yàn)榇鸢缚赡芊浅４?，你只需要輸出答案?duì)P取模的結(jié)果。

因?yàn)殚L(zhǎng)期熬夜刷題，他只看到樣例輸入中的w和P，以及樣例輸出是k，看不清到底有幾個(gè)物品，也看不清每個(gè)物品的體積是多少。直到夢(mèng)醒，小Q也沒有看清n和v，請(qǐng)寫一個(gè)程序，幫助小Q一起回憶曾經(jīng)的樣例輸入。

分析：這道題是自由度最高的構(gòu)造題之一了。這就導(dǎo)致了沒有頭緒，難以入手的情況。不難發(fā)現(xiàn)模數(shù)是假的。由于我們自由構(gòu)造數(shù)據(jù)，我們一定可以讓方案數(shù)不超過模數(shù)。

代碼如下：

#include<cstdio>
using namespace std;
int C[25][25],F[25][20005],Pre[25][20005];
void Pre_C(){
    for (int i=0; i<=20; i++) C[i][0]=1;
    for (int i=0; i<=20; i++)
        for (int j=1; j<=i; j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
}
int main(){
    Pre_C();
    for (int i=0; i<=20; i++){
        for (int j=1; j<=20000; j++) F[i][j]=1e9;
        for (int j=0; j<=20000; j++)
            for (int k=0; k<=i; k++)
                if (j+C[i][k]<=20000 && F[i][j+C[i][k]]>F[i][j]+1){
                    F[i][j+C[i][k]]=F[i][j]+1;
                    Pre[i][j+C[i][k]]=k;
                }
    }
    int T;
    scanf("%d",&T);
    while (T--){
        int w,P,k;
        scanf("%d%d%d",&w,&P,&k);
        for (int i=1; i<=20; i++)
            if (F[i][k]+i<=40){
                printf("%d\n",F[i][k]+i);
                for (int j=1; j<=i; j++) printf("%d ",1);
                while (k){
                    int K=Pre[i][k];
                    k-=C[i][K];
                    printf("%d ",w-K);
                }
                printf("\n");
                break;
            }
    }
    return 0;
}