CodeForces 586C – Gennady the Dentist [链表]


点击打开codeforces题目链接 Mean 有N个孩子去看牙科医生,每个孩子都有一个看牙病时哭泣声音值v,吓跑时哭泣声音值d,和自信值p。一个孩子如果去看病,那么他后面一个孩子自信下降v,后面第二个孩子自信下降v-1,后面依次类推,直到v降到0。如果一个孩子在这个过程...

CodeForces 586C – Gennady the Dentist [链表]

点击打开codeforces题目链接 Mean 有N个孩子去看牙科医生,每个孩子都有一个看牙病时哭泣声音值v,吓跑时哭泣声音值d,和自信值p。一个孩子如果去看病,那么...
阅读全文 0

HDU 3746 – Cyclic Nacklace [KMP处理循环节]


点击打开hdu题目链接 Mean 有一个的串,让你在头部或者尾部增加最少的字符,使得这个头尾相接的串的循环节数>1. Analyse 依然还是用KMP处理字符串的循环问题。如果前i个字符构成一个周期串,那么错位部分[fail[i], i]部分恰好是一个循环节,反过来也成立。本题的...

HDU 3746 – Cyclic Nacklace [KMP处理循环节]

点击打开hdu题目链接 Mean 有一个的串,让你在头部或者尾部增加最少的字符,使得这个头尾相接的串的循环节数>1. Analyse 依然还是用KMP处理字符串的循环问...
阅读全文 0

HDU 3068 – 最长回文 [Manacher]


点击打开hdu题目链接 Mean 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串。 Analyse Manacher的简单应用,我的模板封装成了string+vector版本,以前是返回vector结果,TLE了,改成传引用AC了。关于M...

HDU 3068 – 最长回文 [Manacher]

点击打开hdu题目链接 Mean 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串。 Analyse Manac...
阅读全文 0

HDU 3613 – Best Reward [KMP求最长前缀回文串]


点击打开hdu题目链接 Mean 每个字母(宝物)都有一个价值,可正可负。给你一个字符串,让你砍成两个字串s1,s2,字串价值的计算方法是:如果是回文串,那么就是每个宝物的价值之和,否则为0。问你最大可得价值。 Analyse 发现KMP真是博大精深无所不能啊……...

HDU 3613 – Best Reward [KMP求最长前缀回文串]

点击打开hdu题目链接 Mean 每个字母(宝物)都有一个价值,可正可负。给你一个字符串,让你砍成两个字串s1,s2,字串价值的计算方法是:如果是回文串,那么就...
阅读全文 0

HDU 3336 – Count the string [KMP+DP]


点击打开hdu题目链接 题意 一个长度为N的字符串,有N个前缀,求每个前缀在字符串中匹配次数之和。 分析 本题考察对KMP的失配跳转数组的理解,fail[i]数组保存的是,前缀和后缀的最大匹配,即[0, fail[i]]与[i-fail[i], i]匹配。设置dp[i]代表当前匹配到i时匹配的次数...

HDU 3336 – Count the string [KMP+DP]

点击打开hdu题目链接 题意 一个长度为N的字符串,有N个前缀,求每个前缀在字符串中匹配次数之和。 分析 本题考察对KMP的失配跳转数组的理解,fail[i]数组保存...
阅读全文 0

HDU 5442 – Favorite Donut [后缀数组]


点击打开hdu题目链接 题意 有一个长度为N的字符串,找一个起点,可以正着或反着读一遍,问你怎么读字典序最大。 分析 2015年长春网络赛的题。暴力是铁定不行了。网上有后缀数组和最小表示法两种做法,前几天刚学了后缀数组,先用这题练练手。 首先正反向分别构造出长...

HDU 5442 – Favorite Donut [后缀数组]

点击打开hdu题目链接 题意 有一个长度为N的字符串,找一个起点,可以正着或反着读一遍,问你怎么读字典序最大。 分析 2015年长春网络赛的题。暴力是铁定不行...
阅读全文 0

HDU 2222 – Keywords Search [AC自动机模板题]


点击打开hdu题目链接 题意 给你n个单词和一个字符串,问你有几个单词在字符串中出现过 分析 AC自动机的模板题,灵活构造修改模板即可。 C++代码 #include <bits/stdc++.h> using namespace std; struct ACAutomate { static const int maxnode = 50...

HDU 2222 – Keywords Search [AC自动机模板题]

点击打开hdu题目链接 题意 给你n个单词和一个字符串,问你有几个单词在字符串中出现过 分析 AC自动机的模板题,灵活构造修改模板即可。 C++代码 #include &...
阅读全文 0

UVa 1449 – Dominating Patterns [AC自动机]


点击打开uva题目链接 题意 有n个由小写字母组成的字符串和一个文本串T,你的任务是找出哪些字符串在文本中出现的次数最多。例如字符串aba在ababa中出现了2次,但字符串bab中只出现了1次。 分析 第一道AC自动机的题目,AC自动机一般适用于模板多长度短,文本串少而又...

UVa 1449 – Dominating Patterns [AC自动机]

点击打开uva题目链接 题意 有n个由小写字母组成的字符串和一个文本串T,你的任务是找出哪些字符串在文本中出现的次数最多。例如字符串aba在ababa中出现了2次...
阅读全文 0

HDU 2203 – 亲和串 [str匹配水题]


点击打开HDU题目链接 题意 给你两个串a,b,问你是否可以通过循环移位a,使得a种包含b 分析 将a变为a+a,直接在a+a种找b即可,由于数据比较水,直接用库函数或者写KMP都可以 string.find版本 #include <bits/stdc++.h> using namespace std; int main() {...

HDU 2203 – 亲和串 [str匹配水题]

点击打开HDU题目链接 题意 给你两个串a,b,问你是否可以通过循环移位a,使得a种包含b 分析 将a变为a+a,直接在a+a种找b即可,由于数据比较水,直接用库函数或...
阅读全文 0

POJ 3080 – Blue Jeans [字符串匹配暴力]


点击打开POJ题目链接 Description The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated. As an IBM resear...

POJ 3080 – Blue Jeans [字符串匹配暴力]

点击打开POJ题目链接 Description The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing...
阅读全文 0