每日总结不能少！让自己的头脑好好清醒清醒，才不会犯那些所谓的低级错误！
Contest
A. ssoj3045 A 先生砍香蕉树
根据数据范围 (mle 1000,ble 10000)，显然本题直接暴力枚举格点即可。没想到我为了优化代码推半天还推错了……
我最近做题有一个很主观的感知就是，我的复杂度估计很不准，数组大小估计也是。看来要好好反省一下。
DFS 遍历全图的复杂度是 (O(m))，DFS 枚举排列是 (O(n!))，DFS 枚举区间是 (O(n^2))，有单调性可以化为 (O(n)) 或 (O(nlog n))。
BFS 复杂度与 DFS 差不多，主要是在栈空间上面的问题。
最短路 Floyd 复杂度 (O(n^3))，Dijkstra 复杂度 (O(mlog m))，SPFA 复杂度 (O(nm))，最小生成树 Kruskal (O(mlog m))。
LCA 欧拉序上 ST 算法复杂度预处理 (O(nlog n))，每次询问 (O(1))。
拓扑排序 (O(n+m))，强连通分量 Kosaraju (O(n+m))（求后序遍历 dfn (O(m))，从 dfn 最大的顶点反向 DFS 为一个强连通分量；剩余点继续取 dfn 最大 DFS (O(n))）。
log 级别数据结构有 树状数组、线段树，并查集均摊 (O(1))。线段树开 4 倍空间，常数大。
排序算法 (O(nlog n))。
先背诵下来，再理解理解。
B. 草堆摆放 (restack)
FJ 买了一些干草堆，他想把这些干草堆分成 (N) 堆 ((1le Nle 100,000)) 摆成一圈，其中第 (i) 堆有 (B_i) 数量的干草。不幸的是，负责运货的司机由于没有听清 FJ 的要求，只记住分成 (N) 堆摆成一圈这个要求，而每一堆的数量却是 (A_i) ((1le ile N))。当然 (A_i) 的总和肯定等于 (B_i) 的总和。FJ 可以通过移动干草来达到要求，即使得 (A_i=B_i)，已知把一个干草移动 (x) 步需要消耗 (x) 数量的体力，相邻两个干草堆之间的步数为 1。请帮助 FJ 计算最少需要消耗多少体力才能完成任务。
与蓝书 P4 分金币同理。最终转化为求解中位数。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
int n, B[100005];
ll ans;
int main() {
scanf("%d", &n);
for (int i=1, A; i<=n; ++i) scanf("%d%d", &A, &B[i]), B[i]+=B[i-1]-A;
sort(B+1, B+n+1);
for (int i=1, m=n+1>>1; i<=n; ++i) ans+=B[m]>B[i]?B[m]-B[i]:B[i]-B[m];
printf("%lld
", ans);
return 0;
}
C. Elephants (slo)
对于一个 (1-N) 的排列 (a)，每次你可以交换两个数 (a_x) 与 (a_y)，代价为 (m(a_x)+m(a_y))。若干次交换的代价为每次交换的代价之和。(N) 个 100 到 6500 的整数，按照某个顺序排列。现在要交换若干次，每次交换两个数的位置，使得变成目标顺序。 请问将 (a) 变为 (b) 所需的最小代价是多少。
D. 电路维修
目前想法是 Dijkstra 做最短路，但因为数据水 AC 了。实际上这么做是有问题的，因为一个节点可能被多次访问。
正解应该是在 deque 上做 BFS。维护双端队列，新入队的边如果边权为 0 加入队头，边权为 1 加入队尾。这样就没有什么问题了。
我真是疯了，数组开那么小还 debug 半天……