vp时A题没写出来，场外找的答案，原来思路错了（心虚
A. Trust Nobody
题意
有n个人，其中一些人只说真话，另外一些人只说谎话。每人会说在我们之中至少有x人是说谎者，求说谎者的人数。若所有人的说法矛盾，则输出-1。
思路
枚举答案然后验证即可，若无答案，输出-1。
代码
void solve() {
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
for(int i = 0; i <= n; i++) {
int cnt = 0;
for(int j = 0; j < n; j++) {
cnt += i < v[i];
}
if(cnt == i) {
cout << i << "\n";
return;
}
}
cout << -1 << "\n";
}
B. Lunatic Never Content
题意
给定一个长为n的序列a，定义f(a, x) = [a1 mod x, a2 mod x,..., an mod x]，x是一个正整数。求x的最大值，使得f(a, x)为一个回文序列。
思路
如果要使a,b两个数模x后相等，那么x只能为两个数的差值的所有因数。所以，要使得f(a, x)为回文序列，即模所有左右对称的数的差值的最大公因数。
代码
void solve() {
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
int ans = 0;
for(int i = 0; i < n / 2; i++) {
ans = gcd(ans, abs(v[i] - v[n-i-1]));
}
cout << ans << "\n";
}
C. Dreaming of Freedom
题意
给定n个人和m个选项，让n个人选择，被选择数最多的选项留下来。如果有多个选项留下来，再让n个人选择，直至最后只剩一个选项。如果无论怎么选择最后都会只剩下一个选项，则输出"YES"，否则输出"NO"。
思路
只要确定有n个人可划分为个若干个群体，每个群体的人数相同，并且群体的数量不大于m，则输出"NO"，否则输出"YES"。
枚举每个群体的人数进行验证，枚举范围从1到\(\sqrt n\)，每次枚举的群体的数量为 n/i 和 n/n/i。当 n=1 或 m=1 时，注意特判。
代码
void solve() {
int n, m;
cin >> n >> m;
if(n == 1 || m == 1) {
cout << "YES\n";
return;
}
for(int i = 1; i * i <= n; i++) {
if(n % i != 0) {
continue;
}
if(n / i <= m || (i <= m && i != 1)) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
D. Running Miles
题意
给定一个序列，找一个区间，要求区间内最大的三个值之和减去区间的长度最大。求这个最大值。
思路
设dp[i]为选了i个元素的最大值。则状态转移方程为dp[j]=max(dp[j], dp[j-1]+v[i])，并且每次枚举i的加一时，当前的dp[1]和dp[2]要减一，表示区间增长。
代码
void solve() {
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
array<int, 4> dp{0};
for(int i = 0; i < n; i++) {
dp[1] -= 1;
dp[2] -= 1;
for(int j = 3; j; j--) {
dp[j] = max(dp[j], dp[j-1] + v[i]);
}
}
cout << dp[3] << "\n";
}