codeforce 1476D D. Journey 画图 逆推 C

codeforce 1476D D. Journey 画图 逆推 C https://codeforces.com/contest/1476/problem/D D. Journey time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output

There are n+1">n+1n+1 cities, numbered from 0">00 to n">nn. n">nn roads connect these cities, the i">ii-th road connects cities i−1">i?1i?1 and i">ii (i∈[1,n]">i∈[1,n]i∈[1,n]).

Each road has a direction. The directions are given by a string of n">nn characters such that each character is either L or R. If the i">ii-th character is L, it means that the i">ii-th road initially goes from the city i">ii to the city i−1">i?1i?1; otherwise it goes from the city i−1">i?1i?1 to the city i">ii.

A traveler would like to visit as many cities of this country as possible. Initially, they will choose some city to start their journey from. Each day, the traveler must go from the city where they currently are to a neighboring city using one of the roads, and they can go along a road only if it is directed in the same direction they are going; i.?e., if a road is directed from city i">ii to the city i+1">i+1i+1, it is possible to travel from i">ii to i+1">i+1i+1, but not from i+1">i+1i+1 to i">ii. After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. If the traveler cannot go from their current city to a neighboring city, their journey ends; it is also possible to end the journey whenever the traveler wants to.

The goal of the traveler is to visit as many different cities as possible (they can visit a city multiple times, but only the first visit is counted). For each city i">ii, calculate the maximum number of different cities the traveler can visit during exactly one journey if they start in the city i">ii.

Input

The first line contains one integer t">tt (1≤t≤104">1≤t≤1041≤t≤104) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n">nn (1≤n≤3⋅105">1≤n≤3?1051≤n≤3?105). The second line contains the string s">ss consisting of exactly n">nn characters, each character is either L or R.

It is guaranteed that the sum of n">nn over all test cases does not exceed 3⋅105">3?1053?105.

Output

For each test case, print n+1">n+1n+1 integers. The i">ii-th integer should be equal to the maximum number of different cities the traveler can visit during one journey if this journey starts in the i">ii-th city.

Example input Copy 
2
6
LRRRLL
3
LRL
output Copy 
1 3 2 3 1 3 2
1 4 1 4

24=17+7">27">25">分析

24=17+7">27">25">题目给出的背景有点迷，我们设为上下两部分来算

24=17+7">27">25">b 0 1 2 3 4 5 6

24=17+7">27">25">c 0 1 2 3 4 5 6

24=17+7">27">25">由于LRRRLL

24=17+7">27">25">b1链接c0，c2连接b1，这样每次想走某一条边，就只能通过已经连的进行

24=17+7">27">25">接着就是类似并查集的操作，倒着把连接的边数算到前面

然后再从前往后依次输出并更新

可惜就差那么几秒

就写完了

24=17+7">27">25">代码

https://codeforces.com/contest/1476/submission/105938876

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string.h>
#include 
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-13
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
char a[300005];
int b[300005];
int c[300005];
int bv[300005];
int cv[300005];
int main(){
    int t;
    s(t)
    int n;
    while(t --){
        s(n) gc;
        for(int i = 0; i <= n;i++){
            b[i] = i;
            c[i] = i;
            bv[i] = 1;
            cv[i] = 1;
        }
        for(int i = 1; i <= n; i ++){
            a[i] = gc;
            if(a[i] == 'L'){
                b[i] = i-1;
            }else if(a[i] == 'R'){
                c[i] = i-1;
            }
        }
        for(int i = n; i >= 1; i --){
            if(b[i] == i){
                cv[i] ++;
                bv[i-1] = cv[i];
            }else{
                bv[i] ++;
                cv[i-1] = bv[i];
            }
        }
        /*for(int i = 0; i <= n; i ++){
            p(b[i]) pk
        }
        pn
        for(int i = 0; i <= n; i ++){
            p(c[i]) pk
        }
        pn*/
        for(int i = 0; i <= n-1; i ++){
            p(bv[i]) pk
            if(b[i+1] == i){
                bv[i+1] = cv[i];
            }else{
               cv[i+1] = bv[i];
            }
        }
        p(bv[n]) pk pn
    }
    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签