本文迁移自洛谷原文。
赛时看到“误差修复”就一直往随机化方面想了
假设对于时刻 $j$， 第 $i$ 个人的位置为 $a_{i,j}$。 本文统一用 $i$ 表示人，用$j$ 表示时刻
那么我们令 $sum_j = \sum_{i=1}^{n}a_{i,j}$，$squsum_j=\sum_{i=1}^{n}a_{i,j}^2$
再令$deltasum_{j}=sum_{j+1}-sum_j$，$deltasqusum_j=squsum_{j+1}-squsum_{j}$
本文迁移自洛谷原文。
实质上这题可以用4棵不同的树状数组莽过去
大致思路其他的题解已经讲的很清楚了，这里就讲讲树状数组的不同写法和作用。
比如这道题，我写的第1、2、3、4棵线段树，作用分别是：
1，求左端后缀最大值
2，求右端后缀最小值
3，求左端前缀最大值
4，求右端前缀最小值
如果是要处理前缀的话，我们的 add 函数 和 ask 函数 应该这么写：
1 | inline void add(int x,int d){for(;x<mxn;x+=x&-x)val[x]=max(val[x],d);} //add 往后 让后面的数在ask时能够处理到它 |
反之，如果是处理后缀的话：
1 | inline void add(int x,int d){for(;x;x-=x&-x)val[x]=max(val[x],d);}//add往前 |
此外，这题还有个小问题，样例以就很好的体现了：在两个数相同的时候，且它们都可以作为最小/大值，那么，他们的贡献就会被多次计算。
其实没有太大的关系，因为我们可以钦定如果两个数相同，前面的数大于后面的数，就可以处理掉这种情况了。实现的话就是在 ask 左端时 ask $a_i$ 而在 ask 右端时 ask $a_i +1$ 或 $a_i -1$ 即可。
Code:
1 |
|
本文迁移自洛谷原文。
首先我们可以先贪心的想：
假设我们已经匹配到了 $t$ 串的第 $i$ 位，那么有一个结论，就是如果 $t$ 的子串 $t_{i\dots j}$ 是 $s$ 的子串，而 $t_{i\dots j+1}$ 不是，那么最优方案一定是将 $t_{i\dots j}$ 整个截下来。
可以感性证明：如果不用 $t_{i\dots j}$，用 $t_{i\dots j-1}$，那么 $t_{i\dots j-1}$ 肯定是在 $s$ 中的；但如果第 $j$ 个字符加到了后面，就不能确定原来的那一段加上它后是否还在 $s$ 中，就可能不是最优了。
如果暴力地枚举复杂度会达到 $O(n^3)$；
但如果对于 $i$ 二分最远可以匹配到的地方就可以优化到 $O(n^2log_2n)$。
ps. 我写的这个字符串匹配实质上是 $O(n^2)$ 的，但由于题目的要求跑起来实质上跟 $O(n)$ 的差不多。如果总时限要稳在 $O(n^2log_2n)$ 就可以写个 kmp 处理，但会变得更复杂。
code:
1 | using namespace std; |
本文迁移自洛谷原文。
这里是全网唯一一份分块的题解（也可能是唯一一份分块卡过去的做法）。
现将这 $n$ 个数分块。
令 $dp_{f,i,j}$ 表示考虑到某一块中，考虑到第 $i$ 个位置，上一个位置填的数是 $j$ 时，这一块的开头为 $f$ 的方案数对 $dp_{i,j}$ 的贡献的系数。注意，这里是系数，为了好带入到查询时的整合。可以发现，$f$ 对于转移无关。
处理更新的代码：
1 | inline void go(){ |
然后，查询时有些复杂：
首先，单独处理好整个数列的第一个块（因为 $dp$ 存的是系数，不好接入）。
然后，对于接下来的每个块，考虑与上一个块的末尾相接。
先处理好每个块的块首的答案，然后利用 $dp$ 直接计算得到块尾的答案。
注意要时时刻刻取模。
这样，分块的做法就写好了。
不过，如果你只做到了这儿，你只会想绝大多数分块一样TLE 11
一些优化：
对于查询时的处理，将 $dp[3]$ 展开成 $x,y,z$ 来节省常数
尽量的去掉大括号
register inline
快读快输，火车头
快的大小是信仰数 srand(‘xhztxdy’)
使用 C++14 来替代 C++11
痛苦的心路历程(在 mashups 不断测试)：
整体代码：
1 |
|
加上信仰火车头是6kb
所以6kb干了2kb的活
本文迁移自洛谷原文。
这里是验题人的思路（不同于官方题解）
将所有的树都缩成一个点。
对于第 $i$ 棵树，如果与第 $j$棵树有边，那么 $dist_{i,j}$ 为第 $i$ 棵树的 $i$ 号点到第$j$ 棵树的 $j$ 号点的距离。
叶子节点要特判。
尤其要特判当1号节点为叶子（只有一条出边）时的情况。
最后对新图求直径即可。
Code:
1 |
|
本文迁移自洛谷原文。
考虑dp。
令 $dp_i$ 表示走到底 $i$ 个集市时的最大收益。
1.最朴素的dp
循环 $i$，枚举 $j$ 进行转移。
复杂度：$O(n^2)$
2.分离常项
假设现在是 $i$，要从 $j$ 转移
1.$place_j<place_i$
dp[i]=max(dp[j]+U*(place[i]-place[j]))+val[i]
有
$dp_j+U*(place_i-place_j)=dp_j-Uplace_j+Uplace_i$
所以
dp[i]=max(dp[j]-U*place[j])+val[i]+U*place[i]
用线段树/树状数组维护即可。
2.$j>i$
同理。
时间复杂度:$O(nlogn)$
3.日期相同的情况
贪心可得一定是从一个点直着走到另一个点，中间不会回头。
这里单独弄一个dp。
$dpl_i , dpr_i$ 表示以$i$为结束点，进过集市的开始点在 $i$ 的左边/右边的最大收益。
预处理出不考虑相同日期时每一个点的dp值，然后从左往右、从右往左贪心的递推即可。类似最大子段和。
Code:
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
一道较为简单的双指针
每次维护左边的人走到那个旗子，右边的人走到那个旗子，慢慢向中间不断更新靠拢即可。
1 |
|
本文迁移自洛谷原文。
考虑dp。
令 $f_i$ 表示向左移动 $i$ 格时，向上移动的最小格数。
对于数据预处理完后，倒着去一边取 $max$ 即可。（因为它要大于它后面所有的）
1 |
|
本文迁移自洛谷原文。
考虑构图。
对于集合 $i$，如果有 $j$ 的话，对$i$号节点向 $m+j$ 号节点连一条边权为 $a_i+b_j$的边。
由于题目要求说是无还，所以对这张新图跑最大生成树即可。（不是树必然有环）
最大生成树就是将最小生成树 Kruskal 中每次取出边权最小的边改为最大的边即可，
Code:
1 |
|
本文迁移自洛谷原文。
人菜，只会打暴力
虽然是用小号， 但还是div2里第一个AC的
由于每操作一次就相当于将两个不互质的数变得互质，所以我们的目标是找到一种排列使得相邻两个数不互质的数量尽可能的少。
考虑分解质因数。将由相同质因数的放在一起，留下一个做为连接这个质因数与下一个质因数的桥梁。
暴力即可。
1 |
|