QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#499224 | #1281. Longest Common Subsequence | Hkueen | WA | 99ms | 20248kb | C++14 | 2.0kb | 2024-07-31 09:28:59 | 2024-07-31 09:28:59 |
Judging History
answer
/*
为什么我总会认为一些简单的题难
首先注意到字符集只有1~3
所以可以枚举i,j,表示选i个1和j个3,然后算中间2的个数
这个东西很好维护,对于两个序列,分别设l[i],r[i]表示从左往右第i个1的位置和从右往左第i个3的位置
然后再设s[i]表示前i个位置有几个2,就可以维护答案
也就是i+j+min(sa[ra[j]]-sa[la[i]],sb[rb[j]]-sb[lb[i]])
但是直接做是O(n^2)的。我们考虑优化
尝试在枚举i时维护合法的j
不难发现,随着i逐渐增大,会使得一些j不可用
双指针维护当前可用的最小的j,然后查区间最小的j+r[j]即可
*/
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+10,INF=0x3f3f3f3f;
int tr[N],n,m;
int lowbit(int x){return x&(-x);}
void add(int x,int v){++x;for(int i=x;i<=max(n,m)+1;i+=lowbit(i))tr[i]=max(tr[i],v);}//printf("add(%d,%d)\n",x-1,v);}
int sum(int x){
++x;
int res=-INF;
for(int i=x;i;i-=lowbit(i))res=max(res,tr[i]);
//printf("sum(%d)=%d\n",x-1,res);
return res;
}
int i,j,cnla,cnra,cnlb,cnrb,sa[N],sb[N],ans,a[N],b[N],la[N],lb[N],ra[N],rb[N];
void work(){
scanf("%d%d",&n,&m);
for(i=0;i<=max(n,m)+1;++i)tr[i]=-INF;
cnla=cnra=cnlb=cnrb=sa[0]=sb[0]=ans=0;
for(i=1;i<=n;++i)scanf("%d",a+i),sa[i]=sa[i-1]+(a[i]==2);sa[i]=sa[n];
for(i=1;i<=m;++i)scanf("%d",b+i),sb[i]=sb[i-1]+(b[i]==2);sb[i]=sb[m];
for(i=1;i<=n;++i)if(a[i]==1)la[++cnla]=i;
for(i=n;i;--i)if(a[i]==3)ra[++cnra]=i;ra[0]=n+1;
for(i=1;i<=m;++i)if(b[i]==1)lb[++cnlb]=i;
for(i=m;i;--i)if(b[i]==3)rb[++cnrb]=i;rb[0]=m+1;
for(i=0;i<=min(cnra,cnrb);++i)add(i,min(i+sa[ra[i]],i+sb[rb[i]]));
for(i=0,j=min(cnra,cnrb);i<=min(cnla,cnlb);++i){
while(la[i]>ra[j]||lb[i]>rb[j])--j;
int s=min(i+sum(j)-sa[la[i]],i+sum(j)-sb[lb[i]]);
//printf("i=%d j=%d s=min(%d,%d)\n",i,j,i+sum(j)-sa[la[i]],i+sum(j)-sb[lb[i]]);
ans=max(ans,s);
}
printf("%d\n",ans);
}
int T;
int main(){
scanf("%d",&T);
while(T--)work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 20248kb
input:
3 3 3 1 2 3 1 2 3 3 3 1 1 1 1 1 2 3 3 1 3 2 1 2 3
output:
3 2 2
result:
ok 3 tokens
Test #2:
score: -100
Wrong Answer
time: 99ms
memory: 18204kb
input:
139889 1 10 2 2 1 2 2 3 1 1 2 3 3 7 1 3 2 3 3 1 1 2 2 6 1 2 1 3 1 1 1 1 8 7 3 1 3 3 2 2 3 1 3 2 2 1 3 3 3 10 3 3 2 1 1 2 2 1 1 1 1 3 1 1 5 2 1 2 1 3 1 1 2 1 4 1 3 3 3 3 7 2 3 1 2 1 2 2 3 3 2 6 2 3 1 1 2 1 3 1 3 1 4 1 3 1 1 3 4 2 2 3 2 3 1 3 1 8 1 1 1 3 1 3 3 3 1 4 1 1 3 3 3 1 10 10 3 1 2 1 2 2 2 2 1...
output:
1 1 0 4 1 2 0 1 2 1 1 1 1 6 0 0 1 2 2 3 4 3 0 1 1 0 2 2 2 4 4 1 1 3 2 0 2 1 3 1 0 1 3 1 1 1 3 2 1 2 1 4 1 2 2 1 3 1 1 1 3 1 2 4 4 2 1 1 0 1 1 4 3 2 1 1 2 3 1 2 1 1 4 1 3 2 1 2 3 2 5 2 1 3 0 3 0 2 1 2 2 4 2 2 0 1 1 3 2 2 2 2 0 0 2 3 1 2 0 4 1 3 1 1 3 0 1 0 1 1 1 1 1 2 2 2 3 2 2 1 2 2 3 2 1 1 3 3 1 3 ...
result:
wrong answer 3rd words differ - expected: '1', found: '0'