2018 ACM-ICPC 亚洲青岛区域网络赛 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 iis an integer, stands a traffic light of type ti (ti∈{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−1q=p+1∑nt(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∣≤105, ∣s∣=n, si∈{‘0’,‘1’} for all 1≤i≤∣s∣), indicating the types of the traffic lights. If si=‘0’, the traffic light at point (i−0.5) is of type 0 and is initially red; If si=‘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 106.

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.

作者: 浙江大学竞赛命题组

单位: ACMICPC

时间限制: 500 ms

内存限制: 64 MB

代码长度限制: 32 KB

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int a[100005];
char s[100005];


int main()
{
    long long sum;
    int n, i, j,t;
    scanf("%d", &t);
    while(t--)
    {
        //memset(s, 0,sizeof())
        scanf("%s", &s);
        n = strlen(s);
        long long ans = 0, maxn = 0;
        for(i = 0; i < n; i++)
        {
            a[i] = s[i] - '0';
            if(i == 0)
            {
                if(a[i] == 0)
                    maxn = 2;
                else
                    maxn = 1;
            }
            else
            {
                if(a[i] == a[i-1])
                    maxn += 2;
                else
                    maxn += 1;
            }

            ans += maxn;
        }
       // cout<<" "<<ans<<endl;
        sum = ans;
        int m = n;
        for(i = 1; i < n; i++)
        {
            if(a[i-1] == 1 && a[i] == 1)
            {
                ans = ans - ((m-1) * 2 + 1);
            }
            else if(a[i-1] == 1 && a[i] == 0)
            {
                ans = ans - 1;
            }
            else if(a[i-1] == 0 && a[i] == 1)
            {
                ans = ans - (m * 2);
            }
            else if(a[i-1] == 0 && a[i] == 0)
            {
                ans = ans - (m * 2);
            }
            sum += ans;
            m--;
        }
        printf("%lld
", sum);
    }
    return 0;
}

2018 ACM-ICPC 亚洲青岛区域网络赛 H Traveling on the Axis

相关推荐