2018/10/10考试记录
今天考试内容比较没有头绪，第一道题看样子是序列上的dp，好像又有后效性，就很无奈。干脆写了随机化，最后拿了50分。正解确实是dp，裸的dp能拿50分，如果用Lowerbound和线段树来初始化，用线段树转移状态，就能拿到满分。时间复杂度为\(O(n\log_2n)\)，要注意一些细节，改了很久。
顺便一提，bool operator<(const T &o)在某些环境下是无法编译通过的，但是在某些环境上却可以编译通过，与-std=c++98选项无关，与警告无关。(T){xxxx}也是一样，但是c++11标准是明确支持的，这两个可能会导致CE。为了避免CE，还是手动写一个struct的构造函数为好，最好是以额外的函数形式写。
第二题同样是没有什么头绪，也写了随机化算法，拿到了30分，但是花费了不少时间。第二题解决方法有二：枚举中间节点，跑最小生成树，或者附加状态的dp，或者叫状压dp。
第三题的暴力，可以枚举根节点，跑树状背包。正解是树分治，可惜没有学。
距离NOIP还有30天，需要加倍努力，进省队还是有希望的。
10.16 得分记录
T1 第一题是简单的模拟，首先预处理出\(s[i] = min\{x_j\}(j \le i)\)，设p指向数组末端，从p向前查找第一个大于\(x_i\)的位置，然后把这个位置改为0，重复这个步骤，直到处理完所有输入，或者\(p == 0\)，然后输出\(p\)即可。
T2 这一道题的正解是排序+贪心+并查集，首先将所有的海拔从低到高排序，然后取出其中最低的一个，如果是属于A城市，则连向周围的遍历过的一个点，重复这个步骤，直到所有的A城市的点都于其他点合并了起来。考试的时候没有什么好的思路，于是随机化+卡时，好像拿了30分。
T3 这一题的做法有很多，暴力分能到70甚至90分，常见的做法是：数链剖分、dfs序+数据结构，都可以树状数组/线段树来做。还有做法是利用并查集的路径压缩思想，可以过90分的点。
T4 正解是枚举从左边切的最大次数，然后按照上下左右的顺序切割，直到完成任务。这些做完之后，将图翻转90°，重复。当时写了个有些问题的贪心，只有20分。
10-20
今天考了分治，但是几道题都没有用分治做。 - 第一题是栅栏涂色，没有想到怎么写，甚至连贪心都没有写出来，是个失误。正解是考虑[L,R]，高度>H的一段，要么这一段竖直涂色，要么全部水平涂色，然后就求水平涂色的上方的一段。 - 第二题的思路是，二分最大价格，利用所有价格小于它的边建最小生成树，直到所有有冲突的点都被连接起来。瓶颈在找有冲突的点，相当于找平面最近点对。 - 第三题是求\(k^s\mod m\)，其中s非常大，一个方法是利用拓展欧拉定理，将s转成longlong来操作，另一个方法是直接将s看做n进制数，然后进行快速幂，这个不容易出错。 - 第四题不妨称为斐波那契图，20分的数据是\(n,m\le10\)，50分的数据是\(n\le16, m \le 1e5\)，当时只想到了50分的做法，没想到成了最高分。只是递推出了第n张图，然后直接跑最短路，但这样是\(O(Vm)\)的，不过可以离线处理，复杂度降到了\(O(V^2)\)，踩了题解中的50分做法。标程是首先与处理出每张图的第一个点第一个点到最后一个点的距离，然后得出u,v到最近的割点的距离，再计算割点之间的距离，不需要建图，能过n<1000的点。（但是实际上，它不处理n>80的部分，因为再向上就会爆longlong。