Codeforces Round 621[CF1307]
[链接](<http://codeforces.com/contest/1307)
Problem A
暴力贪心即可。
Problem B
显然一直用最大值跳，跳到总和大于 $x$ 就可以了。
注意特判最大值 $>x$ 的情况。
Problem C
显然出现次数最多时，该字符串的长度只为 $1$ 或 $2$。
前缀和计算一下就好了。
Problem D
一道好题。
题意
给 $n$ 个点 $m$ 条边的无向图。现在你需要在图中加上一条不是自环的边，使得最短路最大。这条边的两个顶点必须在给定的集合 $S$ 内。
$n,m\leq 2\times 10^5,|S|\leq n$
题解
分类讨论：
1，这条边无法影响添加前的答案，此时答案为 $dis_{1,n}$
2，这条能影响答案：
设 $f_i$ 表示点 $i$ 到 $1$ 的距离，$g_i$ 表示点 $i$ 到 $n$ 的距离。这个可以用BFS求出。
题目转换成，给 $|S|$ 个点，每个点有两个值 $f_i,g_i$ ，需要选两个点，使得 $\min(f_i+g_j,f_j+g_i)+1$ 最大。
不妨假设 $f_i+g_j\leq f_j+g_i$，亦即 $f_i-g_i\leq f_j-g_j$。
因此对于每个点，按 $f_i-g_i$ 从小到大排序。枚举点 $i$，求出前缀最大的 $g_j$即可。
时间复杂度 $O(n\log n+m)$。
程序
1 | const int N=4e5+5; |
Problem E
题意
令一道好题。
$m$ 头奶牛，每头奶牛的类型为 $f_i$，能吃 $h_i$ 个草。$n$ 个草坪从左到右排列，每个草坪当中长了类型为 $g_i$ 的奶牛才能吃的一单位的草，被牛吃后不再长草。
奶牛从左或者从右边出发，一直吃下去，直到吃了 $h_i$ 个草后，睡在那个位置。
一种合法的吃草方案为安排一些奶牛吃草，每只奶牛走的时候不能跨过睡着的奶牛。
两种方案不同当且仅当存在某只奶牛在一种方案出现而在另一种方案不出现或者某只奶牛的出发点不同。
求出合法的吃草方案中，最多能选出多少奶牛，以及此时的情况总数对 $10^9+7$ 取模后的值。
$n,m\leq 5000$
题解
听说有 $O(n)$ 或 $O(n\log n)$ 做法。。。
显然的是，相同类型的奶牛只能最多放两只。
不妨试试枚举分界点 $k$。
从左边走的和从右边走的都不能跨过 $k$。然后对于每种奶牛的类型算方案数，相乘起来加进贡献里。
设 $l$ 为只能从左边走的奶牛数量，$r$ 为只能从右边走的奶牛数量，$b$ 为都能走的奶牛数量。
分类讨论一下：
用两只奶牛走的方案数，$l\cdot b+r\cdot b+b\cdot (b-1)$。
只用一只奶牛走的方案数，$l+r+2b$。
当 $l\cdot b+r\cdot b+b\cdot (b-1)>0$ 的时候就必须用两只。
暴力计算，时间复杂度 $O(n^2)$。
但是这样算会算重，因为一种方案可能对应多个分界点。
强行将分界点靠左，也就是枚举左边的集合中，跑得最远的奶牛是哪个，这样就不会算重了。
需要注意一些细节。
程序
1 | const ll mod=1e9+7; |
Problem F
题意
一棵树中，有些给定的点作为中转站，可以加满油。车的油箱容量为 $k$ ，初始是满的。每走一条边消耗 $1$。容量为 $0$ 时不能继续走。
$m$ 次询问，问是否能从 $u_i$ 走到 $v_i$。
$n,m\leq 2\times 10^5$
题解
记一个中转站 $i$ 向外走 $\leq \frac{k}{2}$ 步后（可以走到边上）形成的集合是 $S_i$，若 $S_i$ 和 $S_j$ 的交集不为空则两点间可以互相到达，能互相到达这个条件满足传递性，因此可以用并查集合并之。
每次询问的时候亦可以把起点与终点当做一个临时的中转站。
但是这个 $\frac{k}{2}$ 步比较麻烦，它可以走到一条边的中点上。因此在每条边的中点处多加一个点，变成走 $k$ 步即可。
这个走 $k$ 步可以用BFS实现。
那么首先判断一下两点间的距离是否 $\leq 2k$，如果是，直接输出’YES’就好了。
否则就都向对方跳 $k$ 步，然后判断跳完后两点是否在同一个集合内就可以了。
这个跳 $k$ 步可以用树剖或者倍增实现。
时间复杂度 $O(n\log n)$。
程序
1 |
|