一道很厉害的 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;
}
近期评论