【GDKOI】总结 2.16-2.18

发表于 2016-02-19 分类于信息学，原创阅读次数：本文字数： 930 阅读时长 ≈ 1 分钟

2.16

先看数据范围，根据数据范围推得算法的时间复杂度。能打的暴力，在时间允许的情况下就打，不要怕复杂。
有时一个方法想不通，可以换几种方法，不要陷入一种方法中。
将题意转换化简一下，往往就能得出正解。

因为没有环，转化成树后，经典的树形dp。
枚举结点选或不选，得到该节点的子树的答案最大值。

刚开始看到这道题，没有什么特别好的方法。暴力水的70分。
这题和T4的思想类似，可以通过递归求解直径，通过转根，使得另一边的直径可以直接算出来。
只不过要分多种情况，还是挺复杂的。
要尽量保存更多的信息，而不需要重新计算，通过原先的答案推出新的答案。降低时间复杂度。

这题可贪心，并查集加边维护。正解是dp。
dp要分多种情况讨论。
考试时没有想到特别好的方法，暴力太复杂，所以没打。

很简单的转根，也是我最拿手的题型。

这套题是我感觉最好的一套题，很多题之前都做过相类似的。

做过很多次这种类型的题，单调队列判断最远能扩展到的地方。

瑰丽华尔兹，dp加单调队列优化。

欧拉函数有一个公式，但考试时并不知道，可以通过容斥原理筛选并得出答案。

扩展GCD解整数解，第一次较彻底的明白扩展GCD的功能及其原理。
要有较好的数学功底转化并化简题目。

发挥不大好，T1,T2离正解好差一点。

看起来像01背包，然而打完之后发现并不是，因为这道题有后效性。
除非能够确定一个特定的顺序，确保无后效性，再dp就没问题了。
考试时，因为这一问题卡壳了，然后朝其他方向想，想了一个错误的单调队列。
顺序其实很好确定，讨论一下两个不同的作业谁更优即可。

因为不太会化简恒等取mod式，所以直接暴力枚举。
首先要理解好题意，写出一个恒等式，化简。上扩展GCD直接求得相遇所需的最小年限。优化掉一重循环。

可以建关系树，发现树可以用并查集的路径压缩，来压缩路径，通过一个数组d，判断是否矛盾。

题目竟然有800+字…从前面一堆废话中，提取信息：老师：是x的因子，独立数：该点的欧拉函数。
通过递推式求得答案。