A.Yet Another Tetris Problem
题意：
给定一组序列a，ai代表这一列有多少个方块，询问使用若干个一列两行的方块能否将所有的方块消除
题解：
题意可以转化为对于a，每次可以使任意ai加2，询问最后序列a所有元素是否能相等。那么只要判断序列所有元素的奇偶性是否相同即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[105];
void solve()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
if ((a[i] % 2) != (a[1] % 2))
{
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}B.
题意：
给一个长为n(≤5000)的数组，问是否存在一个长度至少为3的子序列是回文的。
题解：
只要两重for循环，判断一个数的左右是否存在一个值相等即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[5005];
void solve()
{
int n;
scanf("%d", &n);
map<int, bool> mp;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (mp[a[j]])
{
puts("YES");
return;
}
}
mp[a[i]] = 1;
}
puts("NO");
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}C.Frog Jumps
题意：
一个青蛙，一开始只能往右跳，[1,n]有一些字符'L'或者'R'。青蛙可以一开始确定一个最大跳跃距离d，以后他在什么字符的格子就只能往这个方向跳[0,d]步（不能越界）。求跳到n+1需要的最小的d。
题解：
如果有一段全'L'的区间长度为S，如果d<=S那么肯定跳不过去，但是d==S+1就能跳过去了，所以就是全最长的连续'L'区间长度，结果就是长度+1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[maxn];
void solve()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
int t = 0, ans = 0;
for (int i = 1; i <= n + 1; i++)
{
if (s[i] == 'L')
t++;
else
{
ans = max(ans, t);
t = 0;
}
}
printf("%d\n", ans + 1);
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}D.Pair of Topics
题意：
求有多少对(i,j)(i<j)，满足ai+aj>bi+bj。
题解：
移项得ai-bi>bj-aj,即bi-ai<aj-bj,那么我们对于每一位j只需要求前面有多少个bi-ai<aj-bj即可，可以通过离散化后用树状数组即可，每次求query(aj-bj-1)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], b[maxn], c[maxn << 1];
int val[maxn << 1], m;
inline int lowbit(int x) { return x & (-x); }
void add(int x, int val)
{
for (; x <= m; x += lowbit(x))
c[x] += val;
}
ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res += c[x];
return res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
m = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
val[++m] = a[i] - b[i] - 1;
val[++m] = b[i] - a[i];
}
sort(val + 1, val + m + 1);
m = unique(val + 1, val + m + 1) - (val + 1);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int pos1 = lower_bound(val + 1, val + m + 1, a[i] - b[i] - 1) - val;
ans += query(pos1);
int pos2 = lower_bound(val + 1, val + m + 1, b[i] - a[i]) - val;
add(pos2, 1);
}
printf("%lld\n", ans);
return 0;
}E.Sleeping Schedule（dp）
题意：
一共要睡n次，在第i-1次刚睡醒的时候可以控制是ai小时或者ai-1小时后睡第i次觉。每天有h小时，每次睡觉的开始时间在[l,r]中是一次正常作息。求n次睡觉能得到多少次正常作息。
题解：
dp[i][j]表示已经睡了i-1次觉，第i-1次觉是j时刻醒的，那么我们可以通过dp[i][j]状态转移得到dp[i+1][(j+ai)%h]和dp[i+1][(j+ai-1)%h]的值，最终解为dp[n+1][x] (0<=x<h)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[2005], dp[2005][2005];
int n, h, l, r;
int judge(int x)
{
return l <= x && x <= r;
}
int main()
{
scanf("%d%d%d%d", &n, &h, &l, &r);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < h; j++)
{
if (dp[i][j] < 0)
continue;
dp[i + 1][(j + a[i]) % h] = max(dp[i + 1][(j + a[i]) % h], dp[i][j] + judge((j + a[i]) % h));
dp[i + 1][(j + a[i] - 1) % h] = max(dp[i + 1][(j + a[i] - 1) % h], dp[i][j] + judge((j + a[i] - 1) % h));
}
}
int ans = 0;
for (int i = 0; i < h; i++)
ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}F.Maximum White Subtree（树形dp）
题意：
给一棵树，树上有一些黑点白点，对于每个点，选择一个包含该点的连通块，求白色点数量减黑色点数量的最大值
题解：
将树转化为以1为根节点的有根树，dp[u]表示以该点为根构造一棵子树且答案一定包含该点贡献的最大值, ，这样我们就可以求出该点子树部分的贡献。对于该点父节点fa那边的贡献，因为该点对dp[fa]的贡献为max(0,dp[u])，所以我们可以算出dp[fa]除去该点的剩余部分的贡献，所以u点的答案为dp[u]+max(0,(ans[fa]-max(0,dp[u])))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], dp[maxn], ans[maxn];
vector<int> G[maxn];
int n;
void dfs1(int u, int fa)
{
for (auto v : G[u])
{
if (v == fa)
continue;
dfs1(v, u);
dp[u] += max(0, dp[v]);
}
dp[u] += (a[u] ? 1 : -1);
}
void dfs2(int u, int fa)
{
for (auto v : G[u])
{
if (v == fa)
continue;
int t = ans[u] - max(0, dp[v]);
ans[v] = dp[v] + max(0, t);
dfs2(v, u);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
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);
ans[1] = dp[1];
dfs2(1, 0);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
puts("");
return 0;
}
京公网安备 11010502036488号