/*
由题意得，有两个数a,b时，t=a+b;

              有三个数a,b,c 时 t=a+2b+c

              有四个数a,b,c,d时 t=a+3b+3c+d

              ……

             不难得出，符合杨辉三角

于是，可以枚举每个系数后的值，然后进行相加，做适当的剪枝，可以得出答案
*/
#include<iostream>
#include<string>
using namespace std;

int n,t,a[25][25]={0},b[25][25][25];
struct{int x,y;}order[25][25],tr;
bool over=0;

void search(int x,int sum,int ans[],bool vis[]){
     if(over) return ;
     if(x>n)
     {
       for(int i=1;i<n;++i) cout<<ans[i]<<" ";
       cout<<ans[n]<<endl;
       over=1;
       return ;
            }

     int min=0,max=0,d=1;
     for(int i=1;i<=n;++i)
     if(vis[i]==0)
     {max+=i*b[n][x][d];min+=i*b[n][x][n-x-d+2];d++;}
     if(sum+min>t||sum+max<t) return ;
     for(int i=1;i<=n;++i)
     if(vis[i]==0)
     {
       vis[i]=1;
       ans[x]=i;
       search(x+1,sum+a[n][x]*i,ans,vis);
       vis[i]=0;
             }

     }

int main()
{
    for(int i=1;i<=20;++i)
    for(int j=1;j<=i;++j)
    {
      if(j==1||j==i) a[i][j]=1;
      else a[i][j]=a[i-1][j-1]+a[i-1][j];
      order[i][j].x=a[i][j];
      order[i][j].y=j;
            }




    for(int i=1;i<=20;++i)
    for(int j=1;j<=i;++j)
    for(int k=j+1;k<=i;++k)
    if(order[i][j].x>order[i][k].x)
    {tr=order[i][j];order[i][j]=order[i][k];order[i][k]=tr;}
    else if(order[i][j].x==order[i][k].x&&(order[i][j].y>order[i][k].y))
    {tr=order[i][j];order[i][j]=order[i][k];order[i][k]=tr;}



    for(int i=1;i<=20;++i)
    for(int j=1;j<=i;++j)
    for(int k=1;k<=i-j+1;++k)
    {
      int z;int tot=0;
      for(z=1;z<=i&&tot<k;++z)
      if(order[i][z].y>=j) tot++;
      b[i][j][k]=order[i][z-1].x;
            }

    while(cin>>n>>t)
    {
       over=0;
       int ans[25]={0};
       bool vis[25]={0};
       search(1,0,ans,vis);

           }
  //  system("pause");
    }

对于数字a[i]，它对整个答案的贡献是c[n-1][i-1]*a[i]
（系数为c[n-1][i-1]）

按照字典序dfs
最优性剪枝：如果剩下的数字按照最小的配最小的系数，最大的配最大的系数这样算出的结果仍然比所需的小，那么就一定不用再继续了，一定无解，反过来最大配最小系数得到的比所需的大，也一定无解。

