Section 2.2

 

这一节以模拟题为主,比较恶心。一道动态规划,一道枚举。

 

Preface Numbering

问题描述

      先是介绍罗马数字书写(略),给出一个数字,求1到这个数字之间所有数字的罗马表示中共出现几个IVXLCDM

分析

         最初的思路是一个个地模拟:观察后可以发现,46可以表示为XLVI,以数组s[1…7]表示I…M,则472111000,而41100000721000000,总结可知s[n][1]=s[n%10][1];s[n][2]=s[n%10][2];(注意n%10==9的话,s[n][3]+=s[9][3])。2<=i<=7时, s[n][i]=s[n/10][i-2]

         其实完全可以分段统计,比如234,个位出现了230~910~4,十位出现了200~910~3,百位出现了12

 

Subset Sums

问题描述

       对于从1N (1 <= N <= 39) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。给出N,你的程序应该输出划分方案总数,如果不存在这样的划分方案,则输出0

分析

       看完题目最先想到的是深搜,枚举所有可能,当其和等于总和一半的时候则记录。但提交后发现,当N31,程序算了78秒才出答案。看来深搜是不行了,在网上看了别人的解法才知道要动态规划。其实应该算递推,令ans[i][j]表示前i个数里面和为j的方案数,则ans[i][j]可以等于前i-1个数字里面和为j的方案数(即不含数字j的方案),加上前i-1个数字里和为j-i的方案数(即最终含有数字j,ans[N][N*(N+1)/4]即为最终解。状态转移方程为:

                                               ans[i][j]=ans[i-1][j]+ans[i-1][j-i];

 

Runaround Numbers

问题描述:

         寻找循环数----从最右的数字出发,走数字对应的步数,然后从所停的数字继续出发,再走刚才所停数字对应步数,直到回到出发点。

分析:

       循环数有点类似约瑟夫环,直接模拟即可,从题目所给数字开始一个个枚举。注意:数字不含0;回到起始点前,每一位都必须停留过一次且必须只停一次。

 

Party Lamps

问题描述:

      有四个按钮控制N盏灯,10<=N<=100

按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。

按钮2:当按下此按钮,将改变所有奇数号的灯。

按钮3:当按下此按钮,将改变所有偶数号的灯。

按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7...

一个计时器记录按下按钮的次数C,现给出C,和某些灯的最终开关状态,求所有的灯最终可能的所有状态。

分析

         这题很久以前就见过了,觉得比较麻烦,就一直没动,现在不动不行了。在纸上分析后会发现,灯的状态是六个一组循环出现的,故只需得出前六个灯的状态,后面的灯的状态就可知了。每盏灯有开关两种状态,四个循环枚举即可。在网上看了一下别人的解法,用二进制表示状态是比较方便的,于是我决定第一次尝试位运算解题。

         由于异或运算符的特点:01异或1以后取反,异或0不变。第一种操作可以用n^(111111)2实现,第二种操作用n^(101010)2实现,第三种用n^(10101)2实现,第四种用n^(100100)2实现。

         对于状态的读取,我想不出什么好办法。只好这样了:

int ReadOn()
{   bool tem[6];
    memset(tem,
false,sizeof(tem));
    
int i,c;
    
while(fin>>c&&c!=-1)
        tem[(c
-1)%6]=true;//此处灯亮,则令其为1
    c=0;
    
for(i=0;i<6;i++)
    
{   c=c<<1;        
        
if(tem[i])
            c
+=1;
    }

    
return c;//c的二进制表示就是题目给出的部分灯亮的状态
}

例如,测试数据给出2号灯亮,则最终状态里2位上的必为1,表示为:010000 。读入不亮的灯的函数做相应修改即可。

判断当前枚举得到的状态是否满足要求可用以下方法:

if(a+b+c+d<=times)
  
if((state|Off)==Off)
  
{   if((state&On)==On)//Off表示测试数据给出的不亮的灯 On表示亮的灯(即限制条件)
     ans[state]=true;
     
if(state==0&&On==0
     ans[state]
=true;
  }

第五行如果state0即都不亮,而On也为0,本来应该是符合的,但由于0&0=1=0.所以在后面补上。

posted on 2010-05-26 13:02 ZAKIR 阅读(228) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