作者： itewqq

发布于

[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning

思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。

需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”

发布于

[对抗搜索][剪枝][建模转化][模板] POJ 1085

minimax搜索+α-β剪枝优化模板题。

第一个需要处理的就是把状态全部转化成二进制形式，包括三角形，边，棋盘，等等。转化好了之后就可以用minimax搜索了。在一开始的时候边读入边改变局面和cnta，cntb这两个分别代表a和b的得分，这个题有需要注意的一点就是如果一方得分了那么他是可以继续下一轮的，所以每次都要判断走向下一个局面的时候是不是得分。注意α是max层的最大值的最小边界，β是min层的最小值的最大边界，这里对一方操作之后发现不再满足α<=β，其实是跟父节点的另一方作对比的，一旦不满足即说明当前节点不再有利用价值，直接把这个越界的值返回父节点即可（因为父节点还是要更新状态的）这里并没有要求算出具体得分，所以用-1和1 来表示输赢即可，在每一层里加上cnt与5的关系判别也可以做到剪枝的作用。

继续阅读“[对抗搜索][剪枝][建模转化][模板] POJ 1085”

发布于

[DP][线段树][离散化][细节][坑] XDOJ 1324

离散化写挫了就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”

发布于

[DP][数位DP] HDU 2089 不要62

数位DP入门题，其实只要搞懂dp[i][j]存的是什么就行了。

用搜索解法的话，每次相当于枚举了比当前位小的所有数字，然后需要记录下是不是上界（第一位）。就题目而言的话还需要记录前面一位是不是6（这决定了当前位可不可以是2）,记忆化的话有一点是当如果是上界（第一位）的时候是不能记忆的，因为记忆话那个其实是存了第len位长的前缀为/不为6的当前位可以从0到9的所有数中的答案，注意这里这个东西是和给定的什么串无关的，同时他也不能有关，因为这个不能把信息完全表示出来。所以只有在不是上届的时候才保存记忆化结果。 继续阅读“[DP][数位DP] HDU 2089 不要62”

发布于

[DP][计数DP][组合数学] HDU 6377 度度熊看球赛

https://cn.vjudge.net/problem/HDU-6377

不懂dp的我根本想不到是用dp来做。。。emm

如果把每一对情侣两个人看成等价的，那么可以构造出来，状态只与两个因素有关：一共有多少对情侣；有多少对情侣是坐在一起的，用dp[i][j]来表示有i对情侣，其中j对坐在一起的方案数，在这个的基础上可以往里面继续插入一对新的情侣，而插入的方式和结果总共会导致五种变化，每次都考虑一下，刷表即可。预处理出所有的可能情况，接下来每次输入的时候过一遍dp[n][i]就行了。由于把两个人看成了一样的，所以最后还要乘上2^n，用快速幂即可。 继续阅读“[DP][计数DP][组合数学] HDU 6377 度度熊看球赛”

发布于

[二分][贪心][比赛] 百度之星2018初赛(B) 1004 p1m2

哭了，真的是蠢，好多人三个题都前500了，我3个题吊车尾，感觉代码能力亟待提升。。。

二分答案，每次判断的时候用cnt记录遍历整个数组，比mid大的就cnt+=ar[i]-mid;小的就cnt+=mid-ar[i];这样其实算的是一个下限，也就是比他小的数都只加到了mid而没有多加，因为这样可以使得比mid大的那些，通过他们-2转移来的+1更好的利用，这样的话如果cnt<=0，那说明至少[mid,R]里仍然又满足要求的，所以应该往右边继续扩展，因为我们要求的是最大值！这里错了n发，就是没有搞清楚mid应该是靠右的而不是靠左emmmmmm。然后就是一开始想多了，上限下限都考虑了，后来才意识到要求的是最大值，只要下限可以操作就可以一直往右扩张。最后判断是否-1就是再把数组这样过一遍看看是不是cnt<=0，如果是的话说明是可以操作的（其实我很好奇怎么不可行。。 继续阅读“[二分][贪心][比赛] 百度之星2018初赛(B) 1004 p1m2”

发布于

[搜索][meet in the middle] CF1006F Xor-Paths

https://cn.vjudge.net/problem/CodeForces-1006F

题意要求从矩形左上角走到右下角的路，满足只能向右/向下走，然后路上的数值以后之后的值等于k。

简单的想的话，所有可能的情况大概是C(20,40)，无疑超时，然后记录下到每个点的所有xor值的数量的话就可以meet in the middle了，另一个搜索从右下角开始，两个都只需要搜一半长度，对于这种指数复杂度的来说就相当于开了根号，复杂度暴降，值得拥有。
注意的点，第一是map的使用，感觉自己这些还是有点不灵活。。。第二是LL，已经不知道因为这个错过多少次了。。包括参数表里的long long和int也是注意的点 继续阅读“[搜索][meet in the middle] CF1006F Xor-Paths”

发布于

[二分图带权匹配][KM算法][图论][模型转化] SGU 206 Roads

https://cn.vjudge.net/problem/SGU-206

这个题乍一看不可做系列(难道不是吗)，像是跟生成树相关的问题。然而看了dalao的博客和论文之后总算搞明白了原来要转化为二分图模型。而之所以能转化就是因为里面的绝对值去掉不等式（去绝对值用的是贪心的思想，1-n-1之间的都要变小，n到m的都要变大）之后，非树边 j 和树边 i 的delta关系可以写成Di+Dj>=Ci-Cj,然后dalao们就想到了KM算法里的标杆与权值之间的不等式关系 鬼知道他们怎么想到的 继续阅读“[二分图带权匹配][KM算法][图论][模型转化] SGU 206 Roads”