QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#499233#1281. Longest Common SubsequenceHkueenWA 108ms22188kbC++142.3kb2024-07-31 09:54:092024-07-31 09:54:09

Judging History

你现在查看的是最新测评结果

  • [2024-07-31 09:54:09]
  • 评测
  • 测评结果:WA
  • 用时:108ms
  • 内存:22188kb
  • [2024-07-31 09:54:09]
  • 提交

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=1e6+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(t1,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: 22188kb

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: 108ms
memory: 20244kb

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
1
2
0
1
2
1
1
1
1
6
1
0
1
2
2
3
4
4
1
1
1
0
2
2
3
5
4
1
1
3
2
0
2
1
3
1
1
1
3
1
1
1
3
2
1
2
1
4
1
2
2
1
3
1
1
2
3
1
3
4
4
2
2
1
0
1
2
4
3
2
1
1
2
3
1
2
2
1
4
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
4
0
0
2
3
1
2
0
5
1
4
1
1
3
0
1
0
1
1
1
1
3
2
2
2
3
2
3
1
2
2
3
2
1
1
3
3
2
3
...

result:

wrong answer 5th words differ - expected: '2', found: '1'