H Traveling on the Axis
BaoBao is taking a walk in the interval [0,n] on the number axis, but he is not free to move, as at every point (i?0.5) for all i∈[1,n], where i is an integer, stands a traffic light of type t?i?? (t?i??∈{0,1}).
BaoBao decides to begin his walk from point p and end his walk at point q (both p and q are integers, and p<q). During each unit of time, the following events will happen in order:
- Let's say BaoBao is currently at point x, he will then check the traffic light at point (x+0.5). If the traffic light is green, BaoBao will move to point (x+1); If the traffic light is red, BaoBao will remain at point x.
- All the traffic lights change their colors. If a traffic light is currently red, it will change to green; If a traffic light is currently green, it will change to red.
A traffic light of type 0 is initially red, and a traffic light of type 1 is initially green.
Denote t(p,q) as the total units of time BaoBao needs to move from point p to point q. For some reason, BaoBao wants you to help him calculate
?p=0?∑?n?1???q=p+1?∑?n??t(p,q)
where both p and q are integers. Can you help him?
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first and only line contains a string s (1≤∣s∣≤10?5??, ∣s∣=n, s?i??∈{‘0’,‘1’} for all 1≤i≤∣s∣), indicating the types of the traffic lights. If s?i??=‘0’, the traffic light at point (i?0.5) is of type 0 and is initially red; If s?i??=‘1’, the traffic light at point (i?0.5) is of type 1 and is initially green.
It's guaranteed that the sum of ∣s∣ of all test cases will not exceed 10?6??.
Output
For each test case output one line containing one integer, indicating the answer.
Sample Input
3
101
011
11010
Sample Output
12
15
43
Hint
For the first sample test case, it's easy to calculate that t(0,1)=1, t(0,2)=2, t(0,3)=3, t(1,2)=2, t(1,3)=3 and t(2,3)=1, so the answer is 1+2+3+2+3+1=12.
For the second sample test case, it's easy to calculate that t(0,1)=2, t(0,2)=3, t(0,3)=5, t(1,2)=1, t(1,3)=3 and t(2,3)=1, so the answer is 2+3+5+1+3+1=15.
题目大致意思是一个人从起点出发，如果前面是绿灯则向前走花费一秒，同时路灯每一秒都会交换一次，红->绿->红往复，而红灯要等一秒灯变绿才能够走。题目给的输入数据，1代表绿灯，0代表红灯，是最开始的状态。然后输出结果是对起点和重终点的枚举，枚举任意起点到终点所花费的时间的累加和
我们可以模拟一下这个过程
对于第一个样例 101，
当前位置0 ，第一个是绿灯，花费一秒 （0，1）= 1秒
当前位置1，状态 010 ，下一个还是绿灯，（0，2）=（0，1）+1 ；（1，2）=2；
当前位置2， 状态101，下一个还是绿灯 ， （0，3）=（0，2）+1； （1，3）=（1，2）+1；（2，3）=1；（如果下一个是红灯，（0，3）=（0，2）+2； （1，3）=（1，2）+2；（2，3）=2；并且改变两次次状态就相当于状态不变）
#include<bits/stdc++.h>
using namespace std;
long long sum[100005]={0};
char a[100005],b[100005];
int main()
{long long t;while(cin>>t){while(t--){scanf("%s",a+1);long long len=strlen(a+1);long long f[100005]={0};for(long long i=1;i<=len;++i){b[i]=a[i]=='1'?'0':'1';if(a[i]=='0') {f[i]=2; //f数组记录秒数，如果绿灯就是1秒，红灯就是2 秒}else {f[i]=1;}}long long s=0,k=1; //k等于 1 表示在原始 a序列这条线上，否则在b序列这条线上for(long long i=1;i<=len;++i){if(k==1){if(a[i]=='1'){sum[i]=sum[i-1]+i-1+f[i];k=2;} else{k=1;sum[i]=sum[i-1]+(i-1)*2+f[i];}}else{if(b[i]=='1'){sum[i]=sum[i-1]+i-1+f[i];k=1;} else{sum[i]=sum[i-1]+(i-1)*2+f[i];k=2;}}s+=sum[i];}cout<<s<<endl;}}
}