2018网络预选赛青岛 H

题目链接：https://pintia.cn/problem-sets/1036903825309761536/problems/1041156323504345088

题意：小明从某一点出发，向右方前进，只有路口是绿灯（用1代表）的时候才可通行，红灯要等待，所有红绿灯每过一秒变化一次（红->绿，绿->红）,问从任意一点到该点右边的任意一点的所花费的时间和。

题解：设t(1,n)是从点1到点n所花费的时间，我们可以经过特殊的判断t(1,n)拆分成t(1,a)+t(a,n)+c (c是1，-1，或者0，通过判断得来)。

1：如果该点是红灯（用0代表）且t(1,a)花费了奇数的时间，此时t(a,n)=t(1,n)-t(1,a)+1；

2：如果该点是绿灯且t(1,a)花费了奇数的时间，此时t(a,n)=t(1,n)-t(1,a)-1；

其余情况t(1,n)=t(1,a)+t(a,n),想不太懂可以对照1，2个样例。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=100010;

long long sum[maxn],ssum[maxn];

int main(){

	int T,cnt,p,S;

	char s[100010];

	scanf("%d",&T);

	long long ans,tmp;

	while(T--){

		scanf("%s",s+1);

		ans=0;

		int n=strlen(s+1);

		p=1;

		sum[0]=ssum[n+1]=0;

		for(int i=1;i<=n;i++){

			if(s[i]-'0'==p){

				sum[i]=sum[i-1]+1;//t(i-1,i)的前缀和，即t(0,i)

				p^=1;

			}

			else{

				sum[i]=sum[i-1]+2;

			}

		}

		for(int i=n;i>=1;i--){//后缀和

			ssum[i]=ssum[i+1]+sum[i];

		}

		ans+=ssum[1];

		for(int i=2;i<=n;i++){

			tmp=sum[i-1];

			if(s[i]-'0'==0&&tmp%2==1)tmp--;

			if(s[i]-'0'==1&&tmp%2==1)tmp++;

			ans+=(ssum[i]-(n-i+1)*tmp);

		}

		printf("%lld\n",ans);

	}

}

巴特西

2018网络预选赛青岛 H

最新文章

热门文章

巴特西

2018网络预选赛 青岛 H

最新文章

热门文章

2018网络预选赛青岛 H