很久很久没做过图论的题了，做一个忽然意识到自己记错了欧拉回路的意义emmm
就当是复习一下吧。
昨天哈，喝了不少酒干了傻事，该过去的就让他翻篇吧，
继续阅读“[训练指南][简单题][图论] 无向图的欧拉回路 Uva10054”
[字符串] kmp模板题 HDU1711
大概复习了下，裸的kmp，其实这个对我来说重点不是kmp而是学到的新快读挂。。。当发现自己裸读800ms，加快读挂140ms然后前排聚聚还是能90ms的时候就去翻了下他们代码然后发现了这个神奇的，，我本地 甚至不能正常运行的快读。。Oooooooorz。。。
继续阅读“[字符串] kmp模板题 HDU1711”
[训练指南][字典树][简单] strcmp的比较次数 UVa11732
题目给了strcmp()的代码，然后问给出n个串两两之间strcmp总共会用到多少次==操作。建立一棵字典树，节点信息存储一个前缀之前出现的次数即可，另外还需要存储的信息是当前节点 是多少个串的结束点（这样就不用把’\n’也加入树了）
坑点的话，自己wa的原因是没有看到他大小写数字都可以有TAT我用我的只考虑了小写字母的Trie送了好几发wa（貌似每次这种题出错都是这样？
[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942
题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。
继续阅读“[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942”
[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”