?
hdu 2062 Subset sequence
hdu 2062傳送門： http://acm.hdu.edu.cn/showproblem.php?pid=2062
?
| ? | 考慮一個集合 An = { 1, 2, ..., n}。比如，A1={1}，A3={1,2,3}。我們稱一個非空子集元素的排列為一個子集序列。對所有的子序列按字典順序排序。你的任務就是給出第m個子序列。 |
|---|
?
?
| ? |
首先我們來看看An一共有多少個子集。
n=1時,只有{1}一個子集合也許你發現規律了。An子集合的個數為: C 1 n ·A 1 1 + C 2 n ·A 2 2 + ... + C n n ·A n n 這個公式是對的。但我們換個角度看。 n=3時，有不難發現，An可以按首數字分成n組，而每組里除了第一項，剩下的就是An-1的子集合了。 ∴f(n) = n[f(n-1) + 1] f(1) = 1
我們拿測試數據3 10來做個示范，解釋一下怎么求解。
從上面的計算可以看出來，本題目的關鍵是先求的An中每一組的個數g(n)
|
|---|
?
?
代碼如下：
#include <stdio.h>
int main()
{
? ? int i,n,t;//n：一共多少元素<=20。t：所求子集位于分組后的第幾組
? ? __int64 m;//位于第幾個子集
? ? __int64 c[21]={0};//后面將子集分組后平均每組個數，如:c[2]表示n=2時的分組每組中子集數
? ? int s[21];//后面將子集按字典序分組后每組的初始首元素,組數<=20
? ? for (i=1;i<21;i++)
? ? ? ? c[i]=c[i-1]*(i-1)+1;//推導出來的c[n]=(n-1)*c[n-1]+1
? ? while (scanf("%d%I64d",&n,&m)!=EOF)
? ? {
? ? ? ? for(i=0;i<21;i++)
? ? ? ? ? ? s[i]=i;//每循環一次就重新歸位每組首元素
? ? ? ? while (n>0&&m>0)
? ? ? ? {
? ? ? ? ? ? t=m/c[n]+(m%c[n]>0?1:0);
? ? ? ? ? ? if(t>0)//得到第m個子集在分組后的第t組,若t>0
? ? ? ? ? ? {
? ? ? ? ? ? ? ? printf("%d",s[t]);
? ? ? ? ? ? ? ? for(i=t;i<=n;i++)
? ? ? ? ? ? ? ? ? ? s[i]=s[i+1];//或s[i]+=1,我們發現:第n組中，第2個元素在第n個時變為它的下一個數
? ? ? ? ? ? ? ? m-=((t-1)*c[n]+1);//減去(t-1組總子集數+1）,m變為表示在剩余子集中位于第幾個
? ? ? ? ? ? ? ? putchar(m==0?'\n':' ');
? ? ? ? ? ? }
? ? ? ? ? ? n--;//依次遞減,直到執行上面的if代碼或退出
? ? ? ? }
? ? }
? ? return 0;
}
?
具體操作步驟如下：
程序必需因素：
? ??1、每組子集的個數c[n];
? ??2、每組子集的首元素;
? ? 3、所求子集位于當前分組后的第幾組中t
? ? 4、所求子集位于該組的第幾個
主要遞歸步驟：
1、求出所在組t
2、輸出所在組t的首元素s[t](同一組首元素相同)
3、將該子集的下一個元素到最后一個的值+1,注意這個規律：在第i組，首元素為i，刪除首元素后，在第i個子集后首元素均變大+1.
程序步驟實例解說：
?
n=3，m=10時，有
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{1, 3, 2}
{2}
{2, 1}
{2, 1, 3}
{2, 3}
{2, 3, 1}
{3}
{3, 1}
{3, 1, 2}
{3, 2}
{3, 2, 1}
1。求得t=2
先輸出第2組首元素2，再去掉前面不需要的分組，和首元素,剩下唯一一組子集：
因此此時m-=((t-1)*c[n]+1)=4
//{}
{1}
{1, 3}
{3}
{3, 1}
此時的s[t~~n]均變大+1
2。然后再分成兩組， t=m/c[n]+(m%c[n]>0?1:0)求得當前在第t=2組
輸出第2組首元素3，再去掉前面不需要的分組，和首元素,剩下唯一一組子集
因此此時m-=((t-1)*c[n]+1)=1
//{}
{1}
3。然后剩最后一組， t=m/c[n]+(m%c[n]>0?1:0)求得當前在第t=1組
輸出第1組首元素1，和首元素,剩下唯一一組子集
{}//空集
因此此時m-=((t-1)*c[n]+1)=0
最后退出。
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
