题目链接：https://www.luogu.org/problemnew/show/P1118
这题直接用全排列会超时，需要找出规律，用杨辉三角计算规律优化。
假设一个排列数字用a,b,c,d....代替，那么它最终的和是有规律的：
如果n为4，那么sum是a+3b+3c+d。
如果n为5，那么sum是a+4b+6c+4d+e。
如果n为6，那么sum是a+5b+10c+10d+5e+f。
即排列到哪个数，我们就能快速算出（O(1)）目前为止这个排列最终的和，而不用一步一步模拟求和下去，节省了很多的时间
70，直接暴力全排列判断和
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1e6+5; 12 int vis[maxn],used[maxn],t[maxn]; 13 int n,sum,f; 14 int js() 15 { 16 for(int i=1;i<=n;i++) t[i]=used[i]; 17 for(int i=n;i>1;i--) 18 { 19 for(int j=1;j<=i-1;j++) 20 { 21 t[j]+=t[j+1]; 22 } 23 } 24 25 return t[1]; 26 } 27 28 29 void so(int step) 30 { 31 if(f) return; 32 if(step==n+1) 33 { 34 int ans=js(); 35 if(ans==sum) 36 { 37 for(int i=1;i<=n-1;i++) cout<<used[i]<<' '; 38 cout<<used[n]<<endl; 39 f=1; 40 } 41 return; 42 } 43 44 for(int i=1;i<=n;i++) 45 { 46 if(!vis[i]) 47 { 48 vis[i]=1; 49 used[step]=i; 50 so(step+1); 51 vis[i]=0; 52 } 53 } 54 } 55 56 int main() 57 { 58 ios::sync_with_stdio(false); cin.tie(0); 59 60 cin>>n>>sum; 61 62 so(1); 63 64 return 0; 65 }
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1e6+5; 12 int vis[maxn],used[maxn],t[maxn]; 13 int n,sum,f; 14 int js() 15 { 16 for(int i=1;i<=n;i++) t[i]=used[i]; 17 for(int i=n;i>1;i--) 18 { 19 for(int j=1;j<=i-1;j++) 20 { 21 t[j]+=t[j+1]; 22 } 23 } 24 25 return t[1]; 26 } 27 28 29 void so(int step) 30 { 31 if(f) return; 32 if(step==n+1) 33 { 34 int ans=js(); 35 if(ans==sum) 36 { 37 for(int i=1;i<=n-1;i++) cout<<used[i]<<' '; 38 cout<<used[n]<<endl; 39 f=1; 40 } 41 return; 42 } 43 44 for(int i=1;i<=n;i++) 45 { 46 if(!vis[i]) 47 { 48 vis[i]=1; 49 used[step]=i; 50 so(step+1); 51 vis[i]=0; 52 } 53 } 54 } 55 56 int main() 57 { 58 ios::sync_with_stdio(false); cin.tie(0); 59 60 cin>>n>>sum; 61 62 so(1); 63 64 return 0; 65 }
60，剪枝后60分...可能是每次计算太花费时间
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1e6+5; 12 int vis[maxn],used[maxn],t[maxn]; 13 int n,sum,f; 14 int js(int n) 15 { 16 for(int i=1;i<=n;i++) t[i]=used[i]; 17 for(int i=n;i>1;i--) 18 { 19 for(int j=1;j<=i-1;j++) 20 { 21 t[j]+=t[j+1]; 22 } 23 } 24 25 return t[1]; 26 } 27 28 29 void so(int step,int ans) 30 { 31 if(f || ans>sum) return; 32 if(step==n+1 && ans==sum) 33 { 34 for(int i=1;i<=n-1;i++) cout<<used[i]<<' '; 35 cout<<used[n]<<endl; 36 f=1; 37 return; 38 } 39 40 for(int i=1;i<=n;i++) 41 { 42 if(!vis[i]) 43 { 44 vis[i]=1; 45 used[step]=i; 46 so(step+1,js(step)); 47 vis[i]=0; 48 } 49 } 50 } 51 52 int main() 53 { 54 ios::sync_with_stdio(false); cin.tie(0); 55 56 cin>>n>>sum; 57 58 so(1,0); 59 60 return 0; 61 }
100，看题解明白用杨辉三角数学方式找规律计算....
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1e6+5; 12 int vis[maxn],used[maxn]; 13 int yh[1005][1005]; 14 int n,sum,f; 15 16 void so(int step,int ans) 17 { 18 if(f || ans>sum) return; 19 if(step==n+1 && ans==sum) 20 { 21 for(int i=1;i<=n-1;i++) cout<<used[i]<<' '; 22 cout<<used[n]<<endl; 23 f=1; 24 return; 25 } 26 27 for(int i=1;i<=n;i++) 28 { 29 if(!vis[i]) 30 { 31 vis[i]=1; 32 used[step]=i; 33 so(step+1,ans+used[step]*yh[n][step]);//或者i*yh[n][step] 34 vis[i]=0; 35 } 36 } 37 } 38 39 int main() 40 { 41 ios::sync_with_stdio(false); cin.tie(0); 42 43 cin>>n>>sum; 44 45 yh[1][1]=1;//构造杨辉三角型 46 for(int i=2;i<=n;i++) 47 { 48 for(int j=1;j<=i+1;j++) 49 { 50 yh[i][j]=yh[i-1][j-1]+yh[i-1][j]; 51 } 52 } 53 54 so(1,0); 55 56 return 0; 57 }
完。