Codeforces Round #378 (Div. 2)C.Epidemic in Monstropolis（codeforces733c）

93 阅读 0 评论 62 点赞

我是靠谱客的博主甜甜荔枝，最近开发中收集的这篇文章主要介绍Codeforces Round #378 (Div. 2)C.Epidemic in Monstropolis（codeforces733c），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

codeforces733c

题意：

给你 $n$ 个数， $a_{1},a_{2},a_{3},...a_{n}$ ,再给你m个数 $b_{1},b_{2},b_{3},...b_{m}$ ，问你 $a$ 序列能否通过合并变成 $b$ 序列。合并的条件为只能相邻的数合并， $a_{i}与a_{i+1}$ 能合并的条件为 $a_{i}>a_{i+1}或a_{i}<a_{i+1}$ 。合并出来的值为 $a_{i}+a_{i+1}$ 。然后通过新序列合并下去问你能不能达到b序列？能达到的话输出是如何合并的，不能的话输出NO。

数据范围：

$1leq mleq n leq 500,1leq a_{i} leq 10^6,1leq b_{i} leq 5*10^8$

题解：

1、我们可以把a序列分成m个连续的块，每个块的值的总和与b对应，对于每个块我们单独处理下，我们可以这个块的最大值开始向两边合并，切存在相邻的数小于它，然后一直合并下去就可以了！！！
2、但这里有几个注意点，每个块不能合并的条件为这个块里所有元素都相等且块的长度不为1、b的总和和a的总和要相等。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#include<cmath>
#define PI 2*asin(1.0)
#define LL long long
#define pb push_back
#define pa pair<int,int>
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define bug(x) printf("%d++++++++++++++++++++%dn",x,x)
#define key_value ch[ch[root][1]][0]
const int  MOD = 1000000007;
const int N = 500 + 15;
const int maxn = 1e5+ 14;
const int letter = 130;
const int INF = 1e9;
const double pi=acos(-1.0);
const double eps=1e-8;
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[N],b[N],dis[N],cnt;
vector<int>ps;
struct node{
    int id;
    char ch;
}g[N];
bool solve(int l,int r,int val,int p){
    if(l==r) return 1;
    ps.clear();
    for(int i=l;i<=r;i++) ps.pb(a[i]);
    int id=-1,max1=0;
    for(int i=0;i<ps.size();i++) max1=max(max1,ps[i]);
    for(int i=0;i<ps.size();i++){
        if(i==0&&max1==ps[i]&&ps[i]>ps[i+1]) {id=i;break;}
        else if(i==ps.size()-1&&max1==ps[i]&&ps[i]>ps[i-1]){id=i;break;}
        else if(i!=0&&i!=ps.size()-1&&max1==ps[i]&&(ps[i]>ps[i-1]||ps[i]>ps[i+1])){id=i;break;}
    }
    if(id==-1) return 0;
    while(ps.size()>1){
        if(id==0){
            g[cnt].id=id+p,g[cnt++].ch='R';
            ps[id]+=ps[id+1];
            ps.erase(ps.begin()+id+1);
        }
        else if(id==ps.size()-1) g[cnt].id=id+p,g[cnt++].ch='L',ps[id]+=ps[id-1],ps.erase(ps.begin()+id-1),id--;
        else {
            if(ps[id]>ps[id-1]) g[cnt].id=id+p,g[cnt++].ch='L',ps[id]+=ps[id-1],ps.erase(ps.begin()+id-1),id--;
            else if(ps[id]>ps[id+1])g[cnt].id=id+p,g[cnt++].ch='R',ps[id]+=ps[id+1],ps.erase(ps.begin()+id+1);
        }
    }
    return 1;
}
int main(){
    cnt=0;
    scanf("%d",&n);
    LL c=0,d=0;
    for(int i=1;i<=n;i++) scanf("%d",a+i),c+=1ll*a[i],dis[i]=dis[i-1]+a[i];
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",b+i),d+=1ll*b[i];
    int l=0,gg=1;
    int flag=1;
    for(int p=1;p<=n;p++){
        if(gg>m) {flag=0;break;}
        if(dis[p]-dis[l]==b[gg]){
            if(!solve(l+1,p,dis[p]-dis[l],gg)){flag=0;break;}
            l=p;
            gg++;
        }
        else if(dis[p]-dis[l]>b[gg]){flag=0;break;}
    }
    if(!flag||c!=d){
        puts("NO");
    }
    else {
        puts("YES");
        for(int i=0;i<cnt;i++){
            printf("%d %cn",g[i].id,g[i].ch);
        }
    }
    return 0;
}