#627 DIV3 题解
组样例，每组给一个和个数（），每次操作可以给一个加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;
typedef long long ll;
const int maxn = 100;
int a[maxn];
int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
int n = 0, Max = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
Max = max(Max, a[i]);
}
bool f = 0;
for(int i = 1;i <= n;i++) {
int d = Max - a[i];
if(d % 2 == 1) {
f = 1; break;
}
}
if(f == 1) {
puts("NO");
} else {
puts("YES");
}
}
return 0;
}
组样例，每组给一个和个数（，中是否存在一个长度至少为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
在找到两个数相等之后，由于是子序列可以不连续，在两个数之间随便找一个数即可，所以条件就是且$i+1
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000;
int a[maxn];
int main(){
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
}
bool f = 0;
for(int i = 1;i < n;i++) {
for(int j = i + 1;j <= n;j++) {
if(a[i] == a[j]) {
if(j - i > 1) f = 1;
}
}
if(f == 1) break;
}
if(f == 1) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
组样例，每组样例给出一个由，组成的字符串，一直青蛙要从最左边跳到最右边(字符串是，最左边是0，最右边是)，到青蛙跳到上时，只能向左边，只能向右跳，在开始跳之前青蛙要选择一个，选好之后，青蛙每次只能跳，，问在保证青蛙能到最右边的情况下，最小是多少。( )。
6
LRLRRLL
L
LLR
RRRR
LLLLLL
R
3
2
3
1
7
1
首先考虑青蛙跳到的时候，一定是从最右边的跳的(不然这个就会变大)，所以最起码要等于这个值，而你要到达最右边这个，为使每次跳的距离尽可能小，应该从第二靠右的开始跳，答案就是两个相邻的最大距离。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
char a[maxn];
int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
scanf("%s", a + 1);
int len = strlen(a + 1);
int ans = 0, last = 0;
for(int i = 1;i <= len;i++) {
if(a[i] == 'R') {
ans = max(ans, i - last);
last = i;
}
}
ans = max(ans, len + 1 - last);
printf("%d\n", ans);
}
return 0;
}
给一个和个数，求满足＋的二元组，一共有多少对。()
5
4 8 2 6 2
4 5 4 1 3
7
要满足＋，就是满足，令，即满足的个数，直接排序，然后遍历过程从upper_bound找到第一个大于的数即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
int a[maxn], b[maxn], d[maxn], tmp[maxn];
int main(){
int n = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
}
for(int i = 1;i <= n;i++) {
scanf("%d", b + i);
d[i] = a[i] - b[i];
}
ll ans = 0;
sort(d + 1, d + 1 + n);
for(int i = 1;i <= n;i++) {
int index = upper_bound(d + 1 + i, d + 1 + n, -d[i]) - d;
ans += n - index + 1;
}
printf("%lld\n", ans);
return 0;
}
一天有个小时，Vova要睡次，每次睡$a_i(1\leq a_i
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\n", ans);
return 0;
}
给一颗有个点的树和一个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 ? '\n' : ' ');
}
return 0;
}
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。
点赞的时候，请宠溺一点