Category Archives

418 Articles

OI

AtCoder Grand Contest 035 – 解题报告

Posted by kal0rona on

A – XOR Circle

考虑对仅有的 \(s \leq 3\) 个元素排列顺序然后判就完事了。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ai[MAX_N], si[MAX_N];
map<int, int> mp, tmp;

int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
        scanf("%d", &ai[i]), mp[ai[i]]++;
    if (mp.size() <= 3)
    {
        vector<int> vi;
        for (auto x : mp)
            vi.push_back(x.first);
        bool flag = false;
        do
        {
            int len = vi.size();
            tmp.clear();
            for (int i = 1; i <= 2; i++)
                si[i] = vi[(i - 1) % len];
            for (int i = 3; i <= n; i++)
                si[i] = si[i - 1] ^ si[i - 2];
            for (int i = 1; i <= n; i++)
                tmp[si[i]]++;
            bool cflag = true;
            for (auto x : tmp)
                cflag &= mp[x.first] == x.second;
            flag |= cflag;
        } while (next_permutation(vi.begin(), vi.end()));
        puts(flag ? "Yes" : "No");
    }
    else
        puts("No");
    return 0;
}
OI

「Codeforces 662A」Gambling Nim – 题解

Posted by kal0rona on

主要思路

考虑设 \(S = \oplus_{i = 1}^n a_i\),然后将 \(c_i = a_i \oplus b_i\) 扔到线性基里面。我们可以发现,线性基最少数来拼出一个和 \(S\) 一样的数使得局面必输。那么,赢得概率就是 \(1 – (\frac12)^{siz}\)。

当然,如果拼不出来,那么就稳赢了。

OI

BZOJ3590:[SNOI2013]Quare – 题解

Posted by kal0rona on

主要思路

我操这个题是真的有意思(做完后索然无味)。

肯定这个题状压 DP 没跑的,所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难,我们需要思考一个归纳的方式来构造一个双连通图。