題目鏈接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4054

題意就是一個小孩走一段路，這條路上有n個紅綠燈，并且告訴了你初始紅綠燈的狀態(tài)，用1表示路燈，0表示紅燈，并且沒經(jīng)過一秒紅綠燈就轉換，從綠燈變?yōu)榧t燈或是從紅燈變?yōu)榫G燈。小孩走這一段路，如果碰到了綠燈直接走過去，如果碰到了紅燈停一秒鐘等紅燈變?yōu)榫G燈在走過去，定義t（p，q）為從p點走到q點所需要的時間，q>p,并且q和p可以取任何值，問t（p，q）的總和是多少。

直接畫圖找規(guī)律，可以發(fā)現(xiàn)，如果是紅燈的話，sum=sum-2-2*(thenum-1);第一個是綠燈第二個是紅燈的話，是sum=sum-1;第一個是綠燈，第二個是綠燈的話，是sum=sum-1-2*(thenum-1); 其中sum是從第i個點出發(fā)，走到i+1，i+2.。。。i+n的和。thenum是還剩下幾個點。

詳情見代碼：

#include <iostream> #include <cstring> #include <stdio.h> using namespace std; const int inf=1e5+7; int arr[2][inf]; typedef long long ll;int main() {int T;scanf("%d",&T);string str;while(T--){cin>>str;for(int i=0;i<str.length();i++) {arr[0][i]=str[i]-48;arr[1][i]=1-arr[0][i]; //其中技巧使用。 } int len=str.length(); ll sum1=0,sum=0; //這里的sum是零。 int k=0; for(int i=0;i<len;i++) {if(arr[k][i]==0) //即使是過去之后任然是不變的。 {sum1=sum1+2; //只求算出一層的來。 sum+=sum1;} else{sum1=sum1+1;sum+=sum1;k=(k+1)%2; } }sum1=0;ll temp=0;ll ans=sum; int thenum=str.length(); k=0;for(int i=0;i<len-1;i++) //到3，和4正好對應。 {if(arr[k][i]==0){sum=sum-2-2*(thenum-1);thenum--; ans+=sum; }else if(arr[k][i]==1&&arr[k][i+1]==0) //說明是一。不論是哪一個都是要加一的。 {sum=sum-1;thenum--;ans+=sum; } else{sum=sum-1-2*(thenum-1);thenum--;ans+=sum;}} cout<<ans<<endl;}return 0; }

?

?

總結

以上是生活随笔為你收集整理的Traveling on the Axis （The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online）的全部內容，希望文章能夠幫你解決所遇到的問題。

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