标签:算法-二分/三分

题意自动刷题机每秒会增加或删除 $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\...
题解 动态规划 算法-二分/三分 动态规划-线性DP
提高+/省选-
题意定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图,求最小圈的平均值,保留 $8$ 位小数。其中点数 $n\le 3000$ ,边数 $m\le 10000$ 。题解$0/1$ 分数规划,直接二分答案 $mid$ ,然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界,否则增大下界。#include<bits/stdc++.h&...
题解 算法-二分/三分 图论-负环
省选/NOI-
题意有一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 $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...
题解 算法-二分/三分
普及/提高-