常数优化：系数的数组不必每次重新sort，可以预处理

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
    int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
    return x.v<y.v;
}
bool cmp2(node x,node y) {
    return x.id>y.id;
}
bool dfs(int x,int sum) {
    if (x==n+1) {
        if (sum==0) return 1;
        return 0;
    }
    FOR(i,n) if (!used[i]) {
        int res=i*c[n-1][x-1];
        used[i]=1;
        int cnt=0;
        node *b=d[x+1];
        int res2=0;
        cnt=0;
        FOR(j,n) if (!used[j]) {
            res2+=j*b[++cnt].v;
        }
        if (res+res2<sum) {
            used[i]=0;
            continue;
        }
        res2=0;
        cnt=0;
        for (int j=n;j>=1;j--) if (!used[j]) {
            res2+=j*b[++cnt].v;
        }
        if (res+res2>sum) {
            used[i]=0;
            continue;
        }
        if (dfs(x+1,sum-res)) {
            v.pb(i);
            return 1;
        }
        used[i]=0;
    }
    return 0;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    n=20;
    REP(i,0,n) c[i][0]=1;
    FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
    while (cin>>n>>sum) {
        memset(used,0,sizeof used);
        v.clear();
        FOR(i,n) {
            int cnt=0;
            REP(j,i,n) {
                d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
            }
            sort(d[i]+1,d[i]+1+cnt,cmp);
        }
        dfs(1,sum);
        for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
        cout<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,sum;
bool used[21];
int c[21][21];
struct node {
int id,v;
} d[21][21];
vector<int> v;
bool cmp(node x,node y) {
return x.v<y.v;
}
bool cmp2(node x,node y) {
return x.id>y.id;
}
bool dfs(int x,int sum) {
if (x==n+1) {
if (sum==0) return 1;
return 0;
}
FOR(i,n) if (!used[i]) {
int res=i*c[n-1][x-1];
used[i]=1;
int cnt=0;
node *b=d[x+1];
int res2=0;
cnt=0;
FOR(j,n) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2<sum) {
used[i]=0;
continue;
}
res2=0;
cnt=0;
for (int j=n;j>=1;j--) if (!used[j]) {
res2+=j*b[++cnt].v;
}
if (res+res2>sum) {
used[i]=0;
continue;
}
if (dfs(x+1,sum-res)) {
v.pb(i);
return 1;
}
used[i]=0;
}
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=20;
REP(i,0,n) c[i][0]=1;
FOR(i,n) FOR(j,i) c[i][j]=c[i-1][j]+c[i-1][j-1];
while (cin>>n>>sum) {
memset(used,0,sizeof used);
v.clear();
FOR(i,n) {
int cnt=0;
REP(j,i,n) {
d[i][++cnt].v=c[n-1][j-1],d[i][cnt].id=j;
}
sort(d[i]+1,d[i]+1+cnt,cmp);
}
dfs(1,sum);
for (int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
cout<<endl;
}
return 0;
}

题解
算法还没改进

Link

既然是闯三角关，肯定是杨辉三角啦！

为什么我加了一个排序不等式之后第1个点还是TLE，还有其他的优化吗？？

点击查看程序源码+详细题解

虽然过了，但是楼下有人提出的20 6143311仍然跑不出

数学方法：每个位置i上的数ai*（c（n-1，i-1））

c(n-1,i-1)求的是原杨辉三角上的数打表看看就知道了，因为c的递推公式就像杨辉三角一样c:=c+c

编译通过...

├ 测试数据 01：答案正确... 478ms

├ 测试数据 02：答案正确... 650ms

├ 测试数据 03：答案正确... 212ms

├ 测试数据 04：答案正确... 166ms

├ 测试数据 05：答案正确... 72ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1619ms

判断数有无（要注意0）v[0]:=false就对了

附上写的判断爆数据测试

出数据

var n,i,t,j:longint;

v:array[0..21]of boolean;

c:array[0..21,0..21]of longint;

begin

assign(output,'01.in');rewrite(output);

randomize;

n:=6;

fillchar(v,sizeof(v),true);

fillchar(c,sizeof(c),0);

for i:=0 to 20 do

c:=1;

for i:=1 to 20 do

for j:=1 to i do

c:=c+c;

t:=0;

for i:=1 to n do begin

j:=random(n)+1;

while not v[j] do j:=random(n)+1;

inc(t,c[n-1,i-1]*j);

v[j]:=false;

end;

writeln(n,' ',t);

close(output);

end.

暴力出解（不能过的）

var v:array[0..100]of boolean;

c:array[0..21,0..21]of longint;

a:array[0..100]of longint;

find:boolean;

n,t,i,j:longint;

procedure dfs(dep,t:longint);

var i,j:longint;

begin

if tn then begin

if t=0 then begin

for i:=1 to n do write(a[i],' ');

find:=true;

end;

exit;

end;

for i:=1 to n do

if v[i] then begin

a[dep]:=i;

v[i]:=false;

dfs(dep+1,t-i*c[n-1,dep-1]);

v[i]:=true;

if find then exit;

end;

end;

begin

assign(input,'01.in');reset(input);

fillchar(c,sizeof(c),0);

for i:=0 to 20 do

c:=1;

for i:=1 to 20 do

for j:=1 to i do

c:=c+c;

while not eof do begin

fillchar(v,sizeof(v),true);

readln(n,t);

find:=false;

dfs(1,t);

find:=true;

writeln;

end;

close(input);

end.

接着膜拜雪牛！！！！

编译通过...

├ 测试数据 01：答案正确... 650ms

├ 测试数据 02：答案正确... 931ms

├ 测试数据 03：答案正确... 259ms

├ 测试数据 04：答案正确... 181ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 119ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2228ms

终于A了。。。交了9遍。。。。膜拜Claire神牛！

一个有序化，一个极大一个极小。。。

再次膜拜雪牛！！！

因为要用readln而不是read，交了n遍，一直程序输出比正确答案长，第九次才ac

├ 测试数据 01：答案正确... 1541ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 509ms

├ 测试数据 04：答案正确... 666ms

├ 测试数据 05：答案正确... 806ms

├ 测试数据 06：答案正确... 291ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 431ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4356ms

时间更丑，但较之wa，还是好些的。。。。