CF1539E Game with Cards
看到题首先想到的是dp,记\(f_{0/1,i}\)表示第i个位置选左/右手是否可行,这样可以轻松转移了,从后往前推,如果满足以下条件则\(f_{0,i}\)=1(记转移的位置为j):
-
\(f_{1,j}\)=1
-
在[i+1,j]中都选右手可行 -> 记p∈[i+1,j] \(bl_{p}≤k_{p}≤br_{p}\)
-
在[i,j]中左手都为\(k_i\)可行 -> 记p∈[i,j] \(al_{p}≤k_{i}≤ar_{p}\)
右手亦然
于是你就会搞出来一个O(N^3)的dp,记个后缀就能变成O(N),然后考虑怎么继续优化
你会发现离i的最近f_{1/0,j}=1的j可以直接决定\(f_{0/1,j}\)的值,因为这样上面两个式子的限制最小
于是你就想到一个绝妙的做法,几下这个位置不就行了吗?然后就被一堆细节搞晕了
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mk make_pair
inline int read() {
int x(0),neg(1);char ch(getchar());
while(!isdigit(ch)) {if (ch=='-') neg=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*neg;
}
const int MAXN=2e5;
int n,m;
int f[MAXN+5];
int nxt[2][MAXN+5];
int k[MAXN+5],al[MAXN+5],ar[MAXN+5],bl[MAXN+5],br[MAXN+5];
int okl[MAXN+5],okr[MAXN+5];
int lstl,lstr,ll,lr,rl,rr;
int p[MAXN+5];
int ok1,ok2;
signed main() {
n=read(),m=read();
for (int i=1;i<=n;++i) k[i]=read(),al[i]=read(),ar[i]=read(),bl[i]=read(),br[i]=read();
for (int i=n;i>=1;--i) {
if (al[i]<=k[i] && k[i]<=ar[i]) okl[i]=1;
if (bl[i]<=k[i] && k[i]<=br[i]) okr[i]=1;
okl[i]+=okl[i+1],okr[i]+=okr[i+1];
}
ll=al[n],lr=ar[n],rl=bl[n],rr=br[n];
lstl=lstr=-1;
if (ll<=k[n] && k[n]<=lr) lstl=n,nxt[0][n]=lstl;
if (rl<=k[n] && k[n]<=rr) lstr=n,nxt[1][n]=lstr;
for (int i=n-1;i>=1;--i) {
ll=max(ll,al[i]),lr=min(lr,ar[i]),rl=max(rl,bl[i]),rr=min(rr,br[i]);
//can be put on the left hand
int llst=lstl,rlst=lstr,pll=ll,plr=lr,prl=rl,prr=rr;
if ((okr[i+1]-okr[rlst+1])==(rlst-i) && pll<=k[i] && k[i]<=plr) rl=bl[i],rr=br[i],nxt[0][i]=rlst,lstl=i;
//can be put on the right hand
if ((okl[i+1]-okl[llst+1])==(llst-i) && prl<=k[i] && k[i]<=prr) ll=al[i],lr=ar[i],nxt[1][i]=llst,lstr=i;
}
if (lstl==1) {
puts("Yes");
int now=1,cur=0,lst=2;
cout<<cur<<' ';
while(now!=0) {
for (int i=lst;i<=nxt[cur][now];++i) cout<<(cur^1)<<' ';
if (now==nxt[cur][now]) break;
now=nxt[cur][now];cur^=1;
lst=now+1;
}
}
else if (lstr==1) {
puts("Yes");
int now=1,cur=1,lst=2;
cout<<cur<<' ';
while(now!=0) {
for (int i=lst;i<=nxt[cur][now];++i) cout<<(cur^1)<<' ';
if (now==nxt[cur][now]) break;
now=nxt[cur][now];cur^=1;
lst=now+1;
}
}
else {
int flag1=1,flag2=1;
if (lstl==-1) flag1=0;
if (lstr==-1) flag2=0;
for (int i=1;i<=lstl;++i) {
if (!((al[i]<=k[i] && k[i]<=ar[i]) && (bl[i]==0))) {
flag1=0;
break;
}
}
for (int i=1;i<=lstr;++i) {
if (!((bl[i]<=k[i] && k[i]<=br[i]) && (al[i]==0))) {
flag2=0;
break;
}
}
if (!flag1 && !flag2) puts("No");
else if (flag1) {
puts("Yes");
int now=lstl,cur=0,lst=lstl+1;
for (int i=1;i<=lstl;++i) cout<<cur<<' ';
while(now!=0) {
for (int i=lst;i<=nxt[cur][now];++i) cout<<(cur^1)<<' ';
if (now==nxt[cur][now]) break;
now=nxt[cur][now];cur^=1;
lst=now+1;
}
}
else {
puts("Yes");
int now=lstr,cur=1,lst=lstr+1;
for (int i=1;i<=lstr;++i) cout<<cur<<' ';
while(now!=0) {
for (int i=lst;i<=nxt[cur][now];++i) cout<<(cur^1)<<' ';
if (now==nxt[cur][now]) break;
now=nxt[cur][now];cur^=1;
lst=now+1;
}
}
}
return 0;
}
然后看看我可爱的提交记录就知道(这题细节有多少了)我多菜了: