【做题纪要】NOIp长训营期间做题纪要
[AGC006D] Median Pyramid Hard
看了一圈感觉就这题比较可做，那就先写这个，但是还是没啥头绪。
首先看咋写，这题的暴力肯定是直接从第 \(n\) 层开始反推就行的，但是复杂度好像很劣的样子，这肯定不行
考虑二分答案，我们二分塔顶的值，如果比这个点大我们就设为 \(1\)，如果比这个点小我们就设为 \(0\)
我们发现如果有两个相同的值挨在一起，那么它就会一直一直往上走
如果完全没任何相邻的那就一直是 \(0\)，这个明显比较神秘
复杂度 \(O(n \log n)\) 完全能过
代码写的挺神秘的
注意到我写完的代码有唐诗错误，for_(i,1,n) a[i]=read(); 处应该写 for_(i,1,2*n-1)
「JOI 2017 Final」焚风现象
这题似乎很优的样子，话说 JOI 是日本的 NOI 吗
考虑每次修改实际上对于区间内部和区间的非相邻格子没有影响，只对其相邻的两个格子有影响
因此我们可以先对于最开始的区间进行暴力计算，然后对于修改使用线段树维护
但是请看这条
没错，这题不需要线段树，直接暴力维护两点即可
那就解决了，我服了白打了个线段树
「JOI 2014」水筒
这题咋连个输入格式和输出格式都没有，急了，这我咋写啊，LOJ救我，不过咋又是JOI，JOI这么能出题吗
发现这是一个图论的题，看起来挺优秀的，但是其实是平凡题
考虑对于这样的一个图去打邻接矩阵，然后跑 MST，这是很明显的，对于每一条边的长度直接多源 bfs 去求即可，然后跑克鲁斯卡尔或者perm来重构这个图，去建立一棵树就行
最后跑一个树剖或者 lca 就行，由于机房里有 lca 所以考虑使用 lca 来求两点之间距离