阶段性总结：十月中

九月份的总结忘了写，然后拖到现在，不如改名叫阶段性总结算了。

从纪中回来之后学了两周的文化课，把九月份的东西大概提前猛的学了一下（最后发现数学和化学的速度超出了预期，有点吃亏，其他都上得差不多，联赛回来估计文化课就会炸的稀巴烂）。文化课凉了之后，因为自己太菜的缘故，lcx 就把我催回来学竞赛了。

回来学竞赛打了几场模拟赛，感觉手感要比在纪中好不少，至少不会去刷 Twitter 了；分数也上去了蛮多，但是不太稳定，主要源于心态，现在也慢慢的调节过来了（不过也没什么好调节的，mousezt 这种东西听着都想笑）。刷了一些套路题，也打了一些 CF 的题目，手感越来越好。但是有一些能被想到，细节很多的东西就基本上没辙了：关键还是搞不出来，也没有运用到一些算法的本质。接下来的主要重心还是在 USACO 的一些题还有历年的模拟赛题上吧，还有就是拓宽阅读的范围，稳定复习，温习基础。

这一个月多也反思了很多事情，感觉浪费了一年的光阴，学了很多脱离实际的东西。当然，我认为目前补救还是比较及时的，所以尽量把损失控制到最小吧。联赛好，那就继续快乐；联赛不好，就回17班快乐去，也不赖，毕竟除了语文，其他学起来都还是很开心的，语文虚心跟着陈小荣恶补一下，回到正常线上也比较可期（那也不一定，直面讨厌多年的东西对我而言仍是一件非常困难的事情）。

后悔没有跟一些神仙打好关系，也短视了单人训练的局限性；除此之外也花了几个月认识到了一些人奇怪的心态，也照出了我的心理缺点（fixed weeks ago）。

这一个月也感叹时间流逝之快：一年前 DOFY 和 lornd 还在跟我们讲课，到如今滨江机房的冷清，和青山湖校区的蓬勃。新高一挺好，希望他们也会越来越努力。唉，学长们都退役了，也都轮到我了。

各位 CSP 2019 再见，希望神仙可以最终都能得到自己心愿的成绩。

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\)打标记。

结合一下就可以了。

Continue reading →

「NOIp 2012 疫情控制」题解

主要思路

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

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

Continue reading →

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

Continue reading →

Protected: CSP-S 2019 复习

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;
}

Continue reading →