题目大意

给定n级台阶,符号包括U和D,每经过某级台阶就往相对应的方向前进,且将该级台阶对应的符号反转。问从第i级台阶出发需要多少步才能从楼梯上方或下方出去。

题目分析

@Kino推荐的一道题。大概这阶段就刷他给的题然后退役~。

首先对于一个位置i,考虑它是从楼梯上方或者下方走出。

如果对于它左边包括它本身的U的个数 > 他右边D的个数   那么从右边出去。

反之从左边出去。

确定了这个之后考虑步数的计算,对于某个点i,假设为U。最后向右出来

则它所消耗的步数就等于他所对应的D(假设中间那些U和D已走过并转换成D)-他的下标*2;  有点绕可以画图感知一下。

然后最后加上他一路走出去的距离(即直接从该点走到对应边界的距离)即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;
char ch[1000005];
int cnt[1000005],n;
LL ans[1000005],sum;
int main(){
	scanf("%d\n",&n);
	For (i,n){
		scanf("%c",&ch[i]);
	}
	cnt[0]=0;sum=0;
	For (i,n){
		if (ch[i]=='D') cnt[++cnt[0]]=i;
	} 
	For (i,cnt[0]){
		sum+=(cnt[i]-i)*2;
		ans[i]=sum+i;
	}
	cnt[0]=0;sum=0;
	ForD(i,n){
		if (ch[i]=='U') cnt[++cnt[0]]=i;
	}
	For(i,cnt[0]){
		int now=n-i+1;
		sum+=(now-cnt[i])*2;
		ans[now]=sum+i;
	}
	For (i,n) printf("%lld ",ans[i]);
}

「知我罪我,其惟春秋」