月度归档:2017年11月

BZOJ 2852: 强大的区间(辗转相除法)

Description

curimit很喜欢区间,最近发现了一种很强大的区间。
curimit发现有的区间虽小,比如 (1.99998, 2.000001),但是其中却包含了一个整数2。
但是有的区间较大,比如(1.0001, 1.99998),但是其中却一个整数都没有。
他觉得包含整数的区间很强大,并且提出了一个问题:
我们先给出两个非负实数a,b我们要求一个最小的正整数k ,使得区间(a*k, b*k)是一个包含至少一个整数的区间。
举个例子来说吧,比如我们输入a=1.2 b=1.3 ,那么:
当k=1时, 区间为(1.2 , 1.3) 其中没有整数;
当k=2时, 区间为(2.4 , 2.6) 其中没有整数;
当k=3时, 区间为(3.6 , 3.9) 其中没有整数;
当k=4时, 区间为(4.8 , 5.2) 其中包含了一个整数5。
所以使得区间(1.2*k, 1.3*k)包含一个整数的最小正整数k是4。

Input

两个非负实数a,b。

Output

最小的k的值。

Sample Input

1.2 1.3

Sample Output

4

Hint

HINT

a,b整数部分不超过2^31-1,a,b小数部分位数不超过300位。

发现[a,b]的答案k等价于[a-1,b-1]的答案k,那么假设\(a \leq b\),那么一定可以让\(a <1 \),这时候如果\(b > 1\) 那么答案就是1.否则我们把条件转换一下:\(a*k \leq x \leq b*k\)等价于\(x/b \leq k \leq x/a\),把问题转换成了一个子问题。这样就可以递归下去做了,最后再一步步乘回来,需要高精度小数乘法。

BZOJ 1030: [JSOI2007]文本生成器(AC自动机+dp)

Description

  JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,
他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文
章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,
那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的
标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6
生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?

Input

  输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固 定长度M;以下N行,每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100,并且只可能包 含英文大写字母A..Z Output   一个整数,表示可能的文章总数。只需要知道结果模10007的值。 Sample Input 2 2 A B Sample Output 100 晚上本来想把昨天训练的15长春补一补,结果发现自己读的两个题有点太难了。。。于是就颓了颓,然后做了这个题。 非常像1009,但是有多个串,所以我们可以用AC自动机来解决。 考虑反面有多少个串不可以由单词组成,dp[i][j]表示第i个字符现在匹配到了第j个点,那么就可以在AC自动机上dp了。一种是跳fail,一种是正常转移。但是如果枚举到的j已经是一个单词了,那么是不可以转移的。这些地方注意到了,但是我们注意到在构建fail指针的时候,如果一个节点的fail是一个单词,那么这个节点也是不可以转移的。因为他有个后缀是单词。。。

BZOJ 1212: [HNOI2004]L语言(AC自动机+dp)

Description

标点符号的出现晚于文字的出现,所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。 一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。 我们称一段文章T在某个字典D下是可以被理解的,是指如果文章T可以被分成若干部分,且每一个部分都是字典D中的单词。 例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’},则文章‘whatisyourname’是在字典D下可以被理解的 因为它可以分成4个单词:‘what’, ‘is’, ‘your’, ‘name’,且每个单词都属于字典D,而文章‘whatisyouname’ 在字典D下不能被理解,但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’,也可以在字典D下被理解 而且是在字典D下能够被理解的最长的前缀。 给定一个字典D,你的程序需要判断若干段文章在字典D下是否能够被理解。 并给出其在字典D下能够被理解的最长前缀的位置。

Input

输入文件第一行是两个正整数n和m,表示字典D中有n个单词,且有m段文章需要被处理。 之后的n行每行描述一个单词,再之后的m行每行描述一段文章。 其中1<=n, m<=20,每个单词长度不超过10,每段文章长度不超过1M。 Output 对于输入的每一段文章,你需要输出这段文章在字典D可以被理解的最长前缀的位置。 Sample Input 4 3 is name what your whatisyourname whatisyouname whaisyourname Sample Output 14 6 0 整段文章’whatisyourname’都能被理解 前缀’whatis’能够被理解 没有任何前缀能够被理解 貌似每个单词长度都非常短,所以其实可以暴力在Trie上dp的。但其实模板串很长啊QAQ。。。 当我们走到第i个字符,如果字典里面有一个满足当前条件的后缀,那么他就可以从dp[i-len]转移过来。建立出来AC自动机,暴力跳fail指针,因为fail指针是满足条件的最长的后缀,所以肯定不会漏啦。 一周沉迷复习没写代码,居然可以1A,真是感人。。