• PKU2019数据结构与算法实习作业 11~21

    PKU2019数据结构与算法实习作业 11~21

    题目来源:http://dapractise.openjudge.cn/2019hwall/多模式串字符串匹配模板题AC自动机模板题[crayon-65f93dd609949512689463/]POJ3987ComputerVirusonPlanetPandora[crayon-65f93dd609957037032642/]躲不开的病毒找自动机上的环[crayon-65f93dd60995f321808036/]POJ3691DNArepairDP,考虑前i个字符且停留在trie树上编号为j的节点时,字符串所修改的最小次数[crayon-65f93dd609966784151118/]POJ3450Corpor...

  • 2017 训练赛 1 by hzwer

    2017 训练赛 1 by hzwer

    「poj1054」TheTroublesomeFrog(恼人的青蛙)「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog(恼人的青蛙)首先O(n^3)的算法是显然的,即枚举两个点,check一下这条路径上所有点,由于这道题时限放的比较宽,实际上图可以直接用二维的bool数组存下来网络上的题解大多...

  • 2016 ACM / ICPC Asia Regional Qingdao Online

    2016 ACM / ICPC Asia Regional Qingdao Online

    大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的,其质因数个数不会超过30个dfs出所有数字,二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...

  • UOJ Easy Round #1

    UOJ Easy Round #1

    http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-65f93dd60d787325928193/]「UER#1」跳蚤OS[crayon-65f93dd60d78e377287828/]「UER#1」DZYLovesGraph[crayon-65f93dd60d794788810182/] ...

    02015年4月13日6,359并查集,AC自动机
  • 「fjWC2015」Galaxy

    「fjWC2015」Galaxy

    「题目描述」小X进入了平行宇宙,想在某个平行宇宙开始一段生活。平行宇宙之间用长度为N的仅含有A、B、C、D四个字母的序列标识。每一个由A,B,C,D组成的长度为N的序列标识着不同的平行宇宙。有趣的是,不同的宇宙对应着小X的不同人生,在某些宇宙中,小X的人生过得并不愉快。小X得到了M个特征碎片,特征碎片都为长度小于10的由A,B,C,D构成的序列。如果某个平行宇宙的标识序列包含某个特征碎片(即特征碎片为宇宙...

    02015年2月3日4,407AC自动机,矩阵乘法
  • 「BZOJ2754」[SCOI2012] 喵星球上的点名

    「BZOJ2754」[SCOI2012] 喵星球上的点名

    Descriptiona180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。然而,由于喵星人的字码过于古怪,以至于不能用ASCII码来表示。为了方便描述,a180285决定用数串来表示喵星人的名字。现在你能帮助a1...

    52015年1月15日7,254STL,AC自动机
  • NOI2011阿狸的打字机

    NOI2011阿狸的打字机

    Description 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现,这个打字机是这样工作的:l输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消...

    32014年12月6日9,675dfs序,AC自动机,树状数组
  • 「BZOJ2938」[POI2000] 病毒

    「BZOJ2938」[POI2000] 病毒

    Description二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。示例:例如如果{011,11,00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01,11,000000}为病毒代码段,那么就不存在一个无限长的安全代码。任务:请写一个...

    02014年12月6日6,019深度搜索,AC自动机
  • 「JoyOI1519」博彩游戏

    「JoyOI1519」博彩游戏

    背景BackgroundBob最近迷上了一个博彩游戏……描述Description这个游戏的规则是这样的:每花一块钱可以得到一个随机数R,花上N块钱就可以得到一个随机序列;有M个序列,如果某个序列是产生的随机序列的子串,那么就中奖了,否则不中。Bob会告诉你这M个序列,和身上有的钱的总数N,当然还有R的范围。请你告诉Bob中奖的概率有多少?输入格式InputFormat第一行三个用空格隔开的数N、M和R的范围R。其中1<=R<=9...

    02014年5月11日3,391递推与动规,AC自动机
  • 「hdu2222」Keywords Search

    「hdu2222」Keywords Search

    ProblemDescriptionInthemoderntime,SearchenginecameintothelifeofeverybodylikeGoogle,Baidu,etc.Wiskeyalsowantstobringthisfeaturetohisimageretrievalsystem.Everyimagehavealongdescription,whenuserstypesomekeywordstofindtheimage,thesystemwillmatchthekeywordswithdescriptionofimageandshowtheimagewhichthemostkeywordsbematched.Tosimplifytheproblem,givingyouadescriptionofimage,andsomekeywords,yousho...

    42014年3月24日7,564AC自动机
  • 「BZOJ1030」[JSOI2007] 文本生成器

    「BZOJ1030」[JSOI2007] 文本生成器

    DescriptionJSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章——也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,...

    42014年3月24日8,390AC自动机