打卡信奥刷题（2975）用C++实现信奥题 P6015 [CSGRound3] 游戏

P6015 [CSGRound3] 游戏

题目背景

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

题目描述

有一个牌堆，一共有nnn张牌，第iii张牌上有一个数aia_iai​，其中第一张牌是堆顶。

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

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

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

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

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

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

输入格式

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

第二行nnn个整数a1…na_{1\dots n}a1…n​，表示每张牌上写的数。

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

输出格式

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

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

输入输出样例 #1

输入 #1

5 1 4 3 2 2 5

输出 #1

3 1 2 3

说明/提示

【样例解释】

X=1,2,3X=1,2,3X=1,2,3时，小 Z 取一张牌，小 Y 不管怎么取都是零分。

X=4X=4X=4时，小 Z 如果取111张，那么小 Y 取111张小 Y 就赢了；否则小 Z 只能是零分。

X=5X=5X=5时，小 Z 如果取111张，那么小 Y 取111张小 Y 就赢了；小 Z 如果取了222张，小 Y 也取222张，平局；否则小 Z 只能是零分。

【数据范围】

本题采用捆绑测试。

• Subtask 1（3 points）：n=1n = 1n=1。
• Subtask 2（14 points）：K=1K= 1K=1。
• Subtask 3（20 points）：n,K≤100n,K \le 100n,K≤100。
• Subtask 4（33 points）：n,K≤3333n , K \le 3333n,K≤3333。
• Subtask 5（30 points）：无特殊限制。

对于100%100\%100%的数据，1≤n,K≤1061\leq n,K \leq 10^61≤n,K≤106，1≤ai≤K1\leq a_i \leq K1≤ai​≤K。

C++实现

#include<iostream>usingnamespacestd;longlonga[1000005],res[1000005];intmain(){ios::sync_with_stdio(false);intn,k,ans=0;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];}cin>>k;for(inti=1;i<=n;i++){if(a[i]>=k)break;intp=lower_bound(a+1,a+n+1,2*a[i])-a;if(p==n+1||a[p]-a[i]>k){res[a[i]]++;res[k+1]--;break;}res[a[i]]++;res[a[p]-a[i]]--;}for(inti=1;i<=k;i++){res[i]+=res[i-1];if(res[i])ans++;}cout<<ans<<endl;for(inti=1;i<=k;i++)if(res[i])cout<<i<<' ';return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容