当时比赛的时候没做出来这题，做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡，卡上有数字 $A_i(\le n)$ 。$\forall k$ ，问：每次取 $k$ 张数字互不相同的卡，能取多少次。题解记录每个数字出现的次数为 $s_i$ ，问题就转化为：每次选 $k$ 个正数 $-1$ ，最多操作多少次。然后就可以直接用 洛谷3586 的结论了（...
题意一棵 $n(\le 50000)$ 个点的树，有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守，军队可以同时移动，每小时移动 $1$ 单位长度。问至少要多久才能满足条件，无解输出 -1（没有）。题解答案显然满足单调性，所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
题意给出一个 $1..n(\le 10^5)$ 的全排列，有 $m(\le 10^5)$ 次操作，每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。题解只有最后一次询问，所以可以把操作离线处理。先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面，降序就是挪到前面，可以用线段树解决。可以二分答案 $mid$ ，然后将 $< mid$ ...
题意自动刷题机每秒会增加或删除 $x$ 行代码。存在一个长度 $N > 0$ ，当 某一秒后累积的代码长度 $\geq N$ ，就会提交这个程序，并新建文件。已知刷题机交了 $K$ 道题，求 $N$ 的最值。秒数 $L\le 100000$ 。题解显然 $N$ 越小，交的题目就会越多，所以可以通过二分验证，不过只有刚好 $K$ 道的时候更新答案。唯一麻烦的就是最小值最大值都要求，而 最...
题意有 $N$ 天，每天剩余教室为 $R_i$ 个。有 $M$ 个人要借教室，从 $S_i$ 借到 $T_i$ 。问能否满足所有人，如果不行则输出第一个不满足的人。$N,M\le 10^6$ 。题解本来还想写线段树查询最小值的，然后发现二分+差分就能解决。做法就是二分答案，然后差分修改后验证是否有 $<0$ 的。#include<bits/stdc++.h>
using ...
题意有 $N$ 个矿石，价值和重量为 $V_i,W_i$ 。需要选择一个值 $W$ ，对于区间 $[l,r]$ ，校验值为$$\sum_j 1 \times \sum_j V_j \ \ (j\in [l,r] \ , \ W_j > W) $$总校验值为 $M$ 个区间校验值的总和。求最小总校验值。$N,M\le 200000$ 。题解我纠结了半天 $\sum_j 1$ 到底是啥，直...
题意有 $N$ 个格子，每个格子有权值。最开始每次只能跳 $d$ 格，可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。$N\le 500000$ 。题解可以对 $g$ 二分答案，然后进行验证。令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值，转移方程式为：$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\...
题意定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图，求最小圈的平均值，保留 $8$ 位小数。其中点数 $n\le 3000$ ，边数 $m\le 10000$ 。题解$0/1$ 分数规划，直接二分答案 $mid$ ，然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界，否则增大下界。#include<bits/stdc++.h&...
题意有一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。题解我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树，再对黑边跑剩下的就行了。但打到一半突然发现不行，于是便跑去看题解。显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小，那么我们就可以给所有白边加一个权值 $x$ 然后再跑；如果白边少了同理。...
我们假设在 $AB$ 段走到 $M$ 点，然后走到 $CD$ 段的 $N$ 点，那么可以得到时间为$$T= \dfrac {AM}{P} + \dfrac {MN}{R} + \dfrac {ND}{Q}$$很显然我们的目标就是找到合适的 $M$ 和 $N$ 让时间最小。对于 $M$ ，如果我们知道 $k= \dfrac {AM}{AB}$ ，那么就可以确定 $M$ 的坐标为$$M(A_x+...
10011.愤怒的牛二分答案，然后贪心进行验证，即只要达到了枚举的距离能放就放，如果最后能放下就验证成功。int n,m,ans,s[100005];
inline bool check(int x)
{
int now=1;
for (int i=1;i<m;i++)
{
int j=now+1;
while (s[now]+...
最开始我zz的想法是直接把整个区间二分，但后来才发现只能找到一个。然后看了下题解，因为每个长度为1的区间只可能有一个解，所以直接枚举每一个长度为1的区间来二分即可。只需要注意区间不能重复，所以可以把右端点减一个很小的数即可。我犯的最智障的错误莫过于用快读来读了double。。。而且改了半天今早才想起，感觉白学OI了。#define eps 1e-2
double a,b,c,d,ans[5...