A.
每组给一个和个数（），每次操作可以给一个加2，求是否能使n个数相等
4
3
1 1 3
4
1 1 2 1
2
11 11
1
100
YES
NO
YES
YES
直接扫一遍，记录最大值与当前的差是否能被2整除。
#include<bits/stdc++.h>
using namespace std;
int a[120];
int main() {
//freopen("in.txt","r",stdin);
int t, n; cin >> t;
while (t--) {
cin >> n;
int Max = -1;
for (int i = 0; i < n; ++i)cin >> a[i], Max = max(Max, a[i]);
bool f = false;
for (int i = 0; i < n; ++i) {
int d = Max - a[i];
if (d % 2 == 1) {
f = true; break;
}
}
if (f)cout << "NO" << endl;
else cout << "YES" << endl;
}
}
B.
样例，每组给一个和个数（，中是否存在一个长度至少为3的子序列为回文串。
5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5
YES
YES
NO
YES
NO
在找到两个数相等之后，由于是子序列可以不连续，在两个数之间随便找一个数即可
#include<bits/stdc++.h>
using namespace std;
int n, t, a[5050];
int main() {
//freopen("in.txt", "r", stdin);
cin >> t; while (t--) {
cin >> n; for (int i = 1; i <= n; ++i)cin >> a[i];
bool flag = false;
//双指针思想
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j]) {
if (j - i > 1) flag = 1;
}
}
if (flag == 1) break;
}
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
}
C.
题意：
给出一个字符串， 只包含两个字符‘L’，‘R’，如果为L，只能向左走，如果为R，只能向右走，问一只青蛙从最左端开始走，走到最右端一次最少跳多远。这只青蛙可以跳的距离为 [ 1，最短长度 ] 这个区间。
举例：LRLRRLL，最短跳的距离为 3
首先从 0 位置跳到 第一个 'R', 然后从第一个‘R’跳到第二个或者第三个 'R',最终跳到末尾。
在这个样例中，最短跳的距离为 3， 意味着这个青蛙可以向右跳1步，或者2步，或者3步。
解题思路：
可以将字符串两端加入R，判断两个R的最远距离即可，但注意 最短距离下限为 1 而不是 0。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
string s;
int main() {
int t; cin >> t;
while (t--) {
cin >> s; int len = s.length();
s[len] = 'R';
int ans = 1, j = len;
for (int i = len - 1; i >= 0; --i) {
if (s[i] == 'R')
ans = max(ans, j - i), j = i;
}
if (s[0] != 'R')
ans = max(ans, j + 1);
cout << ans << endl;
}
cin >> s;
}
D.
给一个和个数，求满足＋的二元组，一共有多少对。()
5
4 8 2 6 2
4 5 4 1 3
7
要满足＋的条件，直接排序，然后差值遍历过程从upper_bound找到第一个大于的数即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n; long long a[maxn], b[maxn], d[maxn], tmp[maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 1; i <= n; ++i)cin >> b[i], d[i] = a[i] - b[i];
sort(d + 1, d + 1 + n);
long long ans = 0;
//ai + aj > bi + bj <=> Di > -Dj (ai - bi > -(aj - bj))
for (int i = 1; i <= n; ++i) {
int index = upper_bound(d + 1 + i, d + 1 + n, -d[i]) - d;
ans += n - index + 1;//index表示为第一个大于的位置，总数要n - index + 1
}
cout << ans;
}
E.
一天有个n小时，Vova要睡到一定时间
7 24 21 23
16 17 14 20 20 11 22
3
考虑表示前次睡眠刚好用了次减1操作。记录一个关于的前缀和，舒适睡眠的条件是
同时要考虑当前的这个，是在用了一次减一操作还是没有用。
若用了一次减一操作之后的情况：
若在第次没有用的话：
当然如果，不满足，直接从转移到即可，不需要+1。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 5;
int a[maxn], dp[maxn][maxn], sum[maxn];
int main(){
int n, h, l, r;
scanf("%d %d %d %d", &n, &h, &l, &r);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
sum[i] = sum[i - 1] + a[i];
}
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= i;j++) {
if(sum[i] - j < 0) continue;
if((sum[i] - j) % h <= r && (sum[i] - j) % h >= l) {
if(j != 0) {
dp[i][j] = max(dp[i][j], max(dp[i-1][j], dp[i-1][j-1]) + 1);
} else {
dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
}
} else {
if(j != 0) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
}
int ans = 0;
for(int i = 0;i <= n;i++) {
ans = max(ans, dp[n][i]);
}
printf("%d
", ans);
return 0;
}
F.(未做出，网摘解法)
给一颗有个点的树和一个01数组，表示号节点是黑色还是白色，0为黑，1为白，问对于每个，包含点的联通块中的最大值是多少。
9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9
2 2 2 2 2 1 1 0 2
对于一个树上节点来说，为了扩大的值，只能沿着子节点或者父节点往外扩展，用两个来考虑各自的贡献。
首先考虑子树中的贡献，是的子节点，显然只要，所以
之后考虑来自父亲方向的贡献，是的父节点，若,那么往这个方向扩展只会让变小，所以不予考虑。若，我们需要判断节点取最大值的时候，有没有把节点包含进来，若则肯定包含进来了，当把包含进来时，和在统一联通块，之前假设是＞，所以
若时，没有和在同一联通块，而为了使变大，在的时候有
在写法上，显然最小的值只能是-1，因为一个黑点在不能扩展的时候没有必要再加一个黑点进来。所以小于0的情况只要-1。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn], dp[maxn];
vector<int> G[maxn];
void dfs1(int u, int fa) {
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
dfs1(v, u);
if(dp[v] >= 0) dp[u] += dp[v];
}
}
void dfs2(int u, int fa) {
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
if(dp[u] - dp[v] > 0) {
if(dp[v] != -1) dp[v] = dp[u];
else {
dp[v] += dp[u];
}
}
dfs2(v, u);
}
}
int main(){
int n = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
if(a[i] == 0) {
dp[i] = -1;
} else {
dp[i] = 1;
}
}
for(int i = 1;i < n;i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
}
dfs1(1, 0); dfs2(1, 0);
for(int i = 1;i <= n;i++) {
printf("%d%c", dp[i], i == n ? '
' : ' ');
}
return 0;
}