数位DP入门题，其实只要搞懂dp[i][j]存的是什么就行了。
用搜索解法的话，每次相当于枚举了比当前位小的所有数字，然后需要记录下是不是上界（第一位）。就题目而言的话还需要记录前面一位是不是6（这决定了当前位可不可以是2）,记忆化的话有一点是当如果是上界（第一位）的时候是不能记忆的，因为记忆话那个其实是存了第len位长的前缀为/不为6的当前位可以从0到9的所有数中的答案，注意这里这个东西是和给定的什么串无关的，同时他也不能有关，因为这个不能把信息完全表示出来。所以只有在不是上届的时候才保存记忆化结果。 继续阅读“[DP][数位DP] HDU 2089 不要62”
https://cn.vjudge.net/problem/HDU-6377
不懂dp的我根本想不到是用dp来做。。。emm
如果把每一对情侣两个人看成等价的，那么可以构造出来，状态只与两个因素有关：一共有多少对情侣；有多少对情侣是坐在一起的，用dp[i][j]来表示有i对情侣，其中j对坐在一起的方案数，在这个的基础上可以往里面继续插入一对新的情侣，而插入的方式和结果总共会导致五种变化，每次都考虑一下，刷表即可。预处理出所有的可能情况，接下来每次输入的时候过一遍dp[n][i]就行了。由于把两个人看成了一样的，所以最后还要乘上2^n，用快速幂即可。 继续阅读“[DP][计数DP][组合数学] HDU 6377 度度熊看球赛”
哭了，真的是蠢，好多人三个题都前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”
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”
https://cn.vjudge.net/problem/HDU-4597
对抗搜索模板题。裸的minimax算法，搜索的时候注意max层要加上点的值，还没有仔细学α-β剪枝所以没用。。。 只用了记忆化（似乎也没什么卵用啊） 不过这个数据量，基础算法足够了。
继续阅读“[搜索][博弈][模板] HDU 4597 Play Game”
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”
为什么模板题都a的这么艰难
调了这么久发现其实原来的就是对的只是样例可以有不同解，蠢的程度也是没谁了。。。
题意就是求DAG上的最小路径覆盖数，而且使得所有路径权值之和最小，而且要输出路径。将每一个点拆成两个点，分别在二分图左右两侧，读入的所有的路都是从左往右。 求最小路径覆盖也就是求最大匹配，而在这一条件下要求总长度最小，将边附上权值求最小权最大匹配即可。由于KM算法 继续阅读“[带权二分图][KM算法][模板] SGU252 Railway Communication”
这题官方题解给了个Dilworth’s theorem，并不懂是什么东西。。。
写出来一些后可以找规律（多写），然后可以发现就是可以把原序列分成几块连续的上升序列，只不过块之间的相对顺序反了过来。。这个也不知道怎么证明，但是感觉是找不到比这个更好的。。这样的话就相当于LIS+LDS的长度是块的大小加上块的数量。实现的时候注意最后一个块可能不完整。
之所以写这个题纯粹是为了提醒自己！数！组！越！界！
暴力去重枚举所有情况，然后前缀和预处理。debug到怀疑学了假的c++，最后的最后发现，数组越界,错误类似于把该写到a[1][x]写到了a[2][x] 里。。
所以数组下标一定要注意啊啊啊啊啊啊啊啊啊
继续阅读“[CF][枚举][预处理][二进制][坑] CF 1017C The Wu”
这个题确实是领悟到了不少东西，lca倍增的思想和用途，思维方法，构建生成树的逻辑，严格次小的要求。发现图论很重要的一个东西就是存储用的数据结构，我不怎么会写前向星于是就很难受了。。就这个题而言是要先求MST，再对MST做LCA，那么就会有两个图，一个是原始的用来求MST，另一个用来求LCA，第二个就是MST这个树本身。所以建了俩图，第二个图是在Kruskal的过程中建立的，与此同时还要记录下来不在MST上的边，以便之后的枚举操作。另外一个需要注意的点就是要求是严格次小，所以的就需要保存一个第二大这么一个数，这个又有很多情况，不同树上区间合并的时候根据两个区间最大的数的关系来处理。
错误的话，1 求LCA的时候应该swap 使得较深的为y，这里写错了 2 数组容量开错，这个今天错了几次，主要是没看清m和n，而且总是蜜汁把m写成n。。 3 数组下标写错（为什么经常做这种蠢事？？？？ 4 跟LL比较大小却初始化为1<<29，，显然不够，改成1<<60就过了，也是最后一个错误
继续阅读“[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题”
