1008: Horcrux
Time Limit: 1 Sec
Memory Limit: 128 MB
Submit: 447
Solved: 120
[
Submit][
Status][
Web Board]
Description
A Horcrux is an object in which a Dark wizard or witch has hidden a fragment of his or her soul for the purpose of attaining immortality. Constructing a Horcrux is considered Dark magic of the foulest, most evil kind, as it violates laws of nature and morality, and requires a horrific act (a.k.a. murder) to accomplish.
There are two kinds of horcruxes, the white one, denoted as △, and the black one, denoted as ▲. Topper has got N horcruxes, and he wants to destroy them to win the Dark wizard. Toper places all the horcruxes in a line from left to right, one by one, and then says a magic spell to destroy them. In order to make the magic spell works, Toper needs to know the number of the white horcruxes.
Since the horcruxes also has magic, when placing the horcruxes, they will change color from white to black or from black to white under the following rules:
1. When Topper places the i-th horcrux and i is an even number: If the i-th horcrux and the rightmost horcrux have different colors, all consecutive horcruxes of the same color on the right change its color.
2. In other situations, no magic works.
For example, suppose the horcruxes on the line are:
△△▲▲△△△
After placing 7 horcruxes.
If the 8-th horcrux is white, since its color and the color of the rightmost horcrux are the same. Therefore, the horcruxes on the line become as follows:
△△▲▲△△△△
If the 8-th horcrux is black, since its color and the color of the rightmost horcrux are different, the 3 consecutive white stones on the right change their color. Therefore, the stones on the line become as follows:
△△▲▲▲▲▲▲
You see, it’s not an easy job to beat the Dark wizard. So write a program to help Topper.
Input
There are some test cases. In each test case, the first line contains a positive integer n (1≤n≤100,000), which is the number of horcruxes. The following n lines denote the sequence in which Topper places the horcruxes. 0 stands for white horcrux, and 1 stands for black horcrux.
Output
For each test case, output one line containing only the number of white horcruxes on the line after Topper places n horcruxes.
Sample Input
8
1
0
1
1
0
0
0
0
8
1
0
1
1
0
0
0
1
Sample Output
6
2
HINT
Source
这道题一开始没写出来，自己写的有问题，我用的两个数组统计，结果统计来统计去都是错的，学习(抄)了别人的代码之后才发现自己是个sb
我们使用一个数组对前面的信息进行维护，当有相同的时候，我们直接对个数+1，不同的时候，我们只要改变一下信息就行了。
这里注意的是，当i-1,i-2都存在的时候，要注意合并。
#includescanf("%d",&a[i]);
int fl=0;
dp[fl].first=a[0];
dp[fl++].second=1;
for(int i=1; iif(a[i]^dp[fl-1].first) {
if(i&1) {
dp[fl-1].first=a[i];
++dp[fl-1].second;
if(fl>=2) {
dp[fl-2].second+=dp[fl-1].second;
--fl;
}
} else {
dp[fl].first=a[i];
dp[fl++].second=1;
}
} else {
++dp[fl-1].second;
}
}
int ans=0;
for(int i=0; iif(!dp[i].first) {
ans+=dp[i].second;
}
}
printf("%d\n",ans);
}
return 0;
}
//
///*
// start:2016-07-28/22:35
// finish:
//*/
//#define si(x) scanf("%d",&(x))
//const int maxn=1e5+5;
//int a[maxn];
//int z[maxn];
//int o[maxn];
//
//int main() {
// int n;
// while(~si(n)) {
// for(int i=0; i
// if(n==1) {
// printf("%d\n",!a[0]);
// continue;
// }
// int ans=0;
// for(int i=0; i
// if((i&1)&&(a[i]^a[i-1])) {
// if(a[i]) {
// o[i]=o[i-1]+z[i-1]+1;
// ans-=z[i-1];
// z[i]=0;
// } else {
// z[i]=z[i-1]+o[i-1]+1;
// ans+=z[i];
// o[i]=0;
// }
// } else {
// if(a[i]) {
//// if(o[i]==0)
// z[i]=i-1>=0?z[i-1]:0;
// if(i-1>=0){
// if(a[i-1]){
// o[i]=o[i-1]+1;
// }else o[i]=1;
// }
// else o[i]=1;
// } else {
// ++ans;
// o[i]=i-1>=0?o[i-1]:0;
// if(i-1>=0){
// if(!a[i-1]){
// z[i]=z[i-1]+1;
// }else z[i]=1;
// }
// else z[i]=1;
// }
//// if(i-1>=0)z[i]=z[i-1],o[i]=o[i-1];
//// z[i]+=(a[i]==0),o[i]+=(a[i]==1);
//// ans+=(a[i]==0);
// }
// }
// printf("%d\n",n-o[n-1]);//n-o[n-1]);
//// for(int i=0; i
//// cout<
//// }
//// cout<
//// for(int i=0; i
//// cout<
//// }
//// cout<
// }
// return 0;
//}
///*
//12
//1 0 1 1 1 0 0 0 1 0 0 1
//*/