洛谷P6015 [CSGRound3]游戏 题解

题目链接：P6015 [CSGRound3]游戏

题意：

小 Y 和小 Z 是一对好朋友，他们在玩一个游戏。游戏只有一个回合。

有一个牌堆，一共有 $n$ 张牌，第 $i$ 张牌上有一个数 $a_i$，其中第一张牌是堆顶。

小 Z 先取牌，他可以从堆顶开始取连续若干张牌（可以取 $0$ 张），取完的牌拿在手上，也就是不在牌堆里了。

然后小 Y 取牌，同样，她也可以从堆顶开始取连续若干张牌（可以取 $0$ 张）。

如果一个人手上的牌的数字和大于 $X$，那么他的分数就是 $0$，否则分数就是数字和。

分数高的人获胜，如果一样高，则无人获胜。

小 Z 为了获胜，使用了透视挂，即他知道牌堆里每张牌上写的数。

现在问你对于满足 $1 \leq X \leq K$ 的所有整数 $X$，哪些可以使得小 Z 有必胜策略，即小 Z 取完后，不管小 Y 怎么取都一定会输。

输入格式：

第一行一个整数 $n$，表示牌堆里有几张牌。

第二行 $n$ 个整数 $a_{1\dots n}$，表示每张牌上写的数。

第三行一个正整数 $K$，含义见题目描述。

输出格式：

第一行一个整数，表示满足要求的 $X$ 的个数。

第二行从小到大依次输出满足要求的 $X$，用空格隔开。

数据范围：

对于 $100\%$ 的数据，$1\leq n,K \leq 10^6$，$1\leq a_i \leq K$。

记 $S_i = \sum _{ j = 1} ^ {i} a_j$ ，$p$ 为所有满足 $S_p - S_i \ge S_i$ 的正整数中最小的一个。

则所有 $X \in \left[S_i, ~S_p - S_i\right)$ 均必胜。则最终答案为所有区间的并。

显然 $p$ 单调不降，因此我们可以以双指针的形式维护它。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

vector<int> vec;
int n,k,p,X[N * 2 + 15],sum[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) { cin >> sum[i], sum[i] += sum[i - 1]; }
    cin >> k;
    for(int i = 0; i <= n; i++)
    {
        if(sum[i] > k) break;
        for(; p <= n && sum[p] < sum[i] * 2; ++p) {;}
        ++X[sum[i]]; if(p <= n) --X[sum[p] - sum[i]];
    }
    for(int i = 1; i <= k; i++) {
        if(X[i] += X[i - 1]) vec.emplace_back(i);
    }
    cout << vec.size() << '\n'; for(auto i : vec) cout << i << ' ';
    return 0;
}