「牛客 OI 周赛2 – 提高组」解题报告

A – 游戏

我大概乱搞一下:从最外围向内操作,计算操作次数再取模然后对应姓名即可。我不太了解为什么就过了。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + 200;

char mp[MAX_N][MAX_N];
int n, m, T, delta[MAX_N][MAX_N], now[MAX_N][MAX_N], matrix[MAX_N][MAX_N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(delta, 0, sizeof(delta)), memset(now, 0, sizeof(now));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%s", mp[i] + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (mp[i][j] == 'R')
                    matrix[i][j] = 1;
                else if (mp[i][j] == 'G')
                    matrix[i][j] = 2;
                else
                    matrix[i][j] = 0;
        int cnt = 0;
        for (int i = n; i >= 1; i--)
        {
            delta[i][m + 1] += delta[i + 1][m + 1];
            for (int j = m; j >= 1; j--)
            {
                delta[i][j] += delta[i + 1][j];
                now[i][j] = now[i][j + 1] + delta[i][j + 1];
                int curt = (matrix[i][j] + now[i][j]) % 3;
                cnt += (3 - curt) % 3;
                now[i][j] += (3 - curt) % 3, delta[i][j + 1] += (3 - curt) % 3;
            }
        }
        printf("%s\n", cnt % 3 == 2 ? "dreagonm" : (cnt % 3 == 1 ? "fengxunling" : "BLUESKY007"));
    }
    return 0;
}

B – 水果蛋糕

我先打了个表,把\(n \in [3, 6]\)的都打了一遍,然后发现规律;可惜我用了非常丑的写法,打表打废掉了。最后到手只有 20 分。正解如下:

// B.cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    if (n < m)
        swap(n, m);
    if (m <= 2)
        printf("%lld", n * m);
    else if (m == 3)
        printf("%lld", n + 6 * (n / 6) + 2 * min(n % 6, 3LL));
    else if (m == 4)
    {
        if (n % 6 == 0)
            printf("%lld", 2 * n);
        else if (n % 6 == 1 || n % 6 == 2)
            printf("%lld", 12 * (n / 6) + 4 * (n % 6));
        else if (n % 6 == 3 || n % 6 == 4)
            printf("%lld", 12 * (n / 6) + 4 * 2 + 2 * ((n % 6) - 2));
        else
            printf("%lld", 12 * (n / 6) + 4 * 2 + 2 * 2);
    }
    else
        printf("%lld", (n * m + 1) / 2);
    return 0;
}

C – 好朋友

典型的正难则反系列,刚开始觉得这题比较好做,但是数位 DP 还是不太会处理导致全部炸裂(明天要去做做板子了)。设置状态\(dp[i][j]\)计算长度为\(i\)的、有\(j\)个零的数的个数。防止出现七就行了。具体处理见正解代码:

// C.cpp
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

ll predigits[20], dp[20][4], T, digits[20];

ll solve(ll pos)
{
    if (pos < 1000)
        return 0;
    int tot = 0, x = 0;
    for (; pos; pos /= 10)
        digits[tot++] = pos % 10;
    reverse(digits, digits + tot);
    memset(dp, 0, sizeof(dp));
    dp[1][0] = digits[0] - 1;
    for (int i = 1; i < tot; i++)
    {
        dp[i + 1][0] = dp[i][0] * 9, dp[i + 1][1] = dp[i][0] + dp[i][1] * 9;
        dp[i + 1][2] = dp[i][1] + dp[i][2] * 9, dp[i + 1][3] = dp[i][2] + dp[i][3] * 10;
        dp[i + 1][x] += digits[i] - 1;
        dp[i + 1][x + ((x < 2 && digits[i]) || (x == 2 && digits[i] > 7))]++;
        if (((x < 2 && !digits[i]) || (x == 2 && digits[i] == 7)))
            x++;
    }
    return predigits[tot - 1] + dp[tot][3];
}

int main()
{
    for (ll i = 0, val = 1; i <= 18; i++, val *= 10)
        predigits[i] = solve(val - 1);
    ll ans = 0;
    scanf("%lld", &T);
    while (T--)
    {
        ll lft, rig;
        scanf("%lld%lld", &lft, &rig);
        ans ^= (solve(rig + 1) - solve(lft));
    }
    printf("%lld", ans);
    return 0;
}

我认为这几场 OI 周赛的题质量不高。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注