CF1033G 题解_C_内存溢出

CF1033G 题目传送门

题意

题解

考虑先手胜利的情况：

1. 先手

2. 后手

推导范围

AC Code

题意

有堆棋子，W 和 L 轮流取，W 每次只能取个，L 每次只能取个。

问，对于所有满足且的，假设 W 和 L 都绝对聪明，分别有几种方案满足如下四种情况。

- W win
- L win
- 先手 win
- 后手 win

题解 1.

~~因为只有 W 真的是人win，所以答案是。~~

~~做完了。~~

对于 :

- W win: 拿的必胜
- L win: 拿的必胜
- 先手 win：谁先手谁胜
- 后手 win：谁后手谁胜

显然四种情况是不会有重叠的，容易发现 W win 和 L win 的情况是等价的。

那么其实只要考虑先手必胜和后手必胜的方案数，然后就能求出所有答案。

的局面等价于的局面。

好像可以解释成，分成了两个子游戏，因为这两个游戏的赢家先后手不变，所以其中有一个是，那么总的异或和不为。

那么我们的就会减小到以内了。

草，叫起来太麻烦了……还是 A 每次拿
，B 每次拿罢（。

我们现在只考虑先手胜还是后手胜的问题，所以我们不妨设 A 小，B 大（也就是）
1. 情况1：废点。

不用管。

2. 情况2： A 可拿次，B 拿不了。

3. 情况3： A 可拿次，B 拿次。

4. 情况4： A 可拿次，B 拿次。

我们注意到每堆最多被一个人拿。

分类讨论。

被括起来的是必胜者。

（A）存在情况 2。

不存在情况 2

（A）情况个数：那么，第一轮里， A 肯定可以和 B 抢到一个情况 4，将它转化为情况 2。

1. 情况 4 个数

2 .情况 3 和情况 4 个数( )为奇数。

（A）A 是先手

（B）B 是先手

3. （A）情况 3 和情况 4 个数 () 为偶数。

不存在情况 4。

1. 情况 3 个数 () 是奇数

（A）A 是先手

（B）B 是先手

2. 情况 3 个数 () 是偶数
（B）A 是先手

（A）B 是先手

整合一下。

只要考虑先手必胜和后手必胜的。

不存在情况 2

情况 4 个数。

（先）为奇数

不存在情况 4。

>> （先）：情况 3 个数 () 是奇数

>> （后）：情况 3 个数 () 是偶数

那么我们就可以暴力枚举了。

然鹅

过不去。

。

4. 考虑胜利的情况：

先手胜利的情况

不存在

并且为奇数。

后手胜利的情况：
- 不存在
- 并且为偶数。

首先枚举

对进行排序。

要求就处于一个的区间内。

枚举是哪个区间。

（边界区间也要考虑）

然后的奇偶性就可知了。

分别考虑先手胜和后手胜的情况。

设最大的是，次大的是。

1. 先手

即：v_{n-1}" src="https://latex.codecogs.com/gif.latex?%5Cmax%282a%2Cb%29%3Ev_%7Bn-1%7D" />
即：必须满足 \tfrac{n_v-1}{2}" src="https://latex.codecogs.com/gif.latex?a%3E%20%5Ctfrac%7Bn_v-1%7D%7B2%7D" />和 v_{n-1}" src="https://latex.codecogs.com/gif.latex?b%3Ev_%7Bn-1%7D" /> 中至少一个。
看起来这个玩意儿需要容斥。

但是实际上不用。
因为在一个区间里，所以 v_{n-1}" src="https://latex.codecogs.com/gif.latex?b%3Ev_%7Bn-1%7D" /> 的时候一定大于 \tfrac{n_v-1}{2}" src="https://latex.codecogs.com/gif.latex?v_%7Bn-1%7D%3E%5Ctfrac%7Bn_v-1%7D%7B2%7D" />。

所以只需要计算 \tfrac{n_v-1}{2}" src="https://latex.codecogs.com/gif.latex?a%3E%5Ctfrac%7Bn_v-1%7D%7B2%7D" /> 的情况。

2. 后手

即：v_n" src="https://latex.codecogs.com/gif.latex?%5Cmax%282a%2Cb%29%3Ev_n" />
即：\tfrac{n_v}{2}" src="https://latex.codecogs.com/gif.latex?a%3E%5Ctfrac%7Bn_v%7D%7B2%7D" /> 或 v_n" src="https://latex.codecogs.com/gif.latex?b%3Ev_n" /> 同理。
因为在一个区间里，所以 v_n" src="https://latex.codecogs.com/gif.latex?b%3Ev_n" /> 的时候一定大于 \tfrac{n_v-1}{2}" src="https://latex.codecogs.com/gif.latex?v_n%3E%5Ctfrac%7Bn_v-1%7D%7B2%7D" />。

所以只需要计算 \tfrac{n_v}{2}" src="https://latex.codecogs.com/gif.latex?a%3E%5Ctfrac%7Bn_v%7D%7B2%7D" /> 的情况。

推导范围

那么我们最后会框出一个的范围，然后

l=max(v[j]%s,mx/2)+1,r=min(v[j+1]%s,m);

注意到我们开始有个设定叫，现在我们想抛弃它，否则会很难写。

那么就是

也就是

那么最终的范围就是

AC Code

#include
using namespace std;
typedef long long ll;
#define ls(x)((x)<<1)
#define rs(x)((x)<<1|1)
#define fi first
#define se second
#define mkp make_pair
#define PII pair
const int N=110,M=2e5+10;
int n,m,tmp[N];
ll v[N],ans,ansf,anss;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(int s=2;s<=(m<<1);s++)
    {
        tmp[0]=0;tmp[n+1]=s-1;
        for(int i=1;i<=n;i++)
            tmp[i]=v[i]%s;
        sort(tmp,tmp+(n+1)+1);
        for(int i=1;i<=n+1;i++)
        {
            //a,b在 [tmp[i-1],tmp[i]]之间。


            //fl: >=b 的个数是否为奇数。


            bool fl=(n+1-i)&1;
            int l=max(tmp[i-1],tmp[n-1+(!fl)]/2)+1,r=min(tmp[i],m);
            //是奇数：可能后手必败（先手必胜）。

找次大
            //是偶数：可能先手必败（后手必胜）。

找最大
            (fl?ansf:anss)+=max(0,min(r,s-l)-max(l,s-r)+1);
        }
    }
    ans = (1ll*m*m-ansf-anss)>>1;
    printf("%lld %lld %lld %lld\n",ans,ans,ansf,anss);
    return 0;
}

啊啊啊，一晚上的时间都耗在此题上了，中间上了厕所回来发现有个小可爱把我题解删了，亏了可以`Ctrl+Z`，不然我会气吐血的……

最后感谢老师细心地解答/纠正一些离大谱的问题/bx

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/564714.html