[BZOJ3895]取石子

2021/12/23 23:10:09

本文主要是介绍[BZOJ3895]取石子,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

取石子

题解

在笔者写这篇题解之前,你可以发现,网上大部分流行的解法都是 O ( n ∑ a ) O\left(n\sum a\right) O(n∑a)的,但我们可以发现在 LOJ 的较快代码都是清一色的线性时间复杂度。
这篇题解将主要对这种线性的做法进行讲解。

首先我们抬出我们的结论:
我们记 x = ∑ [ a i = 1 ] x=\sum [a_i=1] x=∑[ai​=1]即 1 1 1堆的个数, y = ∑ [ a i > 1 ] ( a i + 1 ) − 1 y=\sum [a_i>1](a_i+1)-1 y=∑[ai​>1](ai​+1)−1,也就是非 1 1 1堆的和。
当 y ⩽ 2 y\leqslant 2 y⩽2时,如果 3 ∣ x 3|x 3∣x,后手必胜,否则先手必胜。
当 y > 2 y>2 y>2时,如果 2 ∣ x ∧ 2 ∣ y 2|x\wedge2|y 2∣x∧2∣y,后手必胜,否则先手必胜。

显然,不是 1 1 1的堆是不会对我们的答案产生影响的,它一定会做到最终被减到 0 0 0并且完全合(即自身合并的次数一定被用光)。
事实上,它不可能被任何一个人减到 0 0 0,如果有人妄图将它减到 0 0 0,浪费它的合并次数,那么当他将它从 2 2 2变到 1 1 1,是另一个人就会处于干扰对手的意愿,将其合并到它大于 1 1 1的朋友上,这也可以说明我们 y y y中最后要减去一个没处合并的 1 1 1。

显然,如果 y ⩽ 2 y\leqslant 2 y⩽2,那么我们的序列必然是数个连续的 1 1 1,最后可能跟一个 2 2 2。
如果我们的 3 ∣ x 3|x 3∣x,也就是说我们的 1 1 1的个数是 3 3 3的倍数。
如果我们的先手将一个 1 1 1变为 0 0 0,在有 2 2 2的情况下,后手可以将 2 2 2变成 1 1 1,在没 2 2 2的情况下,后手可以将两个 1 1 1变成 2 2 2。
如果先手将一个 2 2 2变成 1 1 1,后手将这个 1 1 1变成 0 0 0即可。
如果先手合并了两个 1 1 1,得到一个 2 2 2,那么在没 2 2 2的情况下,我们可以将一个 1 1 1消去,保持在原状态。
在有 2 2 2的情况,我们考虑现在 x x x的奇偶性没变, y y y的奇偶性变了,显然现在 2 ∤ y 2\not | y 2​∣y,因为现在它们多了一个可合并项,在 y > 2 y>2 y>2的情况看来,我们的后手现在是胜态。
于是,我们的目的有转到了证明 y > 2 y>2 y>2部分的结论是否成立,不妨先假设 y > 2 y>2 y>2部分的结论时对的,在下面会进行证明,先将 y ⩽ 2 y\leqslant 2 y⩽2的情况说明完。
如果我们的 3 ∤ x 3\not | x 3​∣x,那么显然我们的先手可以将现在的情况变为 3 ∣ x 3|x 3∣x,此时他是后手,可以胜利。
如果 x % 3 = 1 x\%3=1 x%3=1,直接将这个 1 1 1减掉即可。
如果 x % 3 = 2 x\%3=2 x%3=2,在有 2 2 2的情况下,可以将 2 2 2变成 1 1 1,没 2 2 2的情况下,将这两个 1 1 1合成 2 2 2。
于是我们便达到了 3 ∣ x 3|x 3∣x的情况,原来的先手现在成了后手,必将胜利。

对于 y > 2 y>2 y>2的情况,我们先说明 2 ∣ x ∧ 2 ∣ y 2|x\wedge 2|y 2∣x∧2∣y的情况后手是必胜的。
如果先手消一个 1 1 1,后手跟着消 1 1 1即可。
如果先手使 y y y减 1 1 1,如果现在 y > 3 y>3 y>3,后手让 y y y减 1 1 1即可。否则,如果前面有 1 1 1的话,一定是偶数个,我们合并两个 1 1 1,可以使 y y y变成 6 6 6。不然的话,整个序列中就一个 3 3 3,此时将这个 3 3 3变成 2 2 2,一个 2 2 2明显是后手必胜。
如果先手将一个 1 1 1合并到 2 2 2上,后手跟着合并一个 1 1 1即可。
如果先手将两个 1 1 1合成 2 2 2,此时 y y y会增加 3 3 3,后手使 y y y减 1 1 1即可。
这样,无论如何,我们的后手都有能与先手匹敌的方案。
如果 2 ∤ x ∨ 2 ∤ y 2\not |x\vee 2\not |y 2​∣x∨2​∣y,先手是一定有一种方案使其变成 2 ∣ x ∧ 2 ∣ y 2|x\wedge 2|y 2∣x∧2∣y的,此时作为后手的原来的先手胜利。
如果 2 ∤ x ∧ 2 ∣ y 2\not | x\wedge 2|y 2​∣x∧2∣y,先手可以直接消去一个 1 1 1。
如果 2 ∣ x ∧ 2 ∤ y 2| x\wedge 2\not |y 2∣x∧2​∣y,当 y > 3 y>3 y>3时,先手可以将 y y y减去一个 1 1 1,当 y = 3 y=3 y=3时,先手如果前面有 1 1 1就合并连个 1 1 1,否则将 y y y减 1 1 1。
如果 2 ∤ x ∧ 2 ∤ y 2\not |x\wedge 2\not | y 2​∣x∧2​∣y,先手可以将一个 1 1 1合并到 2 2 2上面去。
于是,无论如何先手都能赢了。
这样,我们就证罢了 y > 2 y>2 y>2的情况了,那么 y ⩽ 2 y\leqslant 2 y⩽2的情况也就证明完毕了。

于是,我们直接记录 1 1 1的个数与非 1 1 1的数的总和就可以线性求出答案了。
时间复杂度 O ( n ) O\left(n\right) O(n)。

源码

这还要看吗。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 50055
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
const int INF=0x3f3f3f3f;    
const int mo=998244353;
const int inv2=499122177;
const int jzm=233333333;
const int zero=100;
const int lim=200;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int T,n,a[MAXN],sum,num;
signed main(){
	read(T);
	while(T--){
		read(n);num=sum=0;
		for(int i=1;i<=n;i++){
			read(a[i]);
			if(a[i]>1)sum+=a[i]+1;
			else num++;
		}
		if(sum)sum--;
		puts(Dp(num,sum)?"YES":"NO");
	}
	return 0;
}

谢谢!!!



这篇关于[BZOJ3895]取石子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程