纪中20日c组模拟赛T1 2121. 简单游戏-白红宇

纪中20日c组模拟赛T1 2121. 简单游戏

阅读量：5272 次

发布时间：2019-06-14

本文共 13785 字，大约阅读时间需要 45 分钟。

T1 2121. 简单游戏

(File IO): input:easy.in output:easy.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

Charles和sunny在玩一个简单的游戏。若给出1~n的一个排列A，则将A1、A2相加，A2、A3相加……An-1、An相加，则得到一组n-1个元素的数列B；再将B1、B2相加，B2、B3相加，Bn-2、Bn-1相加，则得到一组n-2个元素的数列……如此往复，最终会得出一个数T。而Charles和sunny玩的游戏便是，Charles给出n和T，sunny在尽可能短的时间内，找到能通过上述操作得到T且字典序最小的1~n的排列。（sunny大声说：“What an easy game！”，接着几下就给出了解），Charles觉得没意思，就想和你玩，当然，你可以用一种叫做“电子计算机”的东西帮你。

输入

本题有多组数据，对于每组数据：一行两个整数n（0<n<=20），t即最后求出来的数。两个0表示输入结束

输出

对于每组测试数据输出一行n个整数，用空格分开，行尾无多余空格，表示求出来的满足要求的1~n的一个排列。

样例输入

4 16 3 9 0 0

样例输出

3 1 2 4 1 3 2 对样例解释： 开始排列：  3     1      2      4 第一次操作：3+1=4  1+2=3  2+4=6      得到：  4      3      6 第二次得到：     7     9 最后就是：        16

数据范围限制

数据保证有解。请注意加粗字体！

对于30%的数据，保证该组里的每个N都不超过10。

对于100%的数据，保证有每个N不超过20，且每组数据的个数不超过10。

Solution

首先可以发现,对于一个长度为n的排列,经过了n-1次邻项相加后,第i项被加了C(n-1,i)次(二项式定理).

所以可以先预处理杨辉三角形。

Algorithm1

使用next_permutation方便的计算地排列

但是没有剪枝...很慢的

Code1

简单的垃圾代码

1 #pragma GCC optimize(2) 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #define IL inline12 using namespace std;13 int tria[30][30]={14 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,16 0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,17 0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,18 0,1,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,19 0,1,4,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20 0,1,5,10,10,5,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,21 0,1,6,15,20,15,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,22 0,1,7,21,35,35,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,23 0,1,8,28,56,70,56,28,8,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,24 0,1,9,36,84,126,126,84,36,9,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,25 0,1,10,45,120,210,252,210,120,45,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,26 0,1,11,55,165,330,462,462,330,165,55,11,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,27 0,1,12,66,220,495,792,924,792,495,220,66,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,28 0,1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29 0,1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30 0,1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,31 0,1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1,0,0,0,0,0,0,0,0,0,0,0,0,32 0,1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1,0,0,0,0,0,0,0,0,0,0,0,33 0,1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1,0,0,0,0,0,0,0,0,0,0,34 0,1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1,0,0,0,0,0,0,0,0,0,35 0,1,20,190,1140,4845,15504,38760,77520,125970,167960,184756,167960,125970,77520,38760,15504,4845,1140,190,20,1,0,0,0,0,0,0,0,0,36 0,1,21,210,1330,5985,20349,54264,116280,203490,293930,352716,352716,293930,203490,116280,54264,20349,5985,1330,210,21,1,0,0,0,0,0,0,0,37 0,1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432,646646,497420,319770,170544,74613,26334,7315,1540,231,22,1,0,0,0,0,0,0,38 0,1,23,253,1771,8855,33649,100947,245157,490314,817190,1144066,1352078,1352078,1144066,817190,490314,245157,100947,33649,8855,1771,253,23,1,0,0,0,0,0,39 0,1,24,276,2024,10626,42504,134596,346104,735471,1307504,1961256,2496144,2704156,2496144,1961256,1307504,735471,346104,134596,42504,10626,2024,276,24,1,0,0,0,0,40 0,1,25,300,2300,12650,53130,177100,480700,1081575,2042975,3268760,4457400,5200300,5200300,4457400,3268760,2042975,1081575,480700,177100,53130,12650,2300,300,25,1,0,0,0,41 0,1,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735,7726160,9657700,10400600,9657700,7726160,5311735,3124550,1562275,657800,230230,65780,14950,2600,325,26,1,0,0,42 0,1,27,351,2925,17550,80730,296010,888030,2220075,4686825,8436285,13037895,17383860,20058300,20058300,17383860,13037895,8436285,4686825,2220075,888030,296010,80730,17550,2925,351,27,1,0,43 0,1,28,378,3276,20475,98280,376740,1184040,3108105,6906900,13123110,21474180,30421755,37442160,40116600,37442160,30421755,21474180,13123110,6906900,3108105,1184040,376740,98280,20475,3276,378,28,144 };45 //triangle46 int ans;47 int arr[50],t,n;48 IL int read()49 {50 char ch;int x=0;51 ch=getchar();52 while(ch<'0'||ch>'9') ch=getchar();53 while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();54 return x; 55 }56 int main()57 {58 freopen("easy.in","r",stdin);59 freopen("easy.out","w",stdout);60 n=read();61 t=read();62 do{63 for(int i=1;i<=n;i++) 64 arr[i]=i;65 do{66 ans=0;67 int i;68 for(i=1;i<=n&&ans<=t;i++)69 ans+=arr[i]*tria[n][i];70 if(ans==t&&i>n){71 for(int j=1;j<=n;j++){72 printf("%d",arr[j]);73 if(j

Code1

Algorithm2

使用dfs，对每一位进行判断，同时标记use（是否使用过此数）

这比next_permutation好在可以尽情剪枝——只要你能想到

Code2

这是剪枝1：如果当前的和（前depth个数的和）已经超过了t，就跳出。

也可以把

if(sum>t) return;

放到for循环里（这不是废话吗）

可以减少一点分支

按照题解上的说法，这样子只有40分（果然……）

1 #pragma GCC optimize(2) 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
           8 #include
           
             9 #include
            
             10 #include
             
              11 #define IL inline12 using namespace std;13 int tria[21][30]={14 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,16 0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,17 0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,18 0,1,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,19 0,1,4,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20 0,1,5,10,10,5,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,21 0,1,6,15,20,15,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,22 0,1,7,21,35,35,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,23 0,1,8,28,56,70,56,28,8,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,24 0,1,9,36,84,126,126,84,36,9,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,25 0,1,10,45,120,210,252,210,120,45,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,26 0,1,11,55,165,330,462,462,330,165,55,11,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,27 0,1,12,66,220,495,792,924,792,495,220,66,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,28 0,1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29 0,1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30 0,1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,31 0,1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1,0,0,0,0,0,0,0,0,0,0,0,0,32 0,1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1,0,0,0,0,0,0,0,0,0,0,0,33 0,1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1,0,0,0,0,0,0,0,0,0,0,34 0,1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1,0,0,0,0,0,0,0,0,0,35 };36 int use[21];37 int ans;38 int arr[50],t,n;39 IL int read()40 {41 char ch;int x=0;42 ch=getchar();43 while(ch<'0'||ch>'9') ch=getchar();44 while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();45 return x; 46 }47 bool succ=0;48 IL void dfs(int depth,int sum)49 {50 if(sum>t) return;51 if(succ) return;52 if(depth==n){53 if(sum==t)54 {55 succ=1;56 for(int j=1;j<=n;j++){57 printf("%d",arr[j]);58 if(j

Algorithm3

这是剪枝2：

由于杨辉三角形有对称性

比如，枚举到 2 4 1 3 时，其sum（邻项合并后的结果）会与 2 1 4 3 相同

那么可以加入以下判断：

if(depth>(n/2) && i

代码翻译

如果当前要枚举的数即将放的位置超过了总长度的一半，且即将枚举的数值i小于与它关于这个二项式对称的那一项，那就说明这两项如果调换，总值不会发生变化，那么就不考虑这种情况。

这句话真长……

Code3

1 #pragma GCC optimize(2) 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #define IL inline12 using namespace std;13 int tria[21][30]={14 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,16 0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,17 0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,18 0,1,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,19 0,1,4,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20 0,1,5,10,10,5,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,21 0,1,6,15,20,15,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,22 0,1,7,21,35,35,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,23 0,1,8,28,56,70,56,28,8,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,24 0,1,9,36,84,126,126,84,36,9,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,25 0,1,10,45,120,210,252,210,120,45,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,26 0,1,11,55,165,330,462,462,330,165,55,11,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,27 0,1,12,66,220,495,792,924,792,495,220,66,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,28 0,1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29 0,1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30 0,1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,31 0,1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1,0,0,0,0,0,0,0,0,0,0,0,0,32 0,1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1,0,0,0,0,0,0,0,0,0,0,0,33 0,1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1,0,0,0,0,0,0,0,0,0,0,34 0,1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1,0,0,0,0,0,0,0,0,0,35 };36 int use[21];37 int arr[50],t,n;38 IL int read()39 {40 char ch;int x=0;41 ch=getchar();42 while(ch<'0'||ch>'9') ch=getchar();43 while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();44 return x; 45 }46 bool succ=0;47 IL void dfs(int depth,int sum)48 {49 if(succ) return;50 if(depth==n){51 if(sum==t)52 {53 succ=1;54 for(int j=1;j<=n;j++){55 printf("%d",arr[j]);56 if(j
               
                (n/2) && i
                
                 t) continue;68 use[i]=1;69 arr[depth+1]=i;70 dfs(depth+1,sum+i*tria[n][depth+1]);71 arr[depth+1]=0;72 use[i]=0;73 }74 }75 }76 int main()77 {78 // freopen("easy.in","r",stdin);79 // freopen("easy.out","w",stdout);80 n=read();81 t=read();82 do{83 succ=0;84 dfs(0,0);85 n=read();86 t=read();87 }while(n!=0||t!=0);88 return 0;89 }

Code3

好的，果然如题解所说，这个剪枝并不能加分。

Algorithm4

这是剪枝3：枚举前，就当前还未使用的数字来讲，可以将它们重新排序，对应还没使用的系数，可以算出已选择的数字不变的情况下，让之后几个数排列组合，再乘以对应系数的和的最大值与最小值。

貌似我讲的不太清楚。

当枚举到第X个数时，剩余的N-X个数，与剩余的N-X个系数一一对应，让大数和大系数相乘，小数和小系数相乘可以得到最大值，让大数和小系数相乘，小数和大系数相乘可以得到最小值，如果剩余的值不在这个范围内，就不要搜下去，这样可以大大优化。

举个栗子

若N=4，T=16：

当枚举arr[1]=1时，剩余16-1*1=15，剩余的未放置的数为2，3，4，剩余的系数为1，3，3，这样最大值为4*3+3*3+2*1=23，最小值为4*1+3*3+2*3=19，都超过了15，所以第一个数不能选1。

Code4

1 #pragma GCC optimize(2)  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
           8 #include
           
             9 #include
            
              10 #include
             
               11 #define IL inline 12 using namespace std; 13 int tria[21][30]={ 14 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 15 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 16 0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 17 0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 18 0,1,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 19 0,1,4,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 20 0,1,5,10,10,5,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 21 0,1,6,15,20,15,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 22 0,1,7,21,35,35,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 23 0,1,8,28,56,70,56,28,8,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 24 0,1,9,36,84,126,126,84,36,9,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 25 0,1,10,45,120,210,252,210,120,45,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 26 0,1,11,55,165,330,462,462,330,165,55,11,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 27 0,1,12,66,220,495,792,924,792,495,220,66,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 28 0,1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 29 0,1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 30 0,1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0, 31 0,1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1,0,0,0,0,0,0,0,0,0,0,0,0, 32 0,1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1,0,0,0,0,0,0,0,0,0,0,0, 33 0,1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1,0,0,0,0,0,0,0,0,0,0, 34 0,1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1,0,0,0,0,0,0,0,0,0, 35 }; 36 int use[21]; 37 int tarr[50],ttria[30]; 38 int arr[50],t,n; 39 IL int read() 40 { 41 char ch;int x=0; 42 ch=getchar(); 43 while(ch<'0'||ch>'9') ch=getchar(); 44 while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 45 return x; 46 } 47 bool succ=0; 48 IL void dfs(int depth,int sum) 49 { 50 if(succ) return; 51 if(depth==n){ 52 if(sum==t) 53 { 54 succ=1; 55 for(int j=1;j<=n;j++){ 56 printf("%d",arr[j]); 57 if(j
              
               maxs+sum) return; 81 82 for(int i=1;i<=n;i++) 83 { 84 if(!use[i]) 85 { 86 if(depth>(n/2) && i
               
                t) continue; 88 use[i]=1; 89 arr[depth+1]=i; 90 dfs(depth+1,sum+i*tria[n][depth+1]); 91 arr[depth+1]=0; 92 use[i]=0; 93 } 94 } 95 } 96 int main() 97 { 98 // freopen("easy.in","r",stdin); 99 // freopen("easy.out","w",stdout);100 n=read();101 t=read();102 do{103 succ=0;104 dfs(0,0);105 n=read();106 t=read();107 }while(n!=0||t!=0);108 return 0;109 }