題目：

一個循環(huán)序列，其中有若干0和1，兩個間隔為1（即間隔一個數(shù)）的數(shù)的位置可以互換。問題是，給定一個這樣的隊列，判斷是否可以將所有的0和1分別歸攏到一起，即可以將此循環(huán)序列切斷為兩個序列，一個里面只有1，一個里面只有0.

思考：

題目不難，剛開始沒有發(fā)現(xiàn)公式，考慮到的情況少了，所以wa了，后來考慮到所有情況，并總結了公式，就ac了。

證明：

引理1：相鄰的兩個數(shù)只有10,01,11,00 四種情況，其中00，11這兩種情況對于整個循環(huán)序列沒有影響。

證明：若存在11或00這兩種組合，顯然，通過在不同位置上執(zhí)行數(shù)字互換操作（題目里所提），這種組合可以被移動到循環(huán)序列的任意指定位置。因此，當循環(huán)序列里面只有11和00時，我們可以非常簡單地移動所有11（或00），讓它們相連，這樣循環(huán)序列就可以分成兩個全0和全1的子序列。所以，11和00的存在不影響最終結果。

題目證明

1.如果循環(huán)序列的長度是奇數(shù)，那么此循環(huán)序列一定可以切斷為兩個序列，一個里面只有1，一個里面只有0.

證明：如果長度是奇數(shù)，那么一定有偶數(shù)個1+奇數(shù)個0，或者偶數(shù)個0+奇數(shù)個1.如果1和0的個數(shù)不相等，那么一定有11或00這種情況存在，因為n個0或1無法將n+1個1或0分開（注意，是循環(huán)序列，頭和尾之間也需要插入數(shù)字分開）。又因為引理1，所以存在的00和11可以被消去，即不考慮，那么剩下的循環(huán)序列長度還是奇數(shù)，因此還存在00或11。這樣一直消去，直到長度為1，長度為1的循環(huán)序列是一定滿足要求的。

2.如果循環(huán)序列的長度是偶數(shù)，若0或1在偶數(shù)位上的數(shù)目與在奇數(shù)位上的數(shù)目之差小于等于1，那么此循環(huán)序列一定可以切斷為兩個序列，一個里面只有1，一個里面只有0.

證明：如果長度是偶數(shù)，假設里面有m個01，n個10（剩下的00和11根據(jù)引理1可以不考慮）。如果一個10和一個01相鄰，則可以通過換位操作將1001變成1100。若m和n相等，則最后經過消去，沒有數(shù)字剩下，因此這是個循環(huán)序列；若有m和n相差1，則最后經過消去，只剩下一個01或10，這也是一個循環(huán)序列；若m和n相差大于1，則剩下k個10或01，k>=2，例如：1010,這不是一個循環(huán)序列。所以，只有m和n的差小于等于1時，循環(huán)序列才滿足題目要求。不失一般性地，設10中的1處于奇數(shù)位，01中的1處于偶數(shù)為，則只有在偶數(shù)位上的數(shù)目與在奇數(shù)位上的數(shù)目之差小于等于1時，才滿足題目要求。

?

3.代碼

1 #include<stdio.h> 2 #include<math.h> 3 int main() 4 { 5 int d[30],n,c; 6 scanf("%d",&n); 7 while(n>0) 8 { 9 int ow=0,ew=0; 10 scanf("%d",&c); 11 for(int i=0;i<c;i++) 12 scanf("%d",&d[i]); 13 if(c%2==1) 14 printf("YES\n"); 15 else 16 { 17 for(int i=0;i<c;i++) 18 { 19 if(d[i]==0) 20 { 21 if(i%2==0) 22 ow++; 23 else 24 ew++; 25 } 26 } 27 if(abs(ow-ew)<2) 28 printf("YES\n"); 29 else 30 printf("NO\n"); 31 } 32 n--; 33 } 34 return 0; 35 }

?

?

轉載于:https://www.cnblogs.com/hrlnw/archive/2013/01/17/2865509.html

總結

以上是生活随笔為你收集整理的poj1063 解题报告（poj 1063 analysis report）的全部內容，希望文章能夠幫你解決所遇到的問題。

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