CF1404D题解

· · 题解

题解思路：

当 n 是偶数先手必胜。

当 n 是奇数后手必胜。

我们来证明一下：

  1. >既然 $n$ 是偶数，那么先手有一个构造方案： >> 把 $\mod n$ 相等的数放在一起，例如：$(1 , 1) , (1 , n + 1)$。

所以后手拿的数只有 1 + ... + n。 他就是 (1 + n) \times n \div 2，对于这个值，那么为什么他一定不是 2n 的倍数呢？

n = 2m

因为 n 是偶数，而 n + 1 就是个奇数，那这个数是不是 n 的倍数呢？

我们考虑一下：

因为 n = 2m 所以原式就变成了：(2m + 1) \times m。

那么我们想让 (2m + 1) \times m 是 n 的倍数，那么我们要有个 2，但由于 2m + 1 一定是奇数，所以他一定不是 n 的倍数。\ 因为他不是 n 的倍数，那他就不可能是 2n 的倍数了。

证毕。

那么为什么 n 是偶数时后手必败呢？我们只要证明当 n 是奇数时后手必胜就可以了。

  1. 当 n 为奇数时后手必胜

    首先我们证明一个性质：

    (2n + 1) \times n \mod 2n = n

因为他乘了奇数倍，所以他 \mod 2n 一定是 n，因为它比奇数倍还多了一个 n。

若我们选 n 个数，定义 sum 为选的 n 个数的和。那么 sum \mod n = 0。

那么我们有两种情况 sum \mod 2n = n，sum \mod 2n = 0。

若 sum \mod 2n = 0，那么我们就是答案；若 sum \mod 2n = n，那么另外 n 个数就是答案。

那么只要 \mod n = 0\ 1\ 2\ ......\ n - 1 的数各有两个，那么我不管怎么塞，我们去出来这 n - 1 个数。

注意：奇数的情况时要fflush(stdout)，不然会Idleness limit exceeded on test 3，洛谷显示UKE

AC记录

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1000010;
typedef long long ll; 
int n;
int a[N];
bool vis[N] , vis2[N] , vis3[N];
vector <int> e[N];
vector <int> g[N];
int main() {
    scanf ("%d" , &n);
    if (n & 1) {//奇数的情况 
        puts("Second");
        fflush(stdout);
        for (int i = 1; i <= n * 2; ++ i) {
            scanf ("%d" , &a[i]);//读入 
            e[i % n].push_back (a[i]);
            g[a[i]].push_back (i);
        }
        for (int i = 1; i <= n * 2; ++ i) {
            int root = i % n;
            if (vis[root]) continue; 
            int u = i;
            while (1) {
                vis[u % n] = vis2[u] = 1;//把他标记上 
                int v = -1;
                for (auto x : g[a[u]])
                    if (!vis[x % n])
                        v = x;
                if (v == -1) break;
                if (v > n) v -= n;//>n 就 -n 
                else v += n;//否则加上n 
                u = v;
            }
        }
        ll ans = 0;
        for (int i = 1; i <= n << 1; ++ i) 
            if (vis2[i]) //统计他们的和 
                ans += i;
        if (ans & 1) {//sum % 2n == n
            bool ok = false;//控制空格，避免后面多输出一个空格，当然加不加都无所谓 
            for (int i = 1; i <= n << 1; ++ i) 
                if (!vis2[i]) {//那么另外的那些就是答案 
                    if (ok) printf (" ");
                    printf ("%d" , i);
                    ok = true;
                }
            puts("");
        }else {//否则 sum % 2n == 0 
            bool ok = false;//ok含义同上 
            for (int i = 1; i <= n << 1; ++ i)
                if (vis2[i]) {//那么就是原来的数 
                    if (ok) printf (" ");
                    printf ("%d" , i);
                    ok = true;
                }
            puts("");
        } 
    }else {
        puts ("First");//偶数的情况，先手必胜 
        for (int i = 1; i <= n << 1; ++ i) {//直接输出 
            printf ("%d" , i % n + 1);//把两个同余的放在一块 
            if (i == n << 1) puts("");
            else printf (" ");
        } 
    }
    return 0;
}

码字不易，求赞！