注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

孤独侠的博客

 
 
 

日志

 
 

杭电acm 2062  

2013-08-14 21:23:03|  分类: 杭电acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include <stdio.h>
int main()
{
    int n,i,j,x[21];
    __int64 m,f[30]={0},t;
    for(i=1;i<21;i++)
    {
        f[i]=(i-1)*f[i-1]+1;  //每组序列的个数(每组个数相等).
    }
    while(scanf("%d%I64d",&n,&m)!=EOF)
    {
        for(i=0;i<=n;i++)
        {
            x[i]=i;    //组数
        }
        while(n-- && m)
        {
            t=m/f[n+1]+(m%f[n+1]?1:0);  //找出第m个序列位于哪一组。
            printf("%d",x[t]);         //是第几组则第一个数字就是几。
            for(i=t;i<=n;x[i]=x[i+1],i++);   
            {
                m-=(t-1)*f[n+1]+1;
            }
            putchar(m?' ':'\n');
        }                                    
    }
    return 0;
}
----------------------------------------------------------------------------------
解析:

m得用__int64来接受
----------------------------------------------------------------------------------
考虑一个集合 An = { 1, 2, ..., n}。比如,A1={1},A3={1,2,3}。
不难发现,An可以按首数字分成n组,而每组里除了第一项,剩下的就是An-1的子集合了。
∴f(n) = n[f(n-1) + 1]
  f(1) = 1
我们拿测试数据3 10来做个示范,解释一下怎么求解。
因为n=3,所以开始数组里1、2、3三个数。
我们知道,n=2时,有4种排列,所以上面n=3可以分成三组,每组5个(加上空集)。
因此第10个在第二组里。所以第一个是2,把2输出。原来的数组里删除2,变成1、3两个数。然后10 - (2 - 1) * 5 = 5,即它在第2组的第5个。
减去首个空集合,5 - 1 = 4 ≠ 0,表示2后面还有数字。
因为A1 = 1是,所以再第2组里又可以分成两组,每组2个(加上空集)。
所以,4在第2组,剩下的数组中,第二个元素是3,所以输出3。再把数组里的3删除,剩下1一个数。
然后4 - (2 - 1) * 2 = 2,既它是第2组的第2个。
减去首个空集,2 - 1 = 1 ≠ 0,表示2后面还有数字。
按上面的方法继续下去,直到n = 0 或 后面为空集为止。
最后输出数组里的第1个元素,就得到2 3 1,就是解了。

从上面的计算可以看出来,本题目的关键是先求的An中每一组的个数g(n)
不难得出:g(n) = f(n) / n
∵f(n) = n[f(n-1) + 1]
∴g(n) = n[f(n-1) + 1] / n = f(n-1) + 1
∵f(n-1) = (n-1) * g(n-1)
∴g(n) = (n-1) * g(n-1) + 1

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017