1411: [ZJOI2009]硬幣游戲

Time Limit: 10 Sec??Memory Limit: 162 MB
Submit: 897??Solved: 394
[Submit][Status][Discuss]

Description

Orez很喜歡玩游戲，他最近發明了一款硬幣游戲。他在桌子的邊緣上劃分出2*n個位置并按順時針把它們標號為1，2，……，2n，然后把n個硬幣放在標號為奇數的位置上。接下來每次按如下操作：在任意兩個硬幣之間放上一個硬幣，然后將原來的硬幣拿走；所放硬幣的正反面由它兩邊的兩個硬幣決定，若兩個硬幣均為正面朝上或反面朝上，則所放硬幣為正面朝上，否則為反面朝上。 那么操作T次之后桌子邊緣上硬幣的情況會是怎樣的呢？

Input

文件的第一行包含兩個整數n和T。 接下的一行包含n個整數，表示最開始桌面邊緣的硬幣擺放情況，第i個整數ai表示第i個硬幣擺放在2*i-1個位置上，ai=1表示正面朝上，ai=2表示反面朝上。

Output

文件僅包含一行，為2n個整數，其中第i個整數bi桌面邊緣的第i個位置上硬幣的情況，bi=1表示正面朝上，bi=2表示反面朝上，bi=0表示沒有硬幣。

Sample Input

10 5
2 2 2 1 1 1 1 1 1 2

Sample Output

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

HINT

Source

題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=1411或者https://vijos.org/p/1554

題目大意：給定一圈硬幣，T次操作，每次操作在每個硬幣中間各放一枚硬幣，硬幣的正反面由它旁邊兩個決定，兩邊相同則為正面，兩邊不相同則為反面，然后將之前的硬幣全部撤掉，問T次操作后的硬幣序列，T<=2^60

?

首先我們令硬幣正面為0 反面為1 那么很容易發現新硬幣的值為兩邊硬幣的異或值 樣例也就很好解釋了

?

1-1-1-0-0-0-0-0-0-1- ? 0
-0-0-1-0-0-0-0-0-1-0 ? 1
0-0-1-1-0-0-0-0-1-1- ? 2
-0-1-0-1-0-0-0-1-0-1 ? 3
1-1-1-1-1-0-0-1-1-1- ? 4
-0-0-0-0-1-0-1-0-0-0 ? 5

?

然后這題n<=10W 矩陣乘法一定MLE 即使矩陣特殊構造可以干掉一維空間復雜度 O(n^2*logT)的時間也無法承受

?

我們只考慮偶數的行

?

易知第二行每個數是原序列該位置左右兩個數的異或

?

由數學歸納法可以 第2^k行每個數是原序列該位置左側第2^(k-1)個數和右側第2^(k-1)個數的異或

?

然后將T進行二進制拆分，每位進行一次變換即可 最后再討論T的奇偶

?

時間復雜度O(n*logT)

膜拜出題人，膜拜題解人，這TM也成，我服了！

下面給出AC代碼：

1 #include <bits/stdc++.h> 2 #define in freopen("coin.in","r",stdin); 3 #define out freopen("coin.out","w",stdout); 4 #define M 100100 5 using namespace std; 6 typedef long long ll; 7 ll n,T,tot; 8 char a[2][M],ans[M<<1]; 9 inline ll read() 10 { 11 ll x=0,f=1; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9') 14 { 15 if(ch=='-') 16 f=-1; 17 ch=getchar(); 18 } 19 while(ch>='0'&&ch<='9') 20 { 21 x=x*10+ch-'0'; 22 ch=getchar(); 23 } 24 return x*f; 25 } 26 int main() 27 { 28 ll i,j,x; 29 n=read(); 30 T=read(); 31 for(i=1;i<=n;i++) 32 { 33 x=read(); 34 a[0][i]=x-1; 35 } 36 for(j=2;j<=T;j<<=1) 37 { 38 if(T&j) 39 { 40 tot++; 41 for(i=1;i<=n;i++) 42 { 43 ll x1=(i+(j>>1)%n+n-1)%n+1; 44 ll y1=(i-(j>>1)%n+n-1)%n+1; 45 a[tot&1][i]=a[~tot&1][x1]^a[~tot&1][y1]; 46 } 47 } 48 } 49 for(i=1;i<=n;i++) 50 { 51 ans[i+i-1]=a[tot&1][i]; 52 } 53 if(T&1) 54 { 55 for(i=1;i<=n;i++) 56 { 57 ans[i<<1]=ans[i+i-1]^ans[i==n?1:i<<1|1]; 58 } 59 for(i=1;i<=n;i++) 60 { 61 ans[i+i-1]=-1; 62 } 63 } 64 else 65 { 66 for(i=1;i<=n;i++) 67 { 68 ans[i+i]=-1; 69 } 70 } 71 for(i=1;i<=n<<1;i++) 72 { 73 printf("%d%c",ans[i]+1,i==n+n?'\n':' '); 74 } 75 return 0; 76 }

以上方法我還是有點迷，下面換種寫法，

對于樣例，進行數學歸納，發現2^k變換之后，第i個位置的硬幣情況只與它左右的第k+1個硬幣有關。

如k=0,第3位硬幣情況只與2和4位硬幣有關。因為t可以拆成若干個2^k的和，于是對每個2^k進行O(n)的變換，總復雜度O(nlogt)。

1 #include <bits/stdc++.h> 2 #define in freopen("coin.in","r",stdin); 3 #define out freopen("coin.out","w",stdout); 4 typedef long long ll; 5 using namespace std; 6 inline ll read() 7 { 8 ll x=0,f=1; 9 char ch=getchar(); 10 while(ch<'0'||ch>'9') 11 { 12 if(ch=='-') 13 f=-1; 14 ch=getchar(); 15 } 16 while(ch>='0'&&ch<='9') 17 { 18 x=x*10+ch-'0'; 19 ch=getchar(); 20 } 21 return x*f; 22 } 23 const int N=200020; 24 ll n,t,a[N],b[N]; 25 ll f(ll b,ll k) 26 { 27 ll x=b-k; 28 ll y=b+k; 29 x=(x%(n<<1)+(n<<1)-1)%(n<<1)+1; 30 y=(y-1)%(n<<1)+1; 31 if(k==0) 32 return a[x]; 33 if(a[x]==0) 34 return 0; 35 if(a[x]==a[y]) 36 return 1; 37 else return 2; 38 } 39 void work(ll k,ll q) 40 { 41 if(k==0) 42 return; 43 work(k>>1,q<<1); 44 if(k%2==1) 45 { 46 memset(b,false,sizeof(b)); 47 for(ll j=1;j<=(n<<1);j++) 48 b[j]=f(j,q); 49 swap(a,b); 50 } 51 } 52 int main() 53 { 54 n=read(); 55 t=read(); 56 for(ll i=1;i<=n;i++) 57 a[(i<<1)-1]=read(); 58 work(t,1); 59 for(ll i=1;i<(n<<1);i++) 60 cout<<a[i]<<" "; 61 cout<<a[n<<1]<<endl; 62 return 0; 63 }

?

轉載于:https://www.cnblogs.com/ECJTUACM-873284962/p/7102510.html

總結

以上是生活随笔為你收集整理的BZOJ 1411Vijos 1544 : [ZJOI2009]硬币游戏【递推，快速幂】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。