原题
题目连接 http://poj.org/problem?id=3187
题目分析
这道题的难点在于搜的技巧, 仔细观察会发现有些规律, 就如样例一 3 1 2 4 怎么得到 16 的, 事实上是 3*c(0,3)+1*c(1,3)+2*c(2,3)+4*c(3,3), 具体为什么是这样可以参考杨辉三角, 看每个数字贡献多少值即可. 因此直接用全排列搜, 搜到答案的话肯定是字典序最小的.
代码
- #include <iostream>
- #include <algorithm>
- #include <utility>
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <map>
- #include <set>
- using namespace std;
- typedef long long LL;
- const int INF_INT=0x3f3f3f3f;
- const LL INF_LL=0x3f3f3f3f3f3f3f3f;
- int c[11][11];
- int num[10];
- void pre()
- {
- for(int i=0;i<=10;i++)
- for(int j=0;j<=i;j++)
- {
- if(!j||j==i) c[j][i]=1;
- else c[j][i]=c[j][i-1]+c[j-1][i-1];
- }
- }
- void solve(int n,int ans)
- {
- for(int i=1;i<=n;i++) num[i-1]=i;
- do
- {
- int sum=0;
- for(int i=0;i<n;i++) sum+=num[i]*c[i][n-1];
- if(sum==ans) return ;
- }while(next_permutation(num,num+n));
- }
- int main()
- {
- // freopen("black.in","r",stdin);
- // freopen("black.out","w",stdout);
- pre();
- /* for(int i=0;i<=10;i++)
- {
- for(int j=0;j<=i;j++) printf("c[%d][%d]=%d",j,i,c[j][i]);
- cout<<endl;
- }*/
- int n,sum;
- cin>>n>>sum;
- solve(n,sum);
- cout<<num[0];
- for(int i=1;i<n;i++) printf("%d",num[i]);
- cout<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3166067.html