数位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”
