\(对查询的边x,分为两种情况 \)
\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)
\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)[……]
\(对查询的边x,分为两种情况 \)
\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)
\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)[……]
\(很明显,记叶子节点数为s,则k=\left \lceil \frac{s}{2} \right \rceil \)
\(那么如何匹配呢?首先要选取一个非叶子节点作为根,然后对其进行dfs得到dfs序\)
$latex 按照dfs序大小排序得到叶子节点u[……]
\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较,相同的次数记为res_{i,j},此处可以用哈希进行比较 \)
$latex 因为要取最大前缀,所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j},注意一下下标的偏[……]
\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)
\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)
$latex 要注意若没有t_j=t_i,则c_i = n,同时c_{n+1}[……]
相信不少人轻松灭掉 1,2 两题(蒟蒻无视此句) ,我相信,大家对物理也是很有兴趣的(众人:我们对揍人也是很有兴趣的) ,那么,再奉上 100 分给Physicaler 们。
现给定一个电阻网络,已知其中每条边上的电阻,和若干个点和负极之间的电压(电[……]
三分法适合求解凸性函数的极值问题
\(设当前求解的区间为[l, r],令lmid = l+\frac{r-l}{3},rmid = r-\frac{r-l}{3},计算f(lmid), f(rmid)\)
将其中函数值更优的点叫做好点,函数值较差的点叫做坏点[……]
\(二分答案,判断是否存在长度不小于L的字段,平均数不小于二分的值\)
\(如果把数列中每个数都减去二分的值,就转化为判定是否存在一个长度不小于L的子段,子序列和非负\)
\(用前缀和维护数列,就可用O(1)的时间查询平均数\)
$latex[……]
求最小距离尽可能大,采用二分答案的方法
\(对二分的最小距离d进行校对,若不满足条件则减小,满足条件则增大\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<stdio.h> #include<algorithm> #include<string> #define MAXN 100010 using namespace std; inline int read() { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) x = (x << 3)+(x << 1)+c-48, c = getchar(); return x; } int n, m, x[MAXN]; int check(int d) { int k = 1, p = x[1]+d; for (int i = 2; i <= n; ++i) { if (x[i] < p) continue; k++; p = x[i]+d; } return k >= m; } int main() { n = read(), m = read(); for (int i = 1; i <= n; ++i) x[i] = read(); sort(x+1, x+n+1); int l = 0, r = x[n]-x[1]; while (l <= r) { int mid = (l+r) >> 1; if (check(mid)) l = mid+1; else r = mid-1; } printf("%d", r); return 0; } |
\(设x_{i}为第i个同学从第i-1个同学获得的糖果数,若x_{i} < 0,则第i-1个同学从第i个同学获得-x_{i}个糖果\)
\(特别地,x_{1}为第1个同学从第n个同学获得的糖果数\)
$latex 均分后,每个同学拥有的糖果为avg[……]
\(枚举每一个湖k作为终止点,期间的钓鱼次数则为\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}\)
\(要使钓到数量最多,则需要保证每一次钓到的鱼最多,用优先队列维护\)
$latex 要注意\frac{60H+5\sum_{[……]