A - Anti-Adjacency
签.
#include <bits/stdc++.h>
using namespace std; int main()
{
int n, k;
while (scanf("%d%d", &n, &k) != EOF)
{
int remind = (n + ) / ;
puts(k <= remind ? "YES" : "NO");
}
return ;
}
B - Path
签.
#include <bits/stdc++.h>
using namespace std; int x, y, Max;
vector <int> G[]; void DFS(int u, int fa, int deep)
{
Max = max(Max, deep);
for (auto v : G[u]) if (v != fa)
DFS(v, u, deep + );
} int main()
{
while (scanf("%d%d", &x, &y) != EOF)
{
for (int i = ; i <= ; ++i) G[i].clear();
G[x].push_back(y);
G[y].push_back(x);
for (int i = ; i <= ; ++i)
{
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
Max = ;
DFS(, , );
puts(Max == ? "YES" : "NO");
}
return ;
}
C - When I hit my pocket...
签.
#include <bits/stdc++.h>
using namespace std; #define ll long long
int k, a, b; int main()
{
while (scanf("%d%d%d", &k, &a, &b) != EOF)
{
if (a >= (b - ) || k < a) printf("%d\n", k + );
else
{
k -= a - ;
int Loop = k / ;
if (Loop == ) printf("%d\n", a + k % );
else printf("%lld\n", 1ll * b + 1ll * (Loop - ) * (b - a) + k % );
}
}
return ;
}
D - Ears
Upsolved.
题意：
有一个人在一维线段上走
$每次经过i - 0.5 i 是整数, 就在第i个位置放一颗石头$
$并且起点和终点必须是整数点，只能在整数点向$
$这样一条合法的路径可以用一个石头序列来表示$
$现在给出每个位置的石头数量，这个可能是不合法的$
$但是可以在某个位置放置或者移除一块石头$
$求最少的操作次数使得石头序列合法$
思路：
我们考虑一个合法的石头序列肯定是
零碎 + 偶数 + 奇数 + 偶数 + 零碎
这样五部分构成，并且至少有一部分的个数不为$0$
我们考虑$dp[i][j] 表示第i个位置，当前点位于第j个状态$
$转移即可$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 200010
int n, a[N];
ll f[N][]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
memset(f, 0x3f, sizeof f);
for (int i = ; i < ; ++i) f[][i] = ;
// 0 左边零碎
// 1 左边偶数
// 2 奇数
// 3 右边偶数
// 4 右边零碎
for (int i = ; i <= n; ++i)
{
ll Min = (ll)1e18, cost;
cost = a[i];
Min = min(Min, f[i - ][]);
f[i][] = Min + cost; cost = a[i] == ? : (a[i] % );
Min = min(Min, f[i - ][]);
f[i][] = Min + cost; cost = a[i] == ? : (a[i] % == );
Min = min(Min, f[i - ][]);
f[i][] = Min + cost; cost = a[i] == ? : (a[i] % );
Min = min(Min, f[i - ][]);
f[i][] = Min + cost; cost = a[i];
Min = min(Min, f[i - ][]);
f[i][] = Min + cost;
}
ll res = (ll)1e18;
for (int i = ; i < ; ++i)
res = min(res, f[n][i]);
printf("%lld\n", res);
}
return ;
}
F - Pass
Upsolved.
题意：
$有n个人，每个人手中有两个球，球有红蓝两种$
$0代表手中有两个红球$
$1代表手中有一红一蓝$
$2代表手中有两个蓝球$
$每次每个编号为非1的人，如果手中还有球，那就挑一个球给前面的人$
$编号为1的人，如果手中有球，就将球接到结果集中$
$最后结果集为一个长度为2 \cdot n的字符串，r 代表红球, b代表蓝球$
$求结果集的方案数$
思路：
$dp[i][j] 表示到第i位，已经安排了j个红球的方案数$
$那只需要考虑i + 1这一位能不能放红球后者能不能放蓝球，就能确定转移$
$我们考虑第i个人的球至少要放在第i位或者之后$
$因为传递需要一个过程$
$用前缀和维护一下，就可以知道前i位最多放多少红球, 转移即可$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 4010
const ll MOD = (ll);
int n;
char s[N];
ll f[N][N];
int a[N], b[N]; template <class T>
void add(T &x, T &y) { x += y; if (x >= MOD) x -= MOD; } int main()
{
while (scanf("%s", s + ) != EOF)
{
n = strlen(s + );
for (int i = ; i <= n; ++i) a[i] = a[i - ] + - (s[i] - ''), b[i] = b[i - ] + s[i] - '';
memset(f, , sizeof f);
f[][] = ;
for (int i = ; i <= * n; ++i)
for (int j = ; j <= i; ++j) if (f[i][j])
{
if (a[min(i + , n)] > j) add(f[i + ][j + ], f[i][j]);
if (b[min(i + , n)] > i - j) add(f[i + ][j], f[i][j]);
}
printf("%lld\n", f[ * n][a[n]]);
}
return ;
}