Codeforces-1476D Journey


Problem

Portal


Thoughts

Portal


Accepted Code

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;                     

const int N = 3e5+10;

char s[N];
int pre[N], suf[N];

signed main()
{
    int T; cin >> T;
    while(T -- )
    {
        int n, t = 1; cin >> n >> s+1;
        s[0] = s[1], s[n+1] = s[n];
        // 第i条边左边有多少条边与其交替不同(包括其自己)
        for(int i = 1 ; i <= n ; i ++ )
        {
            if(s[i] != s[i-1]) t ++ , pre[i] = t;
            else pre[i] = t = 1;
        }
        // 第i条边右边有多少条边与其交替不同(包括其自己)
        t = 1;
        for(int i = n ; i >= 1 ; i -- )
        {
            if(s[i] != s[i+1]) t ++ , suf[i] = t;
            else suf[i] = t = 1;
        }
        for(int i = 0 ; i <= n ; i ++ )
        {
            // 加上自身那个点
            if(!i)
            {
                if(s[i+1] == 'R') cout << suf[i+1]+1 << " ";
                else cout << "1 ";
            }
            else if(i == n)
            {
                if(s[i] == 'L') cout << pre[i]+1 << endl;
                else puts("1");
            }
            else
            {
                int res = 1;
                if(s[i] == 'L') res += pre[i];
                if(s[i+1] == 'R') res += suf[i+1];
                cout << res << " ";
            }
        }
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1478D Nezzar and Board Codeforces-1478D Nezzar and Board
ProblemPortal Thoughts题意为给出一个序列xi,你可以任意挑选两个数x,y将2·x-y加入序列中,询问在是否可以在序列中发现数k。假设我们任意挑选4个数:x,y,p,q并且将2·x-y、2·p-q加入到序列中,挑选出新
Next 
Codeforces-1476C Longest Simple Cycle Codeforces-1476C Longest Simple Cycle
ProblemPortal Accepted Code#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5+1
  TOC