[单调栈+线段树]Codeforces407E【k-d-sequence】题解
题目概述有 $n$ 个数，求最长的子区间使得添加 $K$ 个数，排序之后得到一个公差为 $D$ 的等差数列。解题报告我太斯波了，式子都没仔细看就写了个二分，显然不满足单调性……一个区间 $[L,...
[二分图增广路+Tarjan]BZOJ2140【稳定婚姻】题解
题目概述有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP解散之后还能否使得所有人都找到新C...
[线段树+复杂度分析]HDU5634【Rikka with Phi】题解
题目概述有一个序列 $\{a_n\}$ ，现在有三种操作：1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_i=x$ 。3.询问区间和。解题报...
[二分+树状数组]Codeforces1058F【Putting Boxes Together】题解
题目概述有 $n$ 个物品，第 $i$ 个物品在 $a_i$ ，移动一格需要 $w_i$ 的代价。现在有两种操作：1.把 $w_x$ 变成 $y$ 。2.询问把 $[L,R]$ 的物品移动到 $...
[贪心+虚树+状压DP]51Nod1673【树有几多愁】题解
题目概述有一棵树，现在要给这棵树重编号，叶子节点的权值为到根路径的最小值，现在求叶子节点权值的积的最大值，保证叶子节点的个数不超过 $20$ 。解题报告可以想到这样的贪心：一个点的新编号肯定是子...
[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解
题目概述有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次会钦点 $V_i\over{S_i...
[结论+暴力]Codeforces1041F【Ray in the tube】题解
题目概述一个管道，从一端向另一端发射一条射线，问最多能够经过多少两端指定的点。解题报告可能很斯波……隐约会感觉到有用的发射间距 $d$ 很少……实际上真的很少……因为只有 $d=2^k$ 有用。...
[构造+贪心]Codeforces1041E【Tree Reconstruction】题解
题目概述有一棵树，切掉一条树边后会得到两棵树，求出两棵树中的最大编号，记为 $(x,y)$ 。现在给出 $(\{x_{n-1}\},\{y_{n-1}\})$ 。求出一棵满足的树。解题报告我连1...
[LCT+构造]BZOJ3091【城市旅行】题解
题目概述维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $size$ 倍……把一条路径排成序列，...
[随机+差分]Codeforces799F【Beautiful fountains rows】题解
题目概述有 $m\times n$ 的矩阵，第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇数个好的元素，求所有合法 $[A,...
