题目相关
题目链接: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次的值之和某些值有关,即可能存在相消。
所以我们尝试打个表来看看。
似乎并没有什么规律我们从中挑出几行再看:
结论:当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,这样运算会简便很多。
蒟蒻代码
1 |
|