[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]取石子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用