Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的,自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:

  • 不存在两个相同的前缀和。
  • 不存在一对前缀和,其异或值为\(x\)。

针对\(x\)的大小关系,我们可以分成两种情况:

  • \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
  • \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

继续阅读Codeforces 1174D:Ehab and the Expected XOR Problem 题解

「NOIp 2012 疫情控制」题解

主要思路

大概可以想到二分出时间,然后把所有的点往上跳,再把能跨子树分配的点进行分配。思路差不多就是这样,还是很自然的一个思路。

但是有一些细节值得注意:跨子树分配和当前子树覆盖的优先级需要处理好。如果这个不处理好只能拿到洛谷上 80% 的数据。这个地方我改了很久,最后发现需要把跨子树分配作为第一枚举,然后再在枚举之间二次枚举子树覆盖需求(放在堆里,贪心配对即可)。

继续阅读「NOIp 2012 疫情控制」题解

「牛客 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 解题报告