- 浏览: 37676 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
转载请注明出处
摘要:模拟, 环的处理
一. 题目翻译
1. 描述:
你有一条由N个红色的,白色的,或蓝色的珠子组成的项链(3<=N<=350),珠子是随意安排的。 这里是 n=29 的二个例子:
第一和第二个珠子在图片中已经被作记号。图片 A 中的项链可以用下面的字符串表示:brbrrrbbbrrrrrbrrbbrbbbbrrrrb
假如你要在一些点打破项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子,在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子。
例如,在图片 A 中的项链中,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链可以收集到8个珠子。
在一些项链中还包括白色的珠子(如图片B) 所示。当收集珠子的时候,一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。
表现含有白珠项链的字符串将会包括三个符号 r , b 和 w 。写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。
2. 格式:
PROGRAM NAME:beads
INPUT FORMAT:
第 1 行: N, 珠子的数目
第 2 行: 一串长度为N的字符串, 每个字符是 r , b 或 w。
OUTPUT FORMAT:
单独的一行包含从被供应的项
SAMPLE INPUT:
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
SAMPLE OUTPUT:
11
二. 题解
1. 题意理解(将问题分析清楚,大致用什么思路):
这道题目的整体还是比较简单的,思路是从分割点分别向左、向右按题意搜索颜色相同的珠子,然后相加求最大即可。
唯一的难点在于如何处理这个项链这个环?下面给出两种解法:
1. 将项链用一个链表表示,每一个珠子是一个结点。每次遍历到新的剪开位置时,只需将当前链表的头结点移动到尾结点即可。这样每一次还是分别从链表的头以及尾开始遍历。
2. 用三条项链组成一个串,这样只需遍历中间那条项链,然后分别从剪开点向左与向右遍历即可。
2. 具体实现(具体实现过程中出现的问题):
这道题目我是用第一种方法实现的,代码有些混乱,就不贴了。
三. 代码
/* ID: fightin1 LANG: JAVA TASK: beads */ import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; import java.util.LinkedList; public class beads { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub try { BufferedReader br = new BufferedReader(new FileReader("beads.in")); PrintWriter pw = new PrintWriter (new FileWriter("beads.out")); int length = Integer.parseInt(br.readLine()); String temp = br.readLine(); LinkedList<Character> necklace = new LinkedList<Character>(); for (int i=0;i<length;i++) { necklace.add(temp.charAt(i)); } int max = 0; for (int i=0;i<length;i++) { char remove = necklace.removeFirst(); char first = necklace.getFirst(); int position = 0; necklace.addLast(remove); int result = 0; boolean allW = false; if (necklace.getFirst()=='w'){ int end1 = find(necklace,0,length,0); result = end1 + 1; if (end1<necklace.size()-1){ int end2 = find (necklace,end1+1,length,0); first = necklace.get(end2); position = end2; result = result + end2 - end1; }else { allW = true; } } else { int end = find(necklace,0,length,0); position = end ; result = result + end + 1; } if (!allW){ if (necklace.getLast()=='w') { int end1 = find(necklace, length-1,position,1); int end2 = find(necklace,end1-1,position,1); if (necklace.get(end2)==first){ result = result ; }else { result = result + length - end1; result = result + end1 - end2 ; } }else { if (necklace.getLast()==first){ result = result; }else { int end = find(necklace,length-1,position,1); result = result + length - end ; } } } if (result >=max){ max = result; } } pw.println(max); pw.close(); br.close(); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } public static int find(LinkedList<Character> necklace,int startPoint ,int endPoint,int direction){ if (direction ==0 ){ int i=startPoint+1; for (;i<=endPoint-1;i++){ if (necklace.get(i)!=necklace.get(startPoint)&&necklace.get(i)!='w'){ break; } } return i-1; } else { int i=startPoint-1; for (;i>=endPoint+1;i--){ if (necklace.get(i)!=necklace.get(startPoint)&&necklace.get(i)!='w'){ break; } } return i+1; } } }
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 806原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 699原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 908原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 712原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 903原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 854原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 959原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 903原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 716原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1300原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 868原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 744原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1008原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1207原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 658原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 694原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 891原创文章转载请注明出处 摘要:模拟 , 数学分析 ...
相关推荐
[USACO 1.1.4]破碎的项链.cpp
USACO题目Broken Necklace (beads)及代码解析
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 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作