2019.12.28日常总结

2019.12.28日常总结

洛谷P1690

【题意】：
2019.12.28日常总结
【思路】： 先用Floyed算法求出没每两个点之间的最短路，然后暴力求出一种路线，求他的长度，然后统计即可。
【代码】：

【题意】：
2019.12.28日常总结
【思路】： 一个区间的改变，并不会让区间内部元素的相对大小改变。即这个区间的总贡献并不会改变。

进一步的，如果修改区间 $[x,y]$ ，只有点 $x$ 和点 $y+1$ 的贡献会改变。

我们可以根据如上性质联想到差分，然后区间的 $O(N)$ 修改操作就变成了 $O(1)$ 。

【代码】：
2019.12.28日常总结