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\equiv r(modx)$
$a_r\equiv r(modx)$
$a_l=k_{1}x+r$
$a_r=k_{2}x+r$
$a_l-a_r=(k_1-k_2)x$
$x|a_l-a_r$
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;
}