一句话题解

## [1·P3608 [USACO17JAN]Balanced Photo平衡的照片](https://www.luogu.org/problemnew/show/P3608) 把原数组排好序，每加入一个人就相当于把那个位置上的数$+1$，查询就相当于是查询$1$~$l-1$的权值和以及$r+1$~$n$的权值和，因为原数组排好了序，所以肯定对答案产生了影响（前面加的一定比后面的大），于是单点修改和区间查询，用树状数组维护即可 ## [2·P1606 [USACO07FEB]白银莲花池Lilypad Pond](https://www.luogu.org/problemnew/show/P1606) 由于是要求方案数，不难想到最短路计数，但是求的不是单纯的最短路，而是求在满足最短路的条件下求莲花的摆放方法，每放一朵莲花代价为$1$，所以我们对于每一条莲花，预处理出它花费$1$个代价所能到达的点，连一条$1$的边跑$SPFA$即可，需要注意的是：我们要预处理的时候，我们把终点看成水，最后答案$-1$即可 ## [3.P2184 贪婪大陆 ](https://www.luogu.org/problemnew/show/P2184) 咕咕咕…… ## [4.P4436 [HNOI/AHOI2018]游戏](https://www.luogu.org/problemnew/show/P4436) 从$ n - 1 $倒叙枚举，从一个点开始不停地往左走或往右走，直到走不动为止，但是这样是$O(n^2)$的，所以我们每走到以前已经知道答案一个点，把那个点的与现在点的答案比较更新即可 ## [5.P2312 解方程 ](https://www.luogu.org/problemnew/show/P2312) 由于a的数据范围很大，直接算显然需要高精度，但是我们发现，对于一个方程，可以用类似$Hash$，两遍同时模一个大质数，这样在一定几率上会改变结果，所以我们可以模两个甚至更多的质数来保证正确率 ## [6.P4216 [SCOI2015]情报传递 ](https://www.luogu.org/problemnew/show/P4216) 第一问是LCA的模板题，直接用两点的深度减去他们LCA的两倍即可，但是我们发现，第二问在线似乎不太好做~~（反正我不会）~~，我们发现这一道题和上述的P3608平衡的照片比较相似，所以我们可以考虑离线：先将所有传递操作按照当前时间减去风险值排序，代表在多少秒后会对答案产生影响。然后就是树剖的模板题了，只需要单点修改和区间查询即可 ## [7.P4047 [JSOI2010]部落划分 ](https://www.luogu.org/problemnew/show/P4047) 最小化最小值，显然可以用二分答案来做，所以我们先二分出最小距离，检验用并查集来维护：如果两个点的距离小于二分的答案，就合并，统计答案的话就统计还有那些数的祖先是他自己。这里算距离并不需要开根号，两边同时平方可以减少精度误差 ## [8.P1712 [NOI2016]区间 ](https://www.luogu.org/problemnew/show/P1712) 我们发现，先加入那一个区间对答案并不发生影响，所以我们要值从左往右考虑，每加入一个区间相当于把区间所有值$+1$，覆盖区间大于等于m，显然是区间最大值大于等于m，考虑尺取法，先不断的加入区间，直到最大值大于m，更新答案，并删除区间（区间加-1），比较所有答案的最优解即可，但是我们发现&l&和$r$的值都很大，线段树空间显然不够，所以我们用离散化去重即可 ## [9.UVA11464 Even Parity](https://www.luogu.org/problemnew/show/UVA11464) 发现n到了15，直接爆搜肯定会炸，所以我们可以只爆搜第一排的状态，根据第一排来推后面的排来降低时间复杂度、 ## [10.P4198 楼房重建 ](https://www.luogu.org/problemnew/show/P4198) 用线段树维护斜率，每一次递归改区间的一个儿子，具体操作见[楼房重建题解](https://tbr-blog.blog.luogu.org/solution-p4198)。 ## [11.P2502 [HAOI2006]旅行 ](https://www.luogu.org/problemnew/show/P2502) 咕咕咕…… ## [12.P2024 [NOI2001]食物链](https://www.luogu.org/problemnew/show/P2024) 咕咕咕…… ## [13.P4231 三步必杀](https://www.luogu.org/problemnew/show/4231) 维护两个差分数组，等差数列相当于给一个差分数组$l$~$r$加上公差，所以用两个查分数组维护即可 ## [14.P3203 [HNOI2010]弹飞绵羊](https://www.luogu.org/problemnew/show/P3203) 我们发现，直接暴力算显然会超时，用数据结构似乎又不太好做，所以我们考虑分块，每一块记录这一块需要跳几次，跳出去以后会到那一个点，查询的时候区间两端的块直接暴跳，中间部分可以利用块的信息每一次跳$\sqrt{n}$个，修改的话把该点所在的块倒叙枚举，暴力修改即可