2020牛客多校第二场H-Happy Triangle

\(对查询的边x，分为两种情况 \)

\(第一种，x为最大边，只需要找离x最近且比x小的两条边判断a+b>x就够了，此处可用multiset \)

\(第二种，x不是最大边，那么需要找到一个b，使得b \geq x，b-a<x \)[……]

2020牛客多校第二场C-Cover the Tree

\(很明显，记叶子节点数为s，则k=\left \lceil \frac{s}{2} \right \rceil \)

\(那么如何匹配呢？首先要选取一个非叶子节点作为根，然后对其进行dfs得到dfs序\)

$latex 按照dfs序大小排序得到叶子节点u[……]

2020牛客多校第二场A-All with Pairs

\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较，相同的次数记为res_{i,j}，此处可以用哈希进行比较 \)

$latex 因为要取最大前缀，所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j}，注意一下下标的偏[……]

2020牛客多校第一场A-B-Suffix Array

\(令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}[……]

计算电压[洛谷P2011]

题目背景

相信不少人轻松灭掉 1,2 两题（蒟蒻无视此句），我相信，大家对物理也是很有兴趣的（众人：我们对揍人也是很有兴趣的），那么，再奉上 100 分给Physicaler 们。

题目描述

现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电[……]

[LOJ10013]曲线

三分法适合求解凸性函数的极值问题

\(设当前求解的区间为[l, r]，令lmid = l+\frac{r-l}{3}，rmid = r-\frac{r-l}{3}，计算f(lmid), f(rmid)\)

将其中函数值更优的点叫做好点，函数值较差的点叫做坏点[……]

[LOJ10012]Best Cow Fences

\(二分答案，判断是否存在长度不小于L的字段，平均数不小于二分的值\)

\(如果把数列中每个数都减去二分的值，就转化为判定是否存在一个长度不小于L的子段，子序列和非负\)

\(用前缀和维护数列，就可用O(1)的时间查询平均数\)

$latex[……]

[LOJ10011]愤怒的牛

求最小距离尽可能大，采用二分答案的方法

\(对二分的最小距离d进行校对，若不满足条件则减小，满足条件则增大\)

#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;
}

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;

}

[LOJ10010]糖果传递

\(设x_{i}为第i个同学从第i-1个同学获得的糖果数，若x_{i} < 0，则第i-1个同学从第i个同学获得-x_{i}个糖果\)

\(特别地，x_{1}为第1个同学从第n个同学获得的糖果数\)

$latex 均分后，每个同学拥有的糖果为avg[……]

[LOJ10009]钓鱼

\(枚举每一个湖k作为终止点，期间的钓鱼次数则为\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}\)

\(要使钓到数量最多，则需要保证每一次钓到的鱼最多，用优先队列维护\)

$latex 要注意\frac{60H+5\sum_{[……]

1
2
3
…
20
»