codeforces733C

时间：2022-07-22 05:03:25

Epidemic in Monstropolis

CodeForces - 733C

有n条鱼排成一列，第i条鱼大小为ai,根据自然界的生存法则，相邻的两只鱼中，较大的鱼可以吃掉较小的鱼，如果两条鱼大小相等，则它们无法吃掉对方。当一条鱼i吃掉另一条鱼j后，它的体积会变成ai+aj，即获取小鱼的大小。小鱼因为消失故会在序列中被抹去。

例如，对于序列 [1, 2, 2, 2, 1, 2] ，有如下情况

  1. 第一条鱼无法吃掉任何一条鱼因为a1 = 1
  2. 第二条鱼无法吃掉第三条鱼因为 a2 = 2且 a3 = 2;
  3. 第二条鱼无法吃掉第五条鱼因为它们不相邻;
  4. 第二条鱼可以吃掉第一条鱼，吃掉以后a序列更新为 [3, 2, 2, 1, 2].

假设过了一段时间以后，原来的n条鱼只剩下 k (k ≤ n) 条, 第 j 条鱼大小为 bj.

试推导出一个合法的吃鱼顺序，使得a序列转变为b序列，若无法推导，输出NO。

Input

第一行一个整数n (1 ≤ n ≤ 500)

第二行n个整数 a1, a2, ..., an (1 ≤ ai ≤ 106)

第三行一个整数 k (1 ≤ k ≤ n)

第四行k个整数 b1, b2, ..., bk (1 ≤ bj ≤ 5·108)

Output

若无解，输出 "NO"

若有解，第一行输出 "YES".

接下来 n - k 行描述吃鱼的全部过程. 每行包含一个数字x和一个字符c。x表示序列中的第几条鱼，c表示吃的是左边还是右边的鱼，左边则c为'L'，右边则c为'R'

要注意，每次吃掉一条鱼后，序列的长度会减1。

若有多组解，任意输出一组。

Example

Input

6
1 2 2 2 1 2
2
5 5

Output

YES
2 L
1 R
4 L
3 L

Input

5
1 2 3 4 5
1
15

Output

YES
5 L
4 L
3 L
2 L

Input

5
1 1 1 3 3
3
2 1 6

Output

NO

sol：略显蛋疼的模拟题，首先容易发现吃出来的大鱼一定是吃了连续的一段，所以每个bi可以对应a中的一段，但是因为每次吃一条鱼都会使得序列长度减1，然后就需要模拟了，一开始感觉可以用树状数组维护坐标，但是写了一会就放弃了，直接暴力吃暴力更新整段数组又不是不行（o(╥﹏╥)o）

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

inline void F5(int x,int opt);

inline void Debug();

inline bool Solve(int l,int r);

int n,m;

int a[N],b[N],c[N],d[N];

int ans[N],Fx[N];

inline void F5(int x,int opt)

{

    a[x]+=a[x+opt];

    a[x+opt]=;

    memset(c,,sizeof c);

    memmove(c,a,sizeof c);

    memset(a,,sizeof a);

    int i,cnt=;

    for(i=;i<=n;i++) if(c[i])

    {

        a[++cnt]=c[i];

    }

}

inline void Debug()

{

    int i;

    for(i=;i<=n;i++) W(a[i]);

    puts("");

}

inline bool Solve(int l,int r)

{

    if(l==r) return true;

    int i,Now=;

    bool Flag=;

    for(i=l+;i<=r;i++) if(a[i]!=a[i-]) {Flag=; break;}

    if(!Flag) return false;

    for(i=l;i<=r;i++)

    {

        if(a[i]>a[Now]) Now=i;

        else if(a[i]==a[Now]&&((i<r&&a[i]>a[i+])||(i>l&&a[i]>a[i-]))) Now=i;

    }

    int cnt=r-l+,Sum=a[Now];

    while(cnt>)

    {

        if(Now>l&&Sum>a[Now-])

        {

            Sum+=a[Now-];

            ans[++*ans]=Now; Fx[*ans]=-;

            F5(Now,-);

            Now--;

        }

        else if(Now<r&&Sum>a[Now+])

        {

            Sum+=a[Now+];

            ans[++*ans]=Now; Fx[*ans]=;

            F5(Now,);

            r--;

        }

        cnt--;

    }

    return true;

}

int main()

{

    *ans=;

    int i,j;

    R(n);

    for(i=;i<=n;i++) a[i]=read();

    R(m);

    for(i=;i<=m;i++) R(b[i]);

    int Last=;

    for(i=;i<=m;i++)

    {

        int Sum=;

        bool Flag=;

        for(j=Last;j<=n;j++)

        {

            Sum+=a[j];

            if(Sum>b[i]) break;

            if(Sum==b[i])

            {

                if(!Solve(Last,j)) return puts("NO"),;

                Last=i+;

                Flag=;

                break;

            }

        }

        if(!Flag) return puts("NO"),;

    }

    if(a[m+]) return puts("NO"),;

    puts("YES");

    for(i=;i<=*ans;i++)

    {

        W(ans[i]);

        if(Fx[i]==-) putchar('L'); else putchar('R');

        puts("");

    }

    return ;

}

/*

Input

6

1 2 2 2 1 2

2

5 5

Output

YES

2 L

1 R

4 L

3 L

Input

5

1 2 3 4 5

1

15

Output

YES

5 L

4 L

3 L

2 L

Input

5

1 1 1 3 3

3

2 1 6

Output

NO

input

3

2 2 1

1

5

output

YES

2 R

2 L

input

5

1 2 3 4 5

1

10

output

NO

*/

相关文章