QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#499236 | #1281. Longest Common Subsequence | Hkueen | RE | 124ms | 24516kb | C++14 | 2.3kb | 2024-07-31 09:58:03 | 2024-07-31 09:58:03 |
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;
服了,应该要讨论哪边更小来算
*/
#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e6+10,INF=0x3f3f3f3f;
int t1[N],t2[N],n,m;
int lowbit(int x){return x&(-x);}
void add(int *tr,int x,int v){for(int i=x;i<=n+m<<1;i+=lowbit(i))tr[i]=max(tr[i],v);}//printf("add(%d,%d)\n",x-1,v);}
int sum(int *tr,int 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<=n+m<<1;++i)t1[i]=t2[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=-1,j=min(cnra,cnrb);~j;--j){
while(i<min(cnla,cnlb)&&la[i+1]<ra[j]&&lb[i+1]<rb[j]){
++i;
add(t1,sb[lb[i]]-sa[la[i]]+n+m,i-sa[la[i]]);
add(t2,sa[la[i]]-sb[lb[i]]+n+m,i-sb[lb[i]]);
}
ans=max({ans,sum(t1,sb[rb[j]]-sa[ra[j]]+n+m)+j+sa[ra[j]],sum(t2,sa[ra[j]]-sb[rb[j]]+n+m)+j+sb[rb[j]]});
}
printf("%d\n",ans);
}
int T;
int main(){
scanf("%d",&T);
while(T--)work();
return 0;
}
//怒发冲冠,凭栏处,潇潇雨歇。抬望眼,仰天长啸,壮怀激烈。
//三十功名尘与土,八千里路云和月。莫等闲,白了少年头,空悲切。
//靖康耻,犹未雪;臣子恨,何时灭?驾长车,踏破贺兰山缺。
//壮志饥餐胡虏肉,笑谈渴饮匈奴血。待从头,收拾旧山河,朝天阙!
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22204kb
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: 0
Accepted
time: 108ms
memory: 20344kb
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 1 4 2 2 0 1 2 1 1 1 1 6 1 0 1 2 2 3 4 4 1 1 1 0 2 2 3 4 4 1 1 3 2 1 2 1 3 1 1 1 3 1 1 2 3 2 1 3 1 4 1 2 2 1 3 1 1 2 3 1 2 4 4 2 2 1 1 1 2 4 3 2 1 1 2 3 1 2 2 1 5 2 4 2 1 2 3 2 5 2 1 3 1 3 1 2 1 2 2 4 3 2 0 1 1 3 2 3 2 2 0 0 2 3 1 2 0 4 1 4 1 1 3 1 1 0 1 1 1 1 3 2 2 2 3 3 3 1 2 2 3 2 1 1 3 3 2 3 ...
result:
ok 139889 tokens
Test #3:
score: 0
Accepted
time: 124ms
memory: 22280kb
input:
100000 10 10 1 1 1 3 1 2 1 1 1 1 3 1 1 2 1 2 2 2 1 3 10 10 1 1 3 2 3 1 1 2 3 2 3 3 1 3 2 1 1 1 2 1 10 10 2 2 3 3 1 2 3 1 3 2 2 3 2 3 2 1 2 3 3 1 10 10 3 3 1 1 1 3 2 3 2 2 2 2 1 2 2 2 2 2 3 3 10 10 3 3 3 2 1 3 3 1 3 1 1 3 1 1 3 2 1 1 1 3 10 10 1 1 2 1 3 1 1 3 1 3 2 1 1 1 1 3 2 1 2 2 10 10 2 2 3 1 2 2...
output:
4 5 5 4 4 5 4 5 4 7 4 5 5 4 4 5 4 6 6 6 3 4 4 4 5 4 4 4 6 4 5 5 5 3 5 6 5 4 4 4 4 5 5 3 4 4 3 7 3 4 5 4 4 4 3 5 5 5 4 6 5 3 5 5 3 3 3 5 3 4 4 5 4 4 3 4 5 6 5 6 7 5 4 5 4 4 6 5 4 5 6 5 4 3 3 4 3 4 4 4 4 4 5 4 5 5 5 4 2 6 3 5 5 5 5 4 4 4 4 4 5 5 4 4 5 6 5 4 3 4 4 4 3 4 3 3 4 5 5 3 4 6 4 3 4 5 6 5 5 5 ...
result:
ok 100000 tokens
Test #4:
score: 0
Accepted
time: 112ms
memory: 22344kb
input:
59509 16 16 3 3 3 2 3 3 1 3 1 2 1 1 3 1 3 2 3 3 3 1 1 3 1 1 2 2 2 2 3 3 1 1 16 17 2 1 1 1 3 1 1 2 3 3 2 1 2 3 3 3 1 1 3 1 1 1 1 1 1 3 2 3 2 1 3 1 3 19 10 1 1 3 3 2 1 1 2 3 1 2 3 3 1 3 1 2 1 1 3 1 1 3 1 1 1 2 2 1 10 14 3 3 3 1 1 3 3 1 3 1 3 1 3 2 2 3 3 1 1 3 1 3 3 3 12 20 1 1 2 2 1 1 2 1 1 2 3 1 1 1 ...
output:
6 10 7 6 8 4 6 6 7 6 6 7 5 8 8 5 8 5 8 5 5 7 6 5 5 7 6 6 8 7 5 6 6 4 7 7 6 5 7 7 7 9 5 5 8 9 7 7 6 11 8 5 7 9 6 7 8 5 5 6 6 8 8 6 9 8 4 6 7 8 7 5 8 4 5 6 8 8 5 6 6 7 7 8 5 6 7 6 7 5 10 10 6 6 8 6 6 7 5 7 5 6 6 7 3 6 10 5 6 7 7 8 7 4 4 5 7 5 7 7 6 5 6 8 6 8 6 6 7 7 8 4 4 6 7 6 5 5 6 7 8 9 6 8 7 9 8 8...
result:
ok 59509 tokens
Test #5:
score: 0
Accepted
time: 116ms
memory: 22316kb
input:
50000 20 20 1 3 3 2 1 2 1 1 1 2 3 2 1 2 2 2 2 2 1 3 3 2 2 1 3 3 1 2 3 2 1 2 2 3 2 3 1 3 2 1 20 20 1 3 2 3 2 2 1 1 1 3 3 2 2 2 3 3 3 3 3 1 2 3 2 3 1 2 1 2 2 2 1 3 1 3 1 2 3 2 3 1 20 20 1 3 1 1 2 3 1 2 2 3 3 1 2 1 1 1 2 2 1 2 2 1 1 2 2 2 1 1 1 3 1 1 3 1 2 1 2 2 3 1 20 20 3 3 3 2 1 2 2 2 1 2 2 2 2 2 3 ...
output:
8 10 11 8 7 8 9 9 9 8 7 9 9 8 8 10 8 8 10 9 8 8 8 10 9 8 9 9 8 7 5 7 8 7 9 9 9 7 10 11 12 12 8 10 11 10 9 9 10 8 8 8 9 10 8 9 9 10 9 8 8 8 10 8 9 11 9 6 9 6 9 8 8 11 9 10 9 8 8 9 10 9 9 7 9 9 9 8 9 11 6 8 8 8 8 9 9 8 9 7 8 7 6 8 10 9 9 10 8 9 8 9 11 9 8 7 8 8 10 11 6 8 9 9 8 7 9 9 10 9 7 10 8 9 9 8 ...
result:
ok 50000 tokens
Test #6:
score: 0
Accepted
time: 103ms
memory: 22352kb
input:
11967 85 68 1 2 2 2 1 3 3 1 3 3 1 2 2 1 1 2 1 2 1 3 2 2 3 2 3 1 2 3 1 2 3 2 1 1 2 1 3 1 2 3 2 1 2 2 1 2 3 2 2 1 1 1 3 2 2 2 2 3 2 1 3 3 1 3 2 3 1 2 3 2 1 2 1 3 2 3 3 2 2 3 2 2 1 1 2 1 3 3 1 2 1 1 1 2 1 2 3 1 1 3 2 1 3 3 1 1 3 1 1 3 2 2 1 2 1 1 2 3 3 2 1 2 2 3 2 1 2 3 1 3 3 3 1 3 1 3 1 3 3 1 1 3 1 2 ...
output:
32 29 25 37 25 29 22 27 31 31 22 22 31 37 23 29 27 29 22 31 26 30 25 28 26 27 24 26 25 25 28 30 23 33 33 24 21 29 23 35 26 36 26 23 24 33 31 28 25 22 31 35 32 35 26 25 30 35 28 36 27 25 25 28 33 26 30 27 23 35 32 36 30 28 26 30 31 33 28 24 33 36 21 30 33 33 29 29 22 22 29 27 20 38 29 31 30 35 34 39 ...
result:
ok 11967 tokens
Test #7:
score: 0
Accepted
time: 113ms
memory: 22336kb
input:
10000 100 100 2 3 2 2 2 3 2 3 1 1 2 2 2 2 1 2 3 3 3 2 3 3 1 3 3 2 2 3 1 1 3 3 2 3 1 3 3 1 2 2 2 3 1 2 3 1 2 2 3 3 1 1 3 1 3 1 2 2 2 2 2 3 2 1 3 1 2 2 1 2 1 2 1 2 3 2 3 1 3 2 2 1 2 1 2 3 1 3 2 1 3 3 2 2 1 1 3 1 1 2 3 1 1 2 1 1 1 3 3 2 3 3 3 2 1 3 3 2 2 2 1 3 1 3 1 3 1 2 2 1 1 2 3 2 3 3 2 1 3 2 3 3 3 ...
output:
38 40 34 35 39 40 38 40 39 39 36 38 42 41 39 37 42 43 35 37 36 34 39 40 41 40 33 36 38 38 42 38 40 42 44 42 35 41 35 44 39 45 36 37 39 38 40 40 35 37 39 39 40 43 42 37 41 41 39 44 43 35 40 41 37 40 39 39 36 38 40 39 38 39 37 35 40 40 41 38 36 42 41 38 38 38 34 43 37 36 40 39 41 46 38 42 40 37 47 39 ...
result:
ok 10000 tokens
Test #8:
score: 0
Accepted
time: 110ms
memory: 22260kb
input:
1000 1000 1000 3 1 3 3 3 2 3 1 3 2 1 1 3 1 2 2 3 3 1 2 2 3 3 3 3 1 3 3 3 1 1 2 2 1 1 2 1 2 2 2 1 3 1 3 1 1 1 2 3 1 3 1 3 1 1 2 1 1 1 3 1 2 1 1 2 3 2 2 2 1 1 2 2 1 2 2 3 3 2 1 1 2 2 3 1 3 2 1 2 3 3 1 3 2 2 3 2 1 1 3 3 3 1 3 1 2 2 3 1 3 3 3 1 3 2 3 2 3 2 1 2 1 1 1 1 3 1 3 1 2 3 3 1 1 3 3 2 3 3 2 1 1 3...
output:
366 357 362 343 351 343 357 344 343 357 343 348 353 354 358 346 349 357 347 357 344 349 353 356 354 358 350 361 356 342 353 362 350 350 351 353 364 355 355 361 348 349 354 354 347 345 346 361 349 338 360 344 353 339 351 344 343 352 345 354 335 359 355 351 350 355 354 342 347 347 356 358 364 356 351 ...
result:
ok 1000 tokens
Test #9:
score: 0
Accepted
time: 114ms
memory: 24304kb
input:
100 10000 10000 2 2 2 3 2 3 3 2 2 1 1 1 3 3 2 3 2 3 1 2 1 2 2 1 3 2 1 3 1 3 3 2 2 2 2 2 1 3 3 3 2 3 1 3 3 3 2 1 1 2 2 1 2 1 1 3 1 2 3 1 1 3 3 2 1 3 2 2 2 3 3 3 1 2 2 1 3 1 1 3 3 1 3 2 2 2 2 2 1 1 1 2 3 2 2 1 2 2 1 2 3 3 2 3 3 3 1 3 1 3 3 3 2 1 1 2 1 3 1 3 2 2 1 1 2 1 3 3 2 3 3 3 1 2 2 1 3 2 1 3 2 1 ...
output:
3431 3388 3380 3406 3403 3366 3399 3389 3390 3374 3389 3356 3419 3423 3348 3392 3366 3392 3411 3398 3436 3429 3371 3410 3414 3366 3377 3406 3384 3391 3391 3421 3400 3409 3412 3407 3429 3405 3444 3381 3414 3398 3437 3390 3381 3397 3396 3399 3412 3382 3403 3368 3393 3445 3410 3396 3393 3430 3416 3391 ...
result:
ok 100 tokens
Test #10:
score: 0
Accepted
time: 115ms
memory: 24516kb
input:
10 100000 100000 3 1 2 2 1 1 1 3 2 3 1 3 3 1 2 3 1 2 3 3 3 2 3 3 3 3 2 1 1 3 3 1 1 2 3 1 2 3 1 2 2 2 3 3 2 1 1 3 3 1 2 3 3 2 3 3 3 3 1 2 1 3 1 3 3 2 2 2 3 3 3 2 1 1 2 1 3 1 3 2 3 3 3 3 2 3 1 2 2 2 2 3 2 3 1 3 3 1 3 3 1 1 3 2 1 3 1 3 3 3 3 3 2 1 1 2 2 3 1 3 2 3 3 3 2 2 3 1 3 2 1 3 1 2 3 2 2 1 3 3 2 1...
output:
33573 33651 33656 33615 33599 33519 33490 33488 33510 33572
result:
ok 10 tokens
Test #11:
score: -100
Runtime Error
input:
1 1000000 1000000 1 3 2 3 1 1 2 2 2 1 2 1 3 1 1 2 2 3 2 1 3 1 1 1 3 2 2 1 1 1 2 1 2 3 3 1 2 1 2 3 3 2 1 1 1 1 1 2 2 3 2 3 2 1 3 3 1 2 2 3 1 3 3 3 2 3 2 1 2 1 2 3 2 2 1 1 1 3 1 3 2 1 1 3 1 1 2 1 1 3 3 2 1 2 3 3 3 2 1 3 3 2 3 1 1 1 1 3 3 2 3 2 1 1 2 1 3 3 3 3 3 3 2 3 1 3 2 1 2 3 1 2 3 2 2 3 3 1 1 1 1 ...