DDOSvoid's Blog

CF 768E Game of Stones

发表于 分类于
本文字数： 571 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/768/E

Solution

注意到如果我们每次都拿最少的直到不能拿为止，那么我们能够得到一堆石子的最多操作次数

然后我们能够注意到一到这些步都能做到，那么它的 $sg$ 就是最多操作次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long 
using namespace std;

int n, m; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ll x, v; cin >> x;
        v = sqrt(x * 2);
        if (x >= v * (v + 1) / 2) ans ^= v;
        else ans ^= v - 1; 
    }
    cout << (ans ? "NO" : "YES") << "\n";
    return 0;
}