题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5809

题意：n个红绿灯，每个等左右有两个点，标号0~n，t(p,q)表示从点p走到点q花费的时间，每路过一个灯花费1s，如果是红灯不能通行，绿灯可以，每过1s红灯变为绿灯，绿灯变红灯，1表示绿灯，0表示红灯。问t(0,n)+..t(0,1)+t(1,n)+..+t(1,2)+......+t(n-1,n)。

思路：如果这个灯前面的灯不同，那么通过这个灯不需要等待，例如：01，通过第一个灯用了2s，这是第二个灯是绿灯，10也是如此。

　　　基于以上结论，每个灯花费的时间就分为三个部分：1.经过灯必定花费的1s；2.因为和前面的灯不同而需要等待的1s；3.初始状态为0，作为第一个路灯时，必须等待的1s。

　　   第一种情况很好求，第二种和第三种就是统计这个灯在所有t(p,q)中出现的次数。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxlen_s 100009#define ll long longusing namespace std;int sum_sum[maxlen_s]; //前n项和的前n项和int wait_qian[maxlen_s]; //第二种情况int wait_self[maxlen_s]; //第三种情况int arr[maxlen_s];//路灯的初始状态string ss;void setsum_sum() {    sum_sum[1] = 1;    for (int i = 2; i <= 100002; i++) {        sum_sum[i] = ((i*(i + 1)) >> 1) + sum_sum[i - 1];    }}void setwait(int len) {    arr[0] = 0;    for (int i = 1; i <= len; i++) {        if (arr[i] == 0) wait_self[i] = 1;        if (arr[i - 1] == arr[i]) wait_qian[i] = 1;    }    wait_qian[1] = 0;}int main() {    setsum_sum();    int t;    scanf("%d", &t);    getchar();    while (t--)    {        cin >> ss;        for (int i = 0; i
         
          =2                ans += (ss.length() - i + 1) + (i - 2);            }            if (wait_self[i]) {                ans += ss.length() - i + 1;            }        }        printf("%lld\n", ans);        memset(wait_qian, 0, sizeof wait_qian);        memset(wait_self, 0, sizeof wait_self);    }    return 0;}