标签:算法-二分/三分

当时比赛的时候没做出来这题,做了 洛谷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$ 在根节点...
题解 算法-二分/三分 算法-贪心 算法-倍增
省选/NOI-
题意给出一个 $1..n(\le 10^5)$ 的全排列,有 $m(\le 10^5)$ 次操作,每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。题解只有最后一次询问,所以可以把操作离线处理。先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面,降序就是挪到前面,可以用线段树解决。可以二分答案 $mid$ ,然后将 $< mid$ ...
题解 算法-二分/三分 数据结构-线段树
省选/NOI-
题意自动刷题机每秒会增加或删除 $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...
题解 算法-二分/三分
普及/提高-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2