【題目描述】

小A有n個球，編號分別為1到n，小A每次都會從n個球中取出若干個球，至少取一個，至多取n個，每次取完再放回去，需要滿足以下兩個條件。

（1）每次取出的球的個數兩兩不同。

（2）每次取出的球的集合兩兩不包含。

包含是指，對于兩次取球，對于取的數目少的那次取球的所有球都出現在取的數目多的那次取球中，例如｛1，2｝和｛1，2，4｝，｛1，2｝和｛2，3｝則不算作包含。

而小A現在突然想知道他最多能進行多少次這樣的操作，并希望你能給出具體的取球方案。

【輸入樣例】

一個整數n。

【輸出樣例】

第一行一個數k，表示能進行的最多次數。

接下來k行，每行第一個整數p，表示這次取的球數，接下來p個數表示這次取的球的編號，編號只需要不同，不需要按照順序輸出，本題設有spj。

對于每個測試點，每組數據第一行正確可以獲得20%的分，如果第一行和方案均正確獲得100%的分。

【樣例輸入】

4

【樣例輸出】

2

1 1

2 2 3

【備注】

對于30%的數據，n<=7。

對于50%的數據，n<=20。

對于70%的數據，n<=100。

對于100%的數據，4<=n<=1000。

?

【題目分析】

首先對于30%甚至50%的數據，打表是完全沒問題的，那么對于可打表的數據，我們可以發現一個規律：最多可以取的次數為n-2，并且恒成立，下面給出證明：

（1）：n為奇數

n最小為5，此時最大次數為3，可為{1}，{2,3}，{2,4,5}，對于7，我們可以在每一組后添1個7，因為原組合不互相包含，那么加上一個7后仍不互相包含，然后將6作為單獨一組，以此類推，所有為奇數的n均可以用這種方式構造出。

（2）：n為偶數

同（1），n最小為4，最大次數為2，{1}，{2，3}，對于6可以在每一組后添1個6，因為原組合不互相包含，那么加上一個6后仍不互相包含，然后將5作為單獨一組，以此類推，所有為偶數的n均可以用這種方式構造出。證畢。

然后這道題就比較簡單了，代碼見下：

【代碼~】

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;int n,num;
int f[MAXN<<1][MAXN];int main()
{scanf("%d",&n);printf("%d\n",n-2);f[num=MAXN][0]=f[MAXN][1]=1;if(n&1){for(int i=5;i<=n;i+=2){num--;f[num][f[num][0]=1]=i-1;for(int j=num+1;j<=num+i-4;++j)f[j][++f[j][0]]=i;for(int j=1;j<=i-2;++j)f[num+i-3][j]=j;f[num+i-3][0]=i-2;}}else{f[num+1][0]=2;f[num+1][1]=2,f[num+1][2]=3;for(int i=6;i<=n;i+=2){num--;f[num][f[num][0]=1]=i-1;for(int j=num+1;j<=num+i-4;j++) f[j][++f[j][0]]=i;for(int j=1;j<=i-2;j++) f[num+i-3][j]=j;f[num+i-3][0]=i-2;}}for(int i=num;i<num+n-2;++i){printf("%d",f[i][0]);for(int j=1;j<=f[i][0];++j)putchar(' '),printf("%d",f[i][j]);cout<<endl;}return 0;
}

?

轉載于:https://www.cnblogs.com/Ishtar/p/10010850.html

總結

以上是生活随笔為你收集整理的NOIP模拟 数球（思维题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。