-->

51NOD 做好题记录

大佬们都做51NOD的啊
过完NOIP想提升一下自己的实力
于是也来51NOD学习了啊
那就来除波草吧

3/?


4级算法题:

51nod 1255 字典序最小的子序列

一开始看错了题 以为就是要字典序最小 然后中间可以出现多个(其实这道题可以改编成这样的嘛 做法相似)
首先一个想法:你要字典序最小 但是又要考虑到每个字母都被选一次 其实这个字母可能字典序很大 你是不想选它的 所以你就要记录所有字母最后出现的位置
如果到最后的位置你还没有选过它 那么到最后的位置就要选它了
而我们记录下没有选过的字符中 最后位置在最前面的字符 还有位置
但是 我们需要的字典序最小 就询问一下每个没有选过而且比上述字符字典序还小(或者相同)而且出现的下一个位置在上述的最后位置的前面 就可以选
简单点说就是一个小贪心


7级算法题:

51nod 1230 幸运数

一眼就是一道数位dp 关键是怎么写
F[i][j][k]表示从最高位往前到第i个位 之前的和为j 平方和为k

然后就是简单的dp了


51nod 1299 监狱逃离

啊啊啊不会做啊
听说可以用最小割写 我写了一发 就T了
我的感觉这道题怎么有点DFS序+虚树什么的 肯定不对啦
正解是:树形动态规划
简单点说 以i为子树
F[i][0] 表示子树内有犯人上来 没有出路
F[i][1] 表示子树内没有犯人上来 没有出路
F[i][2] 表示子树内没有犯人上来 有出路
然后转移一下就好了


待完成的题目

51nod 1471 小S的兴趣
51nod 1768 Rikka with Sequences KDtree维护历史最大值