不得不表示，能用棧來做的題目前對我來說都很費解，這題又是抄的，來自校友JMDWQ，只不過把C改成了C++。開始時我用的是暴搜，數組的每一位就是一個“魂器”，而他的棧結構里每一位是連續相同的“魂器”的長度，明顯要好的多。對他的核心代碼，我的理解是這樣的，大牛勿噴：

判斷當前與前一位 相同：棧頂++；（當前連續區長度+1）

　　　　　　　　 不同：不能變化 ｜｜ top==0：　　 s[++top] = 1；（開辟新區，長度為1）

　　　　　　　　　　　　 能變化? &&? top（存在區）：只有一個區：棧頂++（長度+1）；t = !t（最左邊的區變了）;

　　　　　　　　　　　　　　　　　　　　　　　　　　存在多個區：s[top-1] += s[top]+1；top－－；（合并區）；

現在舉一個最后一種情況的例子：00110001，當前到最后一個，“1”，不同，可以變化，之前有三個區，s[1]＝＝2，s[2]＝＝2，s[3]＝＝3，區3里的3個0都變為1，加上的當前的1（可以理解為區4），全都合并的區2里了，s[2] += s[3]+1；top－－就是少一個區嘛。

最后不得不說代碼中t的安排，真是巧妙。所有的區是0、1、0、1間隔的，t變化表示最左邊的區變了，后來的top%2==t是用來判斷當前也就是最后一個區是0還是1；本來我還是搞不清，后來看到t=f（第一個數），我覺悟了，原來t 一開始就是最左邊的，它是0 t也是0，它是1 t也是1；然后它變t也變，完全一樣嘛！t與top各2種情況，一共4種，枚舉一下就發現這樣會保證top指向0，真是妙，以后我也這樣判斷。

1 #include<iostream> 2 using namespace std; 3 const int MAXN = 100010; 4 unsigned short s[MAXN]; 5 int main() 6 { 7 int t,f,top,ans,i,n,x; 8 while(cin>>n) 9 { 10 top = ans = 0; 11 memset(s,0,sizeof(s)); 12 cin>>f; 13 t = f; 14 s[++top] = 1; 15 for(i = 1; i < n; i++) 16 { 17 cin>>x; 18 if(f!=x) 19 { 20 f = x; 21 if(i%2 && top) 22 if(top > 1) 23 s[top-1] += s[top]+1,top--; 24 else 25 s[top]++,t = !t; 26 else s[++top] = 1; 27 } 28 else s[top]++; 29 } 30 if(top%2 == t) top--; 31 while(top > 0) 32 { 33 ans += s[top]; 34 top -= 2; 35 } 36 cout<<ans<<endl; 37 } 38 return 0; 39 }

?

轉載于:https://www.cnblogs.com/lzxskjo/archive/2012/04/14/2446840.html

總結

以上是生活随笔為你收集整理的csu 1008 - Horcrux的全部內容，希望文章能夠幫你解決所遇到的問題。

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