Yahoo Programming Contest 2019

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 + 1) / 2;
        puts(k <= remind ? "YES" : "NO");
    }
    return 0;
}

B - Path

签.

#include <bits/stdc++.h>
using namespace std;

int x, y, Max;
vector <int> G[5];

void DFS(int u, int fa, int deep)
{
    Max = max(Max, deep);
    for (auto v : G[u]) if (v != fa)
        DFS(v, u, deep + 1);
}

int main()
{
    while (scanf("%d%d", &x, &y) != EOF)
    {
        for (int i = 1; i <= 4; ++i) G[i].clear();
        G[x].push_back(y);
        G[y].push_back(x);
        for (int i = 1; i <= 2; ++i)
        {
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        Max = 0;
        DFS(1, 1, 1);
        puts(Max == 4 ? "YES" : "NO");
    }
    return 0;
}

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 - 2) || k < a) printf("%d
", k + 1);
        else
        {
            k -= a - 1;
            int Loop = k / 2;
            if (Loop == 0) printf("%d
", a + k % 2);
            else printf("%lld
", 1ll * b + 1ll * (Loop - 1) * (b - a) + k % 2);
        }
    }
    return 0;
}

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][5];

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        memset(f, 0x3f, sizeof f);
        for (int i = 0; i < 5; ++i) f[0][i] = 0;
        // 0 左边零碎
        // 1 左边偶数
        // 2 奇数
        // 3 右边偶数
        // 4 右边零碎
        for (int i = 1; i <= n; ++i)
        {
            ll Min = (ll)1e18, cost;
            cost = a[i];
            Min = min(Min, f[i - 1][0]);
            f[i][0] = Min + cost;
            
            cost = a[i] == 0 ? 2 : (a[i] % 2);
            Min = min(Min, f[i - 1][1]);
            f[i][1] = Min + cost;

            cost = a[i] == 0 ? 1 : (a[i] % 2 == 0);
            Min = min(Min, f[i - 1][2]);
            f[i][2] = Min + cost;
            
            cost = a[i] == 0 ? 2 : (a[i] % 2);
            Min = min(Min, f[i - 1][3]);
            f[i][3] = Min + cost;

            cost = a[i];
            Min = min(Min, f[i - 1][4]);
            f[i][4] = Min + cost;
        }
        ll res = (ll)1e18;
        for (int i = 0; i < 5; ++i)
            res = min(res, f[n][i]);
        printf("%lld
", res);
    }
    return 0;
}

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)998244353;
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 + 1) != EOF)
    {
        n = strlen(s + 1);
        for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + 2 - (s[i] - '0'), b[i] = b[i - 1] + s[i] - '0';
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 0; i <= 2 * n; ++i)
            for (int j = 0; j <= i; ++j) if (f[i][j])
            {
                if (a[min(i + 1, n)] > j) add(f[i + 1][j + 1], f[i][j]);
                if (b[min(i + 1, n)] > i - j) add(f[i + 1][j], f[i][j]);
            }
        printf("%lld
", f[2 * n][a[n]]);
    }
    return 0;
}