Journey
题意
一条链上分布有 0~n 个点，每一个点中间有一条单向边连接，并用字母 ‘L’ 和 ‘R’表示
若为 L 说明该边方向向左，若为 R 说明该边方向向右
你可以在任意一点开始移动，并且每移动一步，上述边的方向改变一次
要求求出每一个点能够到达的最多点数（若一个点被多次走到，那么仅算一次）
思路
当某一点左边或者右边出现RL 交替时 可以一直走下去 并且可以原路返回
只需要求出当前点左边和右边RL 或者LR 交替出现的次数即可 (顺序不重要)
即
if (s[i] != s[i - 1]) sum1[i] = ++temp; // 左边 if (s[i] != s[i + 1]) sum2[i] = ++temp; // 右边
需要注意的是 如果对于每个点直接求 会超时 所以需要预处理一下
for (int i = 1, temp = 1; i <= n; ++i) { if (s[i] != s[i - 1]) { sum1[i] = ++temp; } else sum1[i] = temp = 1; } for (int i = n, temp = 1; i >= 1; --i) { if (s[i] != s[i + 1]) sum2[i] = ++temp; else sum2[i] = temp = 1; }
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 300010; int n; int a[N]; char s[N]; int sum1[N], sum2[N]; void solve() { cin >> n; cin >> s + 1; s[0] = s[1]; s[n + 1] = s[n]; for (int i = 1, temp = 1; i <= n; ++i) { if (s[i] != s[i - 1]) { sum1[i] = ++temp; } else sum1[i] = temp = 1; } for (int i = n, temp = 1; i >= 1; --i) { if (s[i] != s[i + 1]) sum2[i] = ++temp; else sum2[i] = temp = 1; } for (int i = 0; i <= n; ++i) { if (i == 0) { if (s[1] == 'R')cout << sum2[1] + 1 << " "; else printf("1 "); } else if (i == n) { if (s[n] == 'L')cout << sum1[n] + 1 << endl; else printf("1\n"); } else { int res = 1; if (s[i] == 'L')res += sum1[i]; if (s[i + 1] == 'R')res += sum2[i + 1]; cout << res << " "; } } } int main() { int t; cin >> t; while (t--) solve(); return 0; }
