Codeforces Round 870 (Div. 2)【A、B、C、D】

A. Trust Nobody(暴力)

题意：给出n个人的陈述，每个人陈述至少有ai个人说谎，让你求出可能是说谎人数。
思路：（废话，可以不看，本来我考虑一种贪心的方法，假定xxx说的是真的，然后检验，发现wa2），我们可以观察到n很小，我们只需枚举说谎的情况即可，然后统计说谎人数是否符合，时间复杂度为n²，这题卡了很多人，主要还是思维定势，其实没什么难的。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 105;
int a[N];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) cnt += (i < a[j]);
		if (i == cnt) {
			cout << i << '\n';
			return;
		}
	}
	cout << -1 << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

B. Lunatic Never Content(数学)

题意：给你一个数组，让你找到一个最大的模数x，对每一个数取模x，使得这个数组具有回文特性，找不到就输出0。
思路：首先什么时候没有最大的x，如果说已经符合回文特性的话，就可以取无穷大。如果不符合回文特性的话。我们考虑每一对对称不同的数。
推导：此处al为对称轴左侧，ar为对称轴有侧的数，r为余数，k1,k2为整数,x是模数。
a l ≡ r ( m o d   x ) a_l\equiv r(mod~x) al​≡r(mod x)
a r ≡ r ( m o d   x ) a_r\equiv r(mod~x) ar​≡r(mod x)
a l = k 1 x + r a_l=k_1x+r al​=k1​x+r
a r = k 2 x + r a_r=k_2x+r ar​=k2​x+r
a l − a r = ( k 1 − k 2 ) x a_l-a_r=(k_1-k_2)x al​−ar​=(k1​−k2​)x
x ∣ a l − a r x|a_l-a_r x∣al​−ar​
x是每对不同的差的因子，所以直接求最大公约数即可。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
int a[N];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int gcd = 0;
	int l = 1, r = n;
	while (l < r) {
		if (a[l] != a[r]) {
			int d = abs(a[l] - a[r]);
			if (d) {
				if (!gcd) gcd = d;
				else gcd = __gcd(gcd, d); 
			}
		}
		l++;
		r--;
	}
	cout << gcd << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

C. Dreaming of Freedom(数学、暴力)

题意：n个人每人投一票，给m个算法，每次保留票数最多的算法，判断能否保证最后必定留下一个算法。
思路：总票数不变都是n，如果说当前剩下x种算法， n % x != 0 的话，说明至少会有一种算法会被淘汰，可以继续减少，如果说 n % x == 0，可以把票数平均分配，这样就全部保留了。我们考虑最坏的情况，（投票人故意每次投 n / x ,剩下一个 n % x，一个个淘汰），就必须保证，n 不会被 2~m的数整除。我们考虑根号分治，枚举因子。时间复杂度为tsqrt(n)。其实就是找到最小的质因子。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0 && i <= m) {
			cout << "NO\n";
			return;
		}
	}
	if (n <= m && n > 1) {
		cout << "NO\n";
		return;
	}
	cout << "YES\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

D. Running Miles(前缀、后缀)

题意：给出一个数组，你可以选取一个长度大于等于3的区间，value为区间内三个最大的值减去(r-l)。
关键：首先左右两端必定是最大的值中的两个。
证明：如果说左右区间两端不是最大值的两个，我们覆盖的区间更大，那么我们可以减去这两个最大的值外的值，增量不变，但是 r- l变小了，总的值更大了。
思路：上面可以表示为,value=a[l]+a[mid]+a[r]-r+l=a[mid]+a[r]-r+a[l]+l。只需预处理一下mid右侧的a[r]-r的情况，mid左侧a[l]+l的情况

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
int l[N], r[N], a[N];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	l[1] = a[1] + 1;
	r[n] = a[n] - n;
	for (int i = 2; i <= n; i++) l[i] = max(l[i - 1], a[i] + i);
	for (int i = n - 1; i >= 1; i--) r[i] = max(r[i + 1], a[i] - i);
	int ans = -inf;
	for (int i = 2; i < n; i++) {
		ans = max(ans, a[i] + l[i - 1] + r[i + 1]);
	}
	cout << ans << '\n'; 
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}