牛客 CSP-S 提高组赛前集训营 1 – 解题报告

A – 仓鼠的石子游戏

诶嘿题。画了几张图发现只有\(1\)的情况先手必胜,所以考虑多轮交换先后手即可。

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

using namespace std;

const int MAX_N = 1e3 + 200, table[8] = {0, 0, 1, 1, 1, 1, 1, 1};

int T, n, ai[MAX_N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &ai[i]);
        bool flag = false;
        for (int i = 1; i <= n; i++)
            flag ^= (ai[i] == 1);
        printf(flag ? "rabbit\n" : "hamster\n");
    }
    return 0;
}

继续阅读牛客 CSP-S 提高组赛前集训营 1 – 解题报告

「牛客 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;
}

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

NOIp 2016 解题报告

A – 玩具谜题

sb 题,随便搞。

// P1563.cpp
#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    int dir[N];
    string occupations[N];
    int cmdKeys[M];
    int cmdPath[M];
    // I/O;
    for (int i = 0; i < N; i++)
        cin >> dir[i] >> occupations[i];
    for (int j = 0; j < M; j++)
        cin >> cmdKeys[j] >> cmdPath[j];
    // Process;
    int currentBias = 0;
    for (int i = 0; i < M; i++)
        if (cmdKeys[i] == 0)
            if (dir[currentBias % N] == 1)
                currentBias += cmdPath[i];
            else
            {
                currentBias -= cmdPath[i];
                if (currentBias < 0)
                    currentBias = N + currentBias;
            }
        else if (dir[currentBias % N] == 1)
        {
            currentBias -= cmdPath[i];
            if (currentBias < 0)
                currentBias = N + currentBias;
        }
        else
            currentBias += cmdPath[i];
    cout << occupations[currentBias % N];
    return 0;
}

继续阅读NOIp 2016 解题报告

[Fortuna OJ]Aug 21 – Group A 解题报告

B – Maja

考虑超级暴力,设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案:

\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]

继续阅读[Fortuna OJ]Aug 21 – Group A 解题报告

[Fortuna OJ]Jul 8th – Group B 解题报告

今天这几题咋就那么毒瘤呢?

A – String

其实这道题考场上应该能做出来的,是一道很简单的计数问题。在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题。

考虑这样计数:

  1. 枚举一个\(i\),考虑前\(i-1\)个字符与\(T\)串相同,然后第\(i\)个字符小于\(T[i]\),这样可以保证后面怎么放置字母都能满足要求。
  2. 在枚举了\(i\)的情况下,枚举字符\(ch\),范围在\([a, T[i])\),考虑以下两种情况对答案的贡献:
    1. 如果\(ch = S[i]\),那么后面需要变动的字符个数为\(k\)个,对答案的贡献:\[ {n – i \choose k} 25^{k} \]
    2. 如果不等于,那么后面需要变动的字符个数为\(k-1\)个,因为本位占了一个;对答案的贡献:\[ {n – i \choose k – 1} 25^{k – 1} \]
  3. 贡献之后,如果本位\(T[i] \neq S[i]\),那么把\(k–\),代表多固定了一个不同的字符。

继续阅读[Fortuna OJ]Jul 8th – Group B 解题报告