一道很厉害的 DP 题，考场上被卡了。

题目链接：LibreOJ 3271/JOISC2020 D1T1。

[toc]

题目

题目描述

挂上原题 pdf。

给定长度为 $2N$ 的两个序列，分别为序列 $\text{A}$，和序列 $\text{B}$。

构造一个长度为 $2N$ 的序列 $\text{C}$。满足以下条件：

• 序列 $\text{C}$ 的第 $i$ 个数 $C_i$，只能从 $A_i$ 和 $B_i$ 中选取。
• 设 $a$ 为序列 $\text{A}$ 中元素被选取的次数，$b$ 为序列 $\text{B}$ 中元素被选取的次数，则 $a=b=N$。
• 该序列是一个单调上升的序列，不要求严格单调上升。

如有多解，任意输出一组解即可。

数据范围

$$1\leq N\leq 5\times 10^5$$

$$1\leq A_i,B_i\leq 10^9$$

时空限制

$$1.5\text{s}/512\text{MiB}$$

题解

思路

设 $l_{0,i}$ 表示从第一个 $a_1$ 开始构造数列到第 $i$ 项，最少用上 $l_{0,i}$ 个 $a_i$，
设 $r_{0,i}$ 表示从第一个 $a_1$ 开始构造数列到第 $i$ 项，最多用上 $r_{0,i}$ 个 $a_i$。
设 $l_{1,i}$ 表示从第一个 $b_1$ 开始构造数列到第 $i$ 项，最少用上 $l_{1,i}$ 个 $a_i$，
设 $r_{1,i}$ 表示从第一个 $b_1$ 开始构造数列到第 $i$ 项，最多用上 $r_{1,i}$ 个 $a_i$。

判断可行性就很简单了，求答案搜索即可。

代码

时间复杂度为 $\Theta(n)$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=500000+5;

int n;
int a[MAXN<<1],b[MAXN<<1];
int l[2][MAXN<<1],r[2][MAXN<<1];

inline void DFS(reg int type,reg int last,reg int cnt){
    if(last==0)
        return;
    if(cnt<0)
        exit(0);
    if(type==0){
        if(l[0][last-1]<=cnt-1&&cnt-1<=r[0][last-1]&&a[last-1]<=a[last])
            DFS(0,last-1,cnt-1);
        else
            DFS(1,last-1,cnt-1);
        putchar('A');
    }
    else{
        if(l[0][last-1]<=cnt&&cnt<=r[0][last-1]&&a[last-1]<=b[last])
            DFS(0,last-1,cnt);
        else
            DFS(1,last-1,cnt);
        putchar('B');
    }
    return;
}

int main(void){
    n=read();
    for(reg int i=1;i<=(n<<1);++i)
        a[i]=read();
    for(reg int i=1;i<=(n<<1);++i)
        b[i]=read();
    memset(l,0X3F,sizeof(l)),memset(r,-1,sizeof(r));
    l[0][1]=r[0][1]=1,l[1][1]=r[1][1]=0;
    for(reg int i=2;i<=(n<<1);++i){
        if(a[i]>=a[i-1])
            l[0][i]=min(l[0][i],l[0][i-1]+1),r[0][i]=max(r[0][i],r[0][i-1]+1);
        if(a[i]>=b[i-1])
            l[0][i]=min(l[0][i],l[1][i-1]+1),r[0][i]=max(r[0][i],r[1][i-1]+1);
        if(b[i]>=a[i-1])
            l[1][i]=min(l[1][i],l[0][i-1]),r[1][i]=max(r[1][i],r[0][i-1]);
        if(b[i]>=b[i-1])
            l[1][i]=min(l[1][i],l[1][i-1]),r[1][i]=max(r[1][i],r[1][i-1]);
        if(l[0][i]>r[0][i]&&l[1][i]>r[1][i]){
            puts("-1");
            return 0;
        }
    }
    if(l[0][n<<1]<=n&&n<=r[0][n<<1]){
        DFS(0,n<<1,n);
        putchar('\n');
        return 0;
    }
    if(l[1][n<<1]<=n&&n<=r[1][n<<1]){
        DFS(1,n<<1,n);
        putchar('\n');
        return 0;
    }
    puts("-1");
    return 0;
}