sakura樱のOI日志

今天把前面么得解决的题目全部过了一遍~外加一套模拟题……

现在还存在的问题

1、（非常重要了）一定不要感冒~不然noip去不成了！！！！

2、现在做题目总是想不出正确的算法，每次别人一提示，自己就会了，可是noip没人会给提示啊~唉……基础还是有点不扎实……

3、继续dp训练……...

关于树的多叉转二叉，貌似知道左儿子右兄弟就行了，考到TDP可能性本来就小，需要多叉转二叉的可能就更小了。。。

关于离散化，对于一维的一般就是对数轴划分区间，然后按一端排序，然后操作，还有一些就是标记法，来模拟覆盖，还涉及一些贪心什么。二维的主要就是矩形划分，基本不会写，估计考的可能性不大，至于三维？残念。。。

关于博弈论。知道必胜状态和必败状态就可以了，必胜必败都是对于面临此状态的人来说的，如果此状态可以转移到任何一个必败状态，那么必然会使其如此转移，那么另一个人必败，则此状态是必胜状态；如果此状态不能转移到任何一个必败状态，只能转移到必胜状态，那么无论如果行动，另一个人都会面临必胜状态，则此状态时必败状态。这样的话，可以先缩小问题规模，考虑游戏临近结束的状态，然后进行逆推。还有一种是于数值有关的，可以DP，将各种行动作为状态转移，固定一个阶段的总收益，计算一个人的收益，这样有另一个人的收益，可以选择最大来DP，具体就是usaco上的a game。

◆线性连接性的问题（包括分配问题，转换问题，连接问题，及宏观扩展），这样的例子比较多，方程就是由一维来记录处理到的线性位置作为阶段，然后用额外的未来记录分配的情况，之前临近的连接情况等，这样一个一个把状态连接起来得最优

例子：

P1323化工厂装箱员 P1386矿工配餐 P1417魔法塔防 P1421更换轮胎 P1456最小总代价 P1470教主的后花园 P1002过河

◆线性的选择问题

这种就是...

就这样，今天开始：）下面的都是做过超链接的了，直接点就能看到文章了