- 浏览: 35637 次
- 性别:
- 来自: 湖南
最新评论
-
kulinglei:
提烟而过 写道问下楼主:你是拿了别人的注册号在这里害别人,还是 ...
折半搜索 -
jy00105276:
没看代码,看描述难道是2分法?
是的话不一定是a[i-1] ...
折半搜索 -
提烟而过:
问下楼主:你是拿了别人的注册号在这里害别人,还是没事在这里装- ...
折半搜索 -
zqynux:
fffvvvzz 写道11-15
是
11 12 13 14 ...
折半搜索 -
zqynux:
额,, 就是一个NOIP题目的答案..
vijos 谁拿了最多奖学金
Longest Prefix
IOI'96
The structure of some biological objects is represented by the sequence of their constituents denoted by uppercase letters. Biologists are interested in decomposing a long sequence into shorter ones called primitives.
We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives
{A, AB, BA, CA, BBC}
The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives.
PROGRAM NAME: prefix
INPUT FORMAT
First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of upper-case characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (`.'). No primitive appears twice in the list. Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceed 76 letters in length. The "newlines" are not part of the string S.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
A single line containing an integer that is the length of the longest prefix that can be composed from the set P.
SAMPLE OUTPUT (file prefix.out)
11
描述
在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的(称之为元素的)序列很感兴趣。
如果一个集合 P 中的元素可以通过串联(允许重复;串联,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子,序列 ABABACABAAB 可以分解为下面集合中的元素:
{A, AB, BA, CA, BBC}
序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序,输入一个元素集合以及一个大写字母序列,计算这个序列中(由集合元素组成的)最长的前缀的长度。
格式
PROGRAM NAME: prefix
INPUT FORMAT
输入数据的开头包括 1..200 个元素(长度为 1..10 )组成的集合,用连续的以空格分开的字符串表示。字母全部是大写,数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ,长度为 1..200,000 ,用一行或者多行的字符串来表示,每行不超过 76 个字符。换行符并不是序列 S 的一部分。
OUTPUT FORMAT
只有一行,输出一个整数,表示 S 能够分解成 P 中元素的最长前缀的长度。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
SAMPLE OUTPUT (file prefix.out)
11
============================ 华丽的分割线 ============================
前两天写出来了,, 忘记发日志了`
感觉用的这个方法不像是DP(对于DP我还没有特别清楚的概念..),, 其中pre变量存储所有的匹配串(即短的那个字符串.), str是住串(长的那个.), 接下来最关键的是lenth这个变量,, (感觉名字没取好), 这个主串假设分为分为a1 a2 a3 ... an, lenth[i]如果是1的话代表在a1 a2 a3 .. ai 都是能够在匹配串匹配..
说了一些云里雾里的话吧,, 废话不多,, 代码上:
IOI'96
The structure of some biological objects is represented by the sequence of their constituents denoted by uppercase letters. Biologists are interested in decomposing a long sequence into shorter ones called primitives.
We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives
{A, AB, BA, CA, BBC}
The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives.
PROGRAM NAME: prefix
INPUT FORMAT
First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of upper-case characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (`.'). No primitive appears twice in the list. Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceed 76 letters in length. The "newlines" are not part of the string S.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
A single line containing an integer that is the length of the longest prefix that can be composed from the set P.
SAMPLE OUTPUT (file prefix.out)
11
描述
在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的(称之为元素的)序列很感兴趣。
如果一个集合 P 中的元素可以通过串联(允许重复;串联,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子,序列 ABABACABAAB 可以分解为下面集合中的元素:
{A, AB, BA, CA, BBC}
序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序,输入一个元素集合以及一个大写字母序列,计算这个序列中(由集合元素组成的)最长的前缀的长度。
格式
PROGRAM NAME: prefix
INPUT FORMAT
输入数据的开头包括 1..200 个元素(长度为 1..10 )组成的集合,用连续的以空格分开的字符串表示。字母全部是大写,数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ,长度为 1..200,000 ,用一行或者多行的字符串来表示,每行不超过 76 个字符。换行符并不是序列 S 的一部分。
OUTPUT FORMAT
只有一行,输出一个整数,表示 S 能够分解成 P 中元素的最长前缀的长度。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
SAMPLE OUTPUT (file prefix.out)
11
============================ 华丽的分割线 ============================
前两天写出来了,, 忘记发日志了`
感觉用的这个方法不像是DP(对于DP我还没有特别清楚的概念..),, 其中pre变量存储所有的匹配串(即短的那个字符串.), str是住串(长的那个.), 接下来最关键的是lenth这个变量,, (感觉名字没取好), 这个主串假设分为分为a1 a2 a3 ... an, lenth[i]如果是1的话代表在a1 a2 a3 .. ai 都是能够在匹配串匹配..
说了一些云里雾里的话吧,, 废话不多,, 代码上:
/* LANG: C ID: zqy11001 PROG: prefix */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define getstr(s) scanf("%s", s) char pre[401][11]; int m; char lenth[200001]; char str[200000]; int n; int main(void) { int i, j, k; int best = 0; freopen("prefix.in", "r", stdin); freopen("prefix.out", "w", stdout); while(1){ getstr(pre[m]); if(pre[m][0] == '.'){ break; } m++; } while(getstr(str + n) == 1){ n += strlen(str + n); } lenth[0] = 1; best = 0; for(i = 0; i < n; i++){ if(lenth[i]){ best = i; for(j = 0; j < m; j++){ for(k = 0; ((i + k) < n) && (pre[j][k] != '\0') && (pre[j][k] == str[i + k]); k++){ ; } if(pre[j][k] == '\0'){ lenth[i + k] = 1; } } } } if (lenth[n]) best = n; printf("%d\n", best); return 0; }
发表评论
-
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 1265/* LANG: C ID: zqynux11 PROG ... -
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 807解释什么的就算了吧,, /* LANG: C ID: ... -
重做 USACO 1.1 贪婪的送礼者
2010-03-31 18:58 1208这题的话, 我用的是个结构体, 记录各个人.. 我错了的地 ... -
重做 USACO 1.1 你的飞碟在这儿
2010-03-31 18:56 850不解释了.. /* LANG: C ID: zqynu ... -
USACO 3.1 Shaping Regions 形成的区域
2010-03-30 20:01 1496这题二话不说, 用map[i][j]表示坐标为i, j的点 ... -
USACO 3.1 Humble Numbers 丑数
2010-03-28 15:31 1441从这一题开始,, 以后题目我就不贴上来了... 自己去看吧 ... -
USACO 3.1 Score Inflation 总分
2010-03-27 20:19 802Score Inflation The more point ... -
USA 3.1 Agri-Net 最短网络
2010-03-27 20:14 842Agri-Net Russ Cox Farmer John ... -
USACO 2.4 Fractions to Decimals 分数化小数
2010-03-27 15:47 1247Fractions to Decimals Write a ... -
USACO 2.4 Bessie Come Home 回家
2010-03-27 13:01 994Bessie Come Home Kolstad & ... -
USACO 2.4 Cow Tours 牛的旅行
2010-03-27 11:57 1079Cow Tours Farmer John has a nu ... -
USACO 2.4 Overfencing 穿越栅栏
2010-03-25 18:18 930USACO 2.4 Overfencing 穿越栅栏 Over ... -
USACO 2.4 The Tamworth Two 两只塔姆沃斯牛
2010-03-23 22:05 1168The Tamworth Two BIO '98 - Rich ... -
USACO 2.3 Controlling Companies 控制公司
2010-03-23 22:00 1417Controlling Companies Some com ... -
USACO 1.1 Broken Necklace 破碎的项链
2010-03-22 18:04 2074Broken Necklace You have a neck ... -
USACO 2.3 Money Systems 货币系统
2010-03-22 13:31 949Money Systems The cows have no ... -
USACO 2.3 Cow Pedigrees 奶牛家谱
2010-03-21 15:02 1408Farmer John is considering purc ... -
USACO 2.3 Zero Sum 零的算式和
2010-03-20 14:30 1757Zero Sum Consider the sequence ... -
vijos 谁拿了最多奖学金
2010-03-17 12:25 1064描述 Description 某校的惯例是在每 ... -
USACO 2.2 Subset Sums集合
2010-03-16 12:18 1422USACO 2.2 Subset Sums集合 For ...
相关推荐
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco历年测试数据
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO题集及答案
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
USACO历年比赛测试数据:2003年 方便大家测试
USACO全部译题 USACO Training Program Gateway
usaco traning的全部数据 才要3分
内含USACO全部测试数据,绝对全
USACO所有题目的题解 NOCOW整理版
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO历年比赛测试数据:2006年方便大家测试
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!
含2001~2017全部比赛赛题测试数据 2001~2007 数据√ 题面× 标程题解× 2008~2010 数据√ 题面√ 标程题解× 2011~2017 数据√ 题面√ 标程题解√ 其中除2008~2010外其他年份均按照年度、月度、金银铜白金组别整理...
此文件包含了USACO上全部测试数据,方便您离线使用