- 浏览: 37409 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
USACO - 3.2.2 - Stringsobits
原创文章转载请注明出处
摘要:动态规划 , 三星题目
一. 题目翻译
1. 描述:
考虑排好序的N(N<=31)位二进制数。
你会发现,这很有趣。因为他们是排列好的,而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。
你的任务是输出第i(1<=i<=长度为N的二进制数的个数)小的(注:题目这里表述不清,实际是,从最小的往大的数,数到第i个符合条件的,这个意思),长度为N,且1的位数的个数小于等于L的那个二进制数。
(例:100101中,N=6,含有位数为1的个数为3)。
2. 格式:
INPUT FORMAT:
(file kimbits.in)
共一行,用空格分开的三个整数N,L,i。
OUTPUT FORMAT:
(file kimbits.out)
共一行,输出满足条件的第i小的二进制数。.
SAMPLE INPUT:
5 3 19
SAMPLE OUTPUT:
10011
二. 题解
1. 题意理解(将问题分析清楚,大致用什么思路):
分析题目的意思是要输出一个二进制数,这个二进制数是要求在长度为N,且1的位数个数小于等于L的二进制数中第i大数。那么首先我们要先确定到底符合要求的长度为N,且1的位数小于等于L的二进制数有多少个?解决这个问题,我们可以使用动态规划。
dp[k][j]表示长度为k的二进制数中,1的个数为j的二进制数的个数。状态转移方程,dp[k][j] = dp[k-1][j] + dp[k-1][j](第k位取0和取1两种情况)。之后循环累加dp[k][j](j=1..L),使得dp[k][j]表示长度为k的二进制数,1的个数小于等于j的二进制数的个数。
有了dp[k][j]后构造所求的字符串呢 ?
设所求串为sb,sb中的第n位如果取0,那么dp[n-1][l] >=i(l表示字符串包含的1的个数,i表示第几个取值) ;如果sb中的第n位取1,那么dp[n-1][l]<i。(这里思考下为什么?dp[n][l] = dp[n-1][l] + dp[n-1][l-1],dp[n-1][l]表示当前位为0的情况)。
2. 具体实现(具体实现过程中出现的问题):
这里详细描述下有了dp[k][j]后构造字符串sb的过程。
// i表示所求的字符串为排序中的第i个, n表示要生成的字符串的长度 , L表示要生成字符串当中1的个数
if (i<=dp[n-1][L])
sb.append(0);
继续递归(第i位,n-1 ,L);// 第n位必须是“0”,继续递归寻找。字符串长度减1。字符串中1的个数不变
else
sb.append(1);
继续递归(i-dp[n-1][L] ,n-1 , L-1); //第n位是“1”,所以减去第k位是0的字符串的个数。字符串的长度减1。字符串中1的个数也减1.
3. 启示:
这道题目是非常有意思并且值得思考的,题目不可以直接由动态规划求出答案,而是对动态规划后的结果进一步利用,最终产生答案,很有意思。
三. 代码
/* ID:fightin1 LANG:JAVA TASK:kimbits */ package session_3_2_2; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; import java.util.Scanner; public class kimbits{ public static void main(String[] args) throws Exception { // Scanner in = new Scanner(new BufferedReader(new FileReader( // "kimbits.in"))); // PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter( // "kimbits.out"))); Scanner in = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int N = in.nextInt(); int L = in.nextInt(); long i = in.nextLong(); long[][] dp = new long[N+1][L+1]; dp[0][0] = 1; for (int k=1;k<=N;k++){ for (int j=0;j<=L;j++){ if (j-1>=0) dp[k][j] = dp[k-1][j] + dp[k-1][j-1]; else dp[k][j] = dp[k-1][j]; } } for (int k=0;k<=N;k++){ for (int j=1;j<=L;j++){ dp[k][j] += dp[k][j-1]; } } StringBuilder sb = new StringBuilder(); execute(i, dp, N, L, sb); pw.println(sb); pw.close(); } public static void execute(long i,long[][] dp, int n ,int l ,StringBuilder sb){ if (n>=1){ if (i<=dp[n-1][l]){ sb.append(0); execute(i, dp, n-1, l, sb); } else { sb.append(1); execute(i-dp[n-1][l], dp, n-1, l-1, sb); } } } }
发表评论
-
USACO - 3.2.1 - Factorials
2012-08-23 16:01 693原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1030原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 900原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 706原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 897原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 849原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 953原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 883原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 992原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 712原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1293原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 860原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 738原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1004原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1036原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1195原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 653原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 688原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 885原创文章转载请注明出处 摘要:模拟 , 数学分析 ... -
USACO - 2.1.5 - Hamming Codes
2012-08-18 19:22 774原创文章转载请注明出处 摘要:枚举、暴力 ...
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始