20联赛集训day11 题解
A据说是抄重了。。B首先肯定二分答案，设二分的答案为 $x$，最终的权值是 $B$，设一对相邻的点为 $(i,j),(k,l)$，那么一定要满足 $|B_{i,j}-B_{k,l}| \leq x$。可以把绝对值拆开，于是就是 $B_{i,j}-B_{k,l} \leq x$，也就是 $B_{k,l} \geq B_{i,j}-x$（因为这个题要增加，所以我们就搞出下界）显然的贪心是让每个点...
A据说是抄重了。。B首先肯定二分答案，设二分的答案为 $x$，最终的权值是 $B$，设一对相邻的点为 $(i,j),(k,l)$，那么一定要满足 $|B_{i,j}-B_{k,l}| \leq x$。可以把绝对值拆开，于是就是 $B_{i,j}-B_{k,l} \leq x$，也就是 $B_{k,l} \geq B_{i,j}-x$（因为这个题要增加，所以我们就搞出下界）显然的贪心是让每个点...
A贪心删除出现次数最少的数。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #d...
A做法一：答案一定是相邻两个的差的最小值。考虑反证法：如果 $[l,r](l+1 < r)$ 是答案，那么中间一定能取到一段小于等于平均数的。做法二：二分答案。首先答案是 $\min_{i,j} \frac{a_i-a_j}{j-i}$，考虑二分最小值，那么相当于对于所有 $j>i$ 要有 $a_i-a_j \geq kj-ki$，也就是 $a_i+k_i \geq a_j+k_...
A二分答案 $x$，加入所有 $\leq x$ 的边后判断图是否强连通即可。一种方法是判联通性+tarjan，但是可以建正向图和反向图分别从 $1$ 开始 dfs 。（这样说明 $1$ 和任何点都有两条路径，所以任意两点都有两条路径）有向图 tarjan 不要判 father，，一开始因为这个吃了罚时。#include <bits/stdc++.h> #define fi fi...
总算是正常的普及组模拟赛难度了。。昨天的甚至算不上普及组模拟赛难度吧（A二分答案，我们肯定是贪心等到必须要选取某个点的时候再选取。可以每次二分判断，也可以开个指针维护中位数在哪里来判断。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned ...