傳送門

A. Trust Nobody(暴力)

題意：給出n個(gè)人的陳述，每個(gè)人陳述至少有ai個(gè)人說(shuō)謊，讓你求出可能是說(shuō)謊人數(shù)。
思路：（廢話，可以不看，本來(lái)我考慮一種貪心的方法，假定xxx說(shuō)的是真的，然后檢驗(yàn)，發(fā)現(xiàn)wa2），我們可以觀察到n很小，我們只需枚舉說(shuō)謊的情況即可，然后統(tǒng)計(jì)說(shuō)謊人數(shù)是否符合，時(shí)間復(fù)雜度為n²，這題卡了很多人，主要還是思維定勢(shì)，其實(shí)沒(méi)什么難的。

#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(數(shù)學(xué))

題意：給你一個(gè)數(shù)組，讓你找到一個(gè)最大的模數(shù)x，對(duì)每一個(gè)數(shù)取模x，使得這個(gè)數(shù)組具有回文特性，找不到就輸出0。
思路：首先什么時(shí)候沒(méi)有最大的x，如果說(shuō)已經(jīng)符合回文特性的話，就可以取無(wú)窮大。如果不符合回文特性的話。我們考慮每一對(duì)對(duì)稱不同的數(shù)。
推導(dǎo)：此處al為對(duì)稱軸左側(cè)，ar為對(duì)稱軸有側(cè)的數(shù)，r為余數(shù)，k1,k2為整數(shù),x是模數(shù)。
$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是每對(duì)不同的差的因子，所以直接求最大公約數(shù)即可。

#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(數(shù)學(xué)、暴力)

題意：n個(gè)人每人投一票，給m個(gè)算法，每次保留票數(shù)最多的算法，判斷能否保證最后必定留下一個(gè)算法。
思路：總票數(shù)不變都是n，如果說(shuō)當(dāng)前剩下x種算法， n % x != 0 的話，說(shuō)明至少會(huì)有一種算法會(huì)被淘汰，可以繼續(xù)減少，如果說(shuō) n % x == 0，可以把票數(shù)平均分配，這樣就全部保留了。我們考慮最壞的情況，（投票人故意每次投 n / x ,剩下一個(gè) n % x，一個(gè)個(gè)淘汰），就必須保證，n 不會(huì)被 2~m的數(shù)整除。我們考慮根號(hào)分治，枚舉因子。時(shí)間復(fù)雜度為tsqrt(n)。其實(shí)就是找到最小的質(zhì)因子。

#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(前綴、后綴)

題意：給出一個(gè)數(shù)組，你可以選取一個(gè)長(zhǎng)度大于等于3的區(qū)間，value為區(qū)間內(nèi)三個(gè)最大的值減去(r-l)。
關(guān)鍵：首先左右兩端必定是最大的值中的兩個(gè)。
證明：如果說(shuō)左右區(qū)間兩端不是最大值的兩個(gè)，我們覆蓋的區(qū)間更大，那么我們可以減去這兩個(gè)最大的值外的值，增量不變，但是 r- l變小了，總的值更大了。
思路：上面可以表示為,value=a[l]+a[mid]+a[r]-r+l=a[mid]+a[r]-r+a[l]+l。只需預(yù)處理一下mid右側(cè)的a[r]-r的情況，mid左側(cè)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;
}