数球【思维题】

数球【思维题】

题目大意：给出n个球，每次从中拿出若干个球，要求每次拿的个数都不一样，且每次拿的求之间不能相互包含，求最多能拿多少次，并输出每次拿的球数和方案

Sample input

5

Sample output

3
1 1
2 2 3
3 2 4 5

分析

做这道题时一开始没什么思路，于是乎开始打表。。。。

打着打着你就会发现规律，最多拿的次数 = n-2

我们算出n=4和5时的答案，可以递推出后面所有的答案

方法：

1. n=4时的方案：

   1

   2 3

   当n为偶数时，比如n=6，那么我们把前面方案的后面都加上一个6，仍合法：

   1 6

   2 3 6

   将5单独一组，再加上 1 - n-2：

   5

   1 6

   2 3 6

   1 2 3 4

   得到6的方案，同理可以递推出所有偶数时的方案

2. n=5时的方案：

   1

   2 3

   2 4 5

   当n为奇数时，如n=7，那么：

   1 7

   2 3 7

   2 4 5 7

   和上一种偶数的方案差不多：

   6

   1 7

   2 3 7

   2 4 5 7

   1 2 3 4 5

   同理递推出所有奇数时的方案

   代码

   #include<cstdio>
   #include<cstring>
   #include<algorithm>
   using namespace std;
   const int maxn = 10001;
   int n, f[maxn][maxn], len[maxn], cnt;//f[i][j]是第i行的方案
   signed main(){
       freopen("course.in", "r", stdin);
       freopen("course.out", "w", stdout);
       f[1][1] = 1; len[1] = 1;
       f[2][1] = 2; f[2][2] = 3; len[2] = 2;
       f[3][1] = 2; f[3][2] = 4; f[3][3] = 5; len[3] = 3;//手算出4，5的答案
       scanf("%d", &n);
       if(n & 1){//n为奇数
           cnt = 3;//方案数
           for(int i=7; i<=n; i+=2){//递推
               for(int j=1; j<=cnt; j++){//在每行后加上i
                   f[j][++len[j]] = i;
               }
               f[++cnt][1] = i-1;//只拿出一个球的方案
               len[cnt++] = 1;
               for(int k=1; k<=i-2; k++) f[cnt][k] = k;//1 - n-2的方案 
               len[cnt] = i-2;
           }
       }else{//偶数时，和上面差不多
           cnt = 2;
           for(int i=6; i<=n; i+=2){
               for(int j=1; j<=cnt; j++){
                   f[j][++len[j]] = i;
               }
               f[++cnt][1] = i-1;
               len[cnt++] = 1;
               for(int k=1; k<=i-2; k++) f[cnt][k] = k; 
               len[cnt] = i-2;
           }
       }
       printf("%d
   ", n-2);
       for(int i=1; i<=cnt; i++){//输出
           printf("%d ", len[i]);
           for(int j=1; j<=len[i]; j++){
               printf("%d ", f[i][j]);
           }
           printf("
   ");
       }
       return 0;
   }
   

   （不写注释的题解简直恶臭）