结合实例浅析构造题型

什么是构造？大家在日常做题中应该遇到过，构造题这一种题型，而且还是比赛中常见的一类题型。本篇将简要介绍构造题这类题型以及两个实例的展示。

一、什么是构造？

构造题是一种题型，而且还是比赛中常见的一类题型。

不同于其它的算法、数据结垢题，根据查询输出结果；构造题是让你给出一组方案，使得在一定限制内符合条件。从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案。

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

二、特点

构造题一个很显著的特点就是高自由度，也就是说一道题的构造方式可能有很多种，但是会有一种较为简单的构造方式满足题意。看起来是放宽了要求，让题目变的简单了，但很多时候，正是这种高自由度导致题目没有明确思路而无从下手。

构造题另一个特点就是形式灵活，变化多样。并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性。

三、构造题的解法

构造题的经典算法有二分、分治、排序、图论算法如网络流，2-SAT，最短路等等。也会用到一些数学公式推导求出构造方法。

考虑问题时，我们往往从小情况入手，再构造大的情况。

有时我们也会考虑特殊情况，自己添加条件限制范围。

四、举例说明

（1）构造一组，使得对于给定的n，满足 

分析：n,(n+1),n(n+1) 为一组合法解。特殊地，当 n=1 时，无解，因为此时 n+1 与 n(n+1) 相等（也可以证明没有其他形式的解）。至于构造思路是怎么产生的，大概就是观察样例加上一点点数感了吧。此题对于数学直觉较强的人来说并不难。

代码如下：

#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）经过一天辛苦的工作，小Q进入了梦乡。他脑海中浮现出了刚进大学时学01背包的情景，那时还是大一萌新的小Q解决了一道简单的01背包问题。这个问题是这样的：

给定n个物品，每个物品的体积分别为v1,v2,… vn，请计算从中选择一些物品（也可以不选），使得总体积恰好为w的方案数。因为答案可能非常大，你只需要输出答案对P取模的结果。

因为长期熬夜刷题，他只看到样例输入中的w和P，以及样例输出是k，看不清到底有几个物品，也看不清每个物品的体积是多少。直到梦醒，小Q也没有看清n和v，请写一个程序，帮助小Q一起回忆曾经的样例输入。

分析：这道题是自由度最高的构造题之一了。这就导致了没有头绪，难以入手的情况。不难发现模数是假的。由于我们自由构造数据，我们一定可以让方案数不超过模数。

代码如下：

#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;
}