https://cn.vjudge.net/problem/HDU-4027
这个题，本身并没有用到区间修改的什么操作。。如果不加优化就基本可以认为是单点修改区间查询的线段树，但是int64的最大值也只需要6次开根号就会收敛到1，因此我们可以加一个优化就是当子区间每一个都是1的话就不再更新区间（就这一个优化真的可以搞定吗。。。）其他的都跟普通的线段树一样了，只不过初始化建树的时候需要一个单独的点修改函数来操作。
继续阅读“[线段树][优化][特征分析] HDU 4027 Can you answer these queries?”
一开始脑子里总是想今天听讲时候的set，可是怎么也想不出来这个怎么用set做。然后又以为必须离线因为1e7 ,可是后来发现给了500mb内存。。。就愉快的离线了。离线的话可以从后往前单调队列。坑点一个是运算中间结果long long，另外一个是我自己手残，单调队列的尾指针用了r，和参数r重合然后把他覆盖了。。。。这是最傻的一次错误了吧。。。
https://cn.vjudge.net/problem/HDU-3695
跟2222几乎一样，求文本中出现了多少个模式串，但是数据量变大了，5e6的长度。这时候用原来的写法已经会tle了，看到别人说用打标记的方式记录trie上一个节点有没有走过，一开始是不理解的，为什么这么做是正确的？后来想了想，AC自动机的算法确定了一个起点之后，沿着fail回溯的路径便已经确定（神奇），所以这条路上被走过的单词尾，再走的时候就会重复，而我们可以简单的把走过的节点计数标志变为-1，而在之后的过程中再遇到就可以不用管这个节点及其之后所有的节点了。注意这个是在while一开始就得判断。
WA的话，是从带括号的那个原串解压过后忘了在最后加’\0’。。。emmmm以后试验这种一定要从大到小试验数据。还有就是模板一定要用自己熟悉的。。原来以为这题问题在于kuangbin的板子不够快后来发现是没标记。。第二个是一开始没意识到q可以不止1位。。
继续阅读“[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora”
http://codeforces.com/problemset/problem/1019/A
今天想起来这坑还没填。心情差.jpg
当时比赛想了一个小时dp，然后在最后10min意识到可以枚举最后所需要的人数然后贪心。。可是已经没时间来实现了，然后就果断地凉了。今天直接补了
一开始纠结，主要在于，这个决策既得考虑人数又得考虑钱，有点像背包，就很不好操作。但是实际上，n范围只有3000，所以完全可以枚举人数，在这个固定的条件下去考虑对于一特定的人数x需要多少钱，就很容易了：每次先把人数大于等于x的减到x-1，把减去的人加到党派1的支持者数量里，这个过程中挑最小的那些累计起来。在做完这些工作后就是看有没有达到人数x，如果达到了/超过了就说明行了，虽然超过的话就不是正好x但是我们只关心钱数的最小值，如果没有达到，那么还需要从剩下的所有人里从小到大累计够人数才可以。
我这里只排序1次，然后每次设置used数组表示一个人是不是在第一步里用过了。算是n^2复杂度吧。当然这个题数据貌似很水怎么都能过。。
实现的话还有一个问题就是按照我的写法遇到p为1的时候是不能设置used的，因为这个其实是针对于党派1之外的来说的。。。因为这个wa了一发。 继续阅读“[CF][贪心][枚举][思维] CF1019A”
https://cn.vjudge.net/problem/HDU-5880
AC自动机模板题，不过判断是否是禁忌串内的这种标记方法还是值得一看的。
主要是理解了AC自动机的板子。。当时比赛没有把这个题写出来也是挫了，其实就是模板题。有一个需要注意的地方是如果禁忌串互相包含怎么操作，这里参考的大佬代码用的pos-1和+1标记是否在括号内的做法，很舒服。
错误的话，把Trie开到main里RE。。本地都RE，然后每个test都要换行，忘了这个PE了一发。
这个题有很多做法，目前先用二分+KMP过了，二分的原理是如果最大字串存在那么这个最大字串的字串也一定满足要求。难得1Y，明天用后缀数组尝试一下来填坑。。
二分答案倒是容易想到，实现的话需要排序后贪心，但是坑在精度上
我用了printf(“%.0f\n”,ans); WA cout<<(int )(ans+0.5)<<endl; AC 就很玄学。。。。学到了学到了
继续阅读“[01分数规划][二分][精度][坑] POJ2976 Dropping tests”
思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
minimax搜索+α-β剪枝优化模板题。
第一个需要处理的就是把状态全部转化成二进制形式，包括三角形，边，棋盘，等等。转化好了之后就可以用minimax搜索了。在一开始的时候边读入边改变局面和cnta，cntb这两个分别代表a和b的得分，这个题有需要注意的一点就是如果一方得分了那么他是可以继续下一轮的，所以每次都要判断走向下一个局面的时候是不是得分。注意α是max层的最大值的最小边界，β是min层的最小值的最大边界，这里对一方操作之后发现不再满足α<=β，其实是跟父节点的另一方作对比的，一旦不满足即说明当前节点不再有利用价值，直接把这个越界的值返回父节点即可（因为父节点还是要更新状态的）这里并没有要求算出具体得分，所以用-1和1 来表示输赢即可，在每一层里加上cnt与5的关系判别也可以做到剪枝的作用。
离散化写挫了就wa了n发。。
先按照右端点排序，设dp[i]为铺满1到i的最小价值，注意是铺满，那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i] l[i]<=j<=r[i]，注意这里有一个-1，对于左端点来说，因为如果两个线段相邻二不相交，比如(1,2)(3,4)，这样其实也是可以的。这里的话，如果直接把端点离散化，就会导致后面的操作很复杂，因为要考虑相邻中间有没有空（我也是这么错的），所以不如直接在一开始读入左端点的时候就给他-1，这样之后就不用什么多余的操作了，直接每次线段树查询最小值即可。 继续阅读“[DP][线段树][离散化][细节][坑] XDOJ 1324”
