T1（莫队，增量式维护答案）
https://www.luogu.com.cn/problem/P1494
1731。
看上一篇总结的莫队。双倍经验。
QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;typedef long long LL;
typedef pair<LL, LL> PLL;
const int N = 50010;int n, m, L;
int cnt[N], w[N];
struct Query { int l, r, bcnt, id;
bool operator< (const Query& W) const{if (bcnt != W.bcnt) return bcnt < W.bcnt;return r > W.r;
}}q[N];
PLL ans[N];void work(int x, int type, LL& res)
{res -= (LL)cnt[x] * (cnt[x] - 1) / 2; //无论加还是减，之前的都没了cnt[x] += type;if (cnt[x] >= 2) res += (LL)cnt[x] * (cnt[x] - 1) / 2;
}LL gcd(LL a, LL b)
{return b ? gcd(b, a % b) : a;
}int main()
{scanf("%d%d", &n, &m);L = sqrt(n);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);for (int i = 1; i <= m; i ++ ){int l, r;scanf("%d%d", &l, &r);q[i] = {l, r, (l - 1) / L + 1, i};}sort(q + 1, q + m + 1);LL res = 0;for (int i = 1, l = 1, r = 0; i <= m; i ++ ){while (l > q[i].l) -- l, work(w[l], 1, res);while (r < q[i].r) ++ r, work(w[r], 1, res);while (l < q[i].l) work(w[l], -1, res), l ++ ;while (r > q[i].r) work(w[r], -1, res), r -- ;if (!res) ans[q[i].id] = {0, 1};else{LL a = q[i].r - q[i].l + 1;LL k = gcd(res, a * (a - 1) / 2);ans[q[i].id] = {res / k, a * (a - 1) / 2 / k};}}for (int i = 1; i <= m; i ++ )if (!ans[i].first) puts("0/1");else printf("%lld/%lld\n", ans[i].first, ans[i].second);return 0;
}
T2(斜率优化dp模板,费用提前计算思想）
814。
https://www.acwing.com/problem/content/303/
首先做出dp.dp完了优化转移
由于我们知道分了几批就是为了算启动代价，不如直接累加到值里面，把后面的提前算了！
费用提前计算:把以后启动的代价都算进来。
这样状态就变成了：f[i]，前i个物品选若干次，已经考虑当前批代价和对以后启动时间的代价的最小值。
还可以这样理解：
。这样，以c为横坐标，f为纵坐标，我们发现这是个斜率相同的直线，现在所决策应该是一个点，这个点所形成的的直线的截距最小。这是啥？直接凸包维护就好了，取的值就是遍维护凸包边算就行，最后加进来（加进来一定横坐标单调）。
扩展：t不单调（也就是t可以为负）：那就没有办法利用询问斜率的单调性了，只能维护整个凸包。（原先可以边问边删），二分就好。c不单调：那就套一层平衡树维护凸包。
QAQ
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;const int N = 3e5 + 10;int n, s;
LL c[N], t[N];
LL f[N];
int q[N];int main()
{scanf("%d%d", &n, &s);for (int i = 1; i <= n; i ++ ){scanf("%lld%lld", &t[i], &c[i]);t[i] += t[i - 1];c[i] += c[i - 1];}int hh = 0, tt = 0;q[0] = 0;for (int i = 1; i <= n; i ++ ){while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh ++ ;int j = q[hh];f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;q[ ++ tt] = i;}printf("%lld\n", f[n]);return 0;
}
T3（反悔式贪心及部分贪心的证明）
我的比赛思路：
U题，首先考虑dp，肯定开的状态是：前i个，时间，收益。时间当然开不下，考虑优化。发现对于每一秒，都必须打一只。这样大于i的时间就没有用了，一定不优。这样按照当前选不选就能做。不过复杂度是n^2。只能贪心。考虑留一维。必须有时间，于是留下时间t，就是每个物品看看咋选，发现d>t的没必要考虑，只需要留到后面打掉就行了。如果后面打掉不优，还可以调整。这样我排个序，开了个堆维护当前最优的。然后也是写挂了。
V题，消除一定是区间，考虑区间dp。转移就是要么中间消掉，再打两边，要么枚举断点。没错又写挂了。
W题，安排m个树上不相交路径，求最小值最大。当然二分，然后后面咋做没想好。感觉好像可以把所有路径按照根节点分类？写了45分的链和菊花分。
X题，我的想法，可能一定是删掉原图中某些冗余边？然而对于如何判断这个冗余和上述结论，都没想太好。
在做前两题的时候，u题写了个对拍，是a的。不知道怎么挂了。v题自己也是手捏了很多数据，然而也是wa。
我的思路，维护前i个老鼠的最优解。
实际上要求的其实就是最优解唯一。
两个极值点，一定能分出高下。
我们的贪心就是不断探极值的情况。
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;typedef long long LL;const int N = 100010;int n;
struct Node { int d, v;
bool operator< (const Node& W) const
{if (d != W.d) return d < W.d;return v > W.v;
}
} a[N];
priority_queue<int, vector<int>, greater<int> > q;
LL res;
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i].d, &a[i].v);sort(a + 1, a + n + 1);int tim = 1;q.push(a[1].v);res += a[1].v; //特判，防止里面没东西，一定加进去for (int i = 2; i <= n; i ++ ){if (tim < a[i].d) tim ++ , res += a[i].v, q.push(a[i].v);else{int t = q.top(); //取出来的过期时间一定小于i,既然他能放进去，那i也能放进去。if (t < a[i].v){q.pop();res = res - t + a[i].v;q.push(a[i].v);}}}cout << res << endl;return 0;
}
T4
区间dp。f[i][j]表示i~j最大。
决策：最后一段:f[i][j - 1]
or f[i][p]？？？与中间一段接上再一块消。
这里状态没办法描述了。我们考虑加一维。既然要加上一块消，我们就直接f[i][j][k]，k是向右延拓k个格子和最后一段一块消除。
o。
QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int n, cnt;
int f[N][N][N];
int a[N], c[N], w[N];int dp(int x, int y, int k)
{if (x > y) return -0x3f3f3f3f;if (f[x][y][k]) return f[x][y][k];f[x][y][k] = max(f[x][y][k], dp(x, y - 1, 0) + f[y][y][k]);for (int i = x; i < y - 1; i ++ )if (c[i] == c[y]) f[x][y][k] = max(f[x][y][k], dp(x, i, w[y] + k) + dp(i + 1, y - 1, 0));return f[x][y][k];
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1, j = i; i <= n; i = j){j = i;while (j <= n && a[j] == a[i]) j ++ ;int len = j - i;c[ ++ cnt] = a[i];w[cnt] = len;}for (int i = 1; i <= cnt; i ++ )for (int k = 0; i + k <= n; k ++ ) //有可能处理n个，这里注意f[i][i][k] = (w[i] + k) * (w[i] + k);cout << dp(1, cnt, 0) << endl;return 0;
}
T5(树形dp，二分，树上不相交路径dp套路）
安排m个树上不相交路径，求最小值最大。有最优子结构：全局最优，子树就最优。
考虑二分判断+dp.
优化的关键在于只有一条边传上去。这使得我们可以一个个子树考虑。
子树最优嘛，要是不最优，那最多多向上的一条，所以子树多选一定不劣。那现在问题就是当前点最多贡献多少个答案？
答案就是处理传上来的这些边，排个序，贪心匹配。（为啥？最优子结构啊，当前最优就一定不劣），剩下的最大值再传上去。这样就最优了。o。
偷个懒，这里用multiset。
思想的本质：
其实本质还是dp套路：f[u] = f[son] + ().(son，u之间的贡献）
只不过这里的贡献不仅仅是贡献，还要上传最大的边来维护递推。其实只要知道子树传上来最大的边，son和u的问题就变成贪心匹配的问题了。
所以优化的关键在于只有一条边传上去。这使得我们可以一个个子树考虑。
子树内的路径已经考虑完了，经过根的还没考虑呢，但是经过根的路径每个子节点最多传上来一条~，当然传最大的,我们维护一下就行了。
T6(传递闭包，最优决策分析，贪心，无向图拓扑考虑）
最优解唯一，就可以不断探向最优解了，不断维护局部最优解。考虑递推。
无环图按拓扑排序考虑算是常用思路吧。
做法已经写的很明白了。看思路，首先拓扑图，这样我们就能想到，如果只维护后面的最值就可以了，这样就可以递推了。发现最优解唯一
ok，我们考虑保留u的邻边，我们可以想到，编号小的理应不选就没得选了，因此我们考虑不断取小的。
按v从小到大，如果当前过不去，后面的只能更往后，不可能走回到v来
ok，那这样递推就解决了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;int res, n, m;
bool g[N][N];
bool s[N][N];
int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) g[i][i] = true;while (m -- ){int a, b;scanf("%d%d", &a, &b);s[a][b] = true;}int res = 0;for (int i = n; i; i -- )for (int j = i + 1; j <= n; j ++ )if (s[i][j] && !g[i][j]) //能加{res ++ ;for (int k = j; k <= n; k ++ )g[i][k] |= g[j][k];}cout << res << endl;return 0;
}
T7（树上最小支配集模板）
