avatar

目录
洛谷 P4405 [ZJOI2009]硬币游戏

题目相关

题目链接:P4405 [ZOOI2009]硬币游戏

题目描述:

  Orez很喜欢玩游戏,他最近发明了一款硬币游戏。他在桌子的边缘上划分出2*n个位置并按顺时针把它们标号为1,2,……,2n,然后把n个硬币放在标号为奇数的位置上。
  接下来每次按如下操作:在任意两个硬币之间放上一个硬币,然后将原来的硬币拿走;所放硬币的正反面由它两边的两个硬币决定,若两个硬币均为正面朝上或反面朝上,则所放硬币为正面朝上,否则为反面朝上。 那么操作T次之后桌子边缘上硬币的情况会是怎样的呢?

输入输出格式:

输入格式:
  文件的第一行包含两个整数n和T。
  接下的一行包含n个整数,表示最开始桌面边缘的硬币摆放情况,第i个整数ai表示第i个硬币摆放在2*i-1个位置上,ai=1表示正面朝上,ai=2表示反面朝上。

输出格式:
  文件仅包含一行,为2n个整数,其中第i个整数bi桌面边缘的第i个位置上硬币的情况,bi=1表示正面朝上,bi=2表示反面朝上,bi=0表示没有硬币。

输入输出样例:

输入样例#1:
10 5
2 2 2 1 1 1 1 1 1 2
输出样例#1:
0 1 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1

说明:

30%的数据:n≤1000,T≤1000
100%的数据:n≤100000,T≤$2^{60}$

样例解释:

20202010101010101020
01010201010101010201
10102020101010102020
01020102010101020102
20202020201010202020
01010101020102010101



博主乱搞

首先我们知道这是个圆桌否则没法做

蒟蒻解析:

  首先说明这是个圆桌

对于30%的数据:

  对于ZJ来说能有30分暴力分非常不容易。
  应该是一个模拟题(博主没有尝试)。不想解释也没有代码。

对于100%的数据:

  从2^60我们大概能看出这地方需要一个log级别算法。但是哪里用的到?
  关于正反硬币的问题,我们可以用亦或来代替,也就是正面0反面1(空的-1就行了)。可以进行如下操作:

情况1 公式1 情况2 公式2
初始 左右相同 1^1/0^0 左右不同 1^0/0^1
结果 正面 0 反面 1

  这样就能用亦或表达正反面及翻面情况,这对做题有什么帮助呢?
  我们知道a^b^b=a,所以可能玩了T次的值之和某些值有关,即可能存在相消。
  所以我们尝试打个表来看看。

图1

  似乎并没有什么规律我们从中挑出几行再看:

图1

结论:当T=2^k(k∈N*)时,第n枚硬币(在2n-1位置)的状态仅由n-k,n+k枚硬币的状态决定。(超出部分进入循环)

  这样就不必拘泥于暴力模拟,可以省去很多步骤。2^k的思想同快速幂相吻合,这样本题就可以解决。

判断T&2^k是否非0,若非0则进行2^k次转换,也就是每个元素与其相关联的两个元素进行计算。

答疑时间

如果是奇数怎么办?

答:整体再翻一次。

超出部分处理太复杂怎么办?

答:我们可以把硬币A1到An转变为A0到An-1,这样运算会简便很多。

蒟蒻代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=100010;
int a[2][maxn*2],k=0;
ll m[70];
int n,re,p; ll t;
int gp(int x){
return 2*x;
}
void work(int j){
ll d=m[j-1]; k^=1;
for (int i=0;i<n;++i){
a[k][gp(i)]=a[k^1][gp(((i-d)%n+n)%n)]^a[k^1][gp(((i+d)%n+n)%n)];
}
}
int main(){
memset(a,-1,sizeof(a));
scanf("%d%lld",&n,&t);
for (int i=0;i<n;++i){
scanf("%d",&re);
a[0][gp(i)]=re-1;
}
m[0]=1;
while (m[p]<t){
++p; m[p]=m[p-1]*2;
}
for (int j=p;j>=1;--j){
if (m[j]&t) work(j);
}
if (t&m[0]){
k^=1;
for (int i=0;i<n;++i)
a[k][gp(i)+1]=a[k^1][gp(i)]^a[k^1][gp((i+1)%n)];
for (int i=0;i<n;++i)
printf("0 %d ",a[k][gp(i)+1]+1);
}else{
for (int i=0;i<n;++i)
printf("%d 0 ",a[k][gp(i)]+1);
}
return 0;
}
文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2019/07/02/luoguP4405/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog

评论