首页 > 其他 > 详细

codeforces733C

时间:2019-04-21 20:53:24      阅读:150      评论:0      收藏:0      [点我收藏+]

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=0;
    bool f=0;
    char ch= ;
    while(!isdigit(ch))
    {
        f|=(ch==-); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar(-); x=-x;
    }
    if(x<10)
    {
        putchar(x+0); return;
    }
    write(x/10);
    putchar((x%10)+0);
    return;
}
#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) write(x),putchar(‘\n‘)
const int N=505;

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]=0;
    memset(c,0,sizeof c);
    memmove(c,a,sizeof c);
    memset(a,0,sizeof a);
    int i,cnt=0;
    for(i=1;i<=n;i++) if(c[i])
    {
        a[++cnt]=c[i];
    }
}
inline void Debug()
{
    int i;
    for(i=1;i<=n;i++) W(a[i]);
    puts("");
}
inline bool Solve(int l,int r)
{
    if(l==r) return true;
    int i,Now=0;
    bool Flag=0;
    for(i=l+1;i<=r;i++) if(a[i]!=a[i-1]) {Flag=1; 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+1])||(i>l&&a[i]>a[i-1]))) Now=i;
    }
    int cnt=r-l+1,Sum=a[Now];
    while(cnt>1)
    {
        if(Now>l&&Sum>a[Now-1])
        {
            Sum+=a[Now-1];
            ans[++*ans]=Now; Fx[*ans]=-1;
            F5(Now,-1);
            Now--;
        }
        else if(Now<r&&Sum>a[Now+1])
        {
            Sum+=a[Now+1];
            ans[++*ans]=Now; Fx[*ans]=1;
            F5(Now,1);
            r--;
        }
        cnt--;
    }
    return true;
}
int main()
{
    *ans=0;
    int i,j;
    R(n);
    for(i=1;i<=n;i++) a[i]=read();
    R(m);
    for(i=1;i<=m;i++) R(b[i]);
    int Last=1;
    for(i=1;i<=m;i++)
    {
        int Sum=0;
        bool Flag=0;
        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"),0;
                Last=i+1;
                Flag=1;
                break;
            }
        }
        if(!Flag) return puts("NO"),0;
    }
    if(a[m+1]) return puts("NO"),0;
    puts("YES");
    for(i=1;i<=*ans;i++)
    {
        W(ans[i]);
        if(Fx[i]==-1) putchar(L); else putchar(R);
        puts("");
    }
    return 0;
}
/*
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
*/
View Code

 

codeforces733C

原文:https://www.cnblogs.com/gaojunonly1/p/10746556.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!