Description n层楼，每层有一个指示牌指示当前是上一层还是下一层，每经过一层指示牌就会反向，对于一个起点i，最后要经过多少步才能到第0层或者第n+1层，对于每个i输出结果 Input 第一行一整数n表示楼层数，之后一个长度为n的字符串表示初始状态每层的指示方向(1<=n<=1e6) Output 输出n个整数，第i个整数表示初始时在第i层时要经过多少步才能出去，如果永远出不去则输出-1 Sample Input 3 UUD Sample Output 5 6 3 Solution 假如从一个U开始走，那么就一直往上一直走到一个D，然后开始往下走一直到一个U，然后一直往上回到原位，这一段走过后，这个点下面第一个U变成了D，上面第一个D变成了U，而其他位置都没有变化，走过的步数是这两个位置差的二倍，所以每进行一次这样的操作，该点上面一个D和下面一个U就会反向，最后一定是某一边全部是D该点从下面出去或全部是U然后该点从上面出去，令lu[i]为1~i中U的个数，rd[i]表示i~n中D的个数，如果lu[i]<=rd[i+1]，那么第i个点出发就会从下面出去，答案为i+i右边前lu[i]个D到i的距离和*2+i左边所有U到i的距离和*2，否则第i个点就会从上面出去，答案为n-i+1+i左边前rd[i]个U到i的距离和*2+i右边所有D到i的距离和*2，两部分分别统计，先统计U对每个点答案的影响，D同理，从左到右维护一个队列存所有的U的下标，在统计U对第i个答案的影响是，如果栈内元素已经超过rd[i]，说明前面的U对之后的答案已经没有影响，那么就从队首移出去，如果当前点是U就加入队尾，维护一个i-u[j] (u[j]<=i)的和sum，其中u[j]是第j个U的位置，那么U对第i个答案的贡献就是2*sum Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 1111111 int n,lu[maxn],rd[maxn],s,e,a[maxn]; ll ans[maxn]; char c[maxn]; int main() { while(~scanf("%d",&n)) { scanf("%s",c+1); lu[0]=0; for(int i=1;i<=n;i++)lu[i]=lu[i-1]+(c[i]=='U'); rd[n+1]=0; for(int i=n;i>=1;i--)rd[i]=rd[i+1]+(c[i]=='D'); for(int i=1;i<=n;i++) { if(lu[i]<=rd[i+1])ans[i]=i; else ans[i]=n-i+1; } s=e=0; ll temp=0; for(int i=1;i<=n;i++) { temp+=e-s; while(e-s>rd[i]) temp-=i-a[s++]; ans[i]+=2ll*temp; if(c[i]=='U')a[e++]=i; } s=e=0; temp=0; for(int i=n;i>=1;i--) { temp+=e-s; while(e-s>lu[i]) temp-=a[s++]-i; ans[i]+=2ll*temp; if(c[i]=='D')a[e++]=i; } for(int i=1;i<=n;i++) printf("%I64d%c",ans[i],i==n?'\n':' '); } return 0; }