qbxt 10 月 Day7 讲课
UOJ 143首先任意长度为二的子序列都是等差子序列，所以我们想让长度 $\geq 3$ 的子序列都不是等差子序列：我们可以利用奇偶性：每次奇数放左边，偶数放右边，两边除二递归下去，保证了每次跨越中心的所有长度 $\geq 3$ 的子序列差都奇偶性不同。构造不同的东西的时候可以考虑奇偶性。一个智力题给一个最大团大小不小于 $\frac{2n}{3}$ 的图，求一个大小为 $\frac{n}{...
UOJ 143首先任意长度为二的子序列都是等差子序列，所以我们想让长度 $\geq 3$ 的子序列都不是等差子序列：我们可以利用奇偶性：每次奇数放左边，偶数放右边，两边除二递归下去，保证了每次跨越中心的所有长度 $\geq 3$ 的子序列差都奇偶性不同。构造不同的东西的时候可以考虑奇偶性。一个智力题给一个最大团大小不小于 $\frac{2n}{3}$ 的图，求一个大小为 $\frac{n}{...
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假设 $a \geq b$树状数组分开维护就好了。#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 ...
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...