QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#10184#305. 最长公共相似子序列问题hanyuwei80 951ms18980kbC++201.6kb2021-05-06 14:42:032023-08-25 00:54:10

Judging History

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

  • [2023-08-25 00:54:10]
  • 评测
  • 测评结果:80
  • 用时:951ms
  • 内存:18980kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-05-06 14:42:03]
  • 提交

answer

//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<ctime>
#define ll long long
#define inf 20021225
#define N 2010
#define db double
using namespace std;
int read()
{
    int s=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')    f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')    s=s*10+ch-'0',ch=getchar();
    return s*f;
}
int f[N][N],n,s[N],t[N],val[N]; char a[N],b[N]; bool vis[N];
int get(char c){return c=='A'?1:c=='C'?2:c=='G'?3:4;}
int get(int x)
{
	for(int j=1,k=x;j<=n;j++,k++)
	{
		if(k>n)	k=1;
		for(int i=1;i<=n;i++)
			f[j][i]=max(f[j-1][i-1]+(s[i]==t[k]),max(f[j][i-1],f[j-1][i]));
	}
	return f[n][n];
}
struct node{int v,x;};
bool operator<(node a,node b){return a.v<b.v;}
priority_queue<node> pos;
int main()
{
	//freopen("midnight.in","r",stdin); freopen("midnight.out","w",stdout);
	srand(20021225); n=read(); scanf("%s%s",a+1,b+1);
	for(int i=1;i<=n;i++)	s[i]=get(a[i]),t[i]=get(b[i]);
	if(n<=600){int ans=0; for(int i=1;i<=n;i++)	ans=max(ans,get(i)); printf("%d\n",ans); return 0;}
	int cc=n/100,ans=0;
	while(cc--)
	{
		int x=rand()%n+1; while(vis[x])	x=rand()%n+1;
		vis[x]=1; ans=max(val[x]=get(x),ans);
		pos.push((node){val[x],x}); 
	}
	while(!pos.empty() && (db)clock()/CLOCKS_PER_SEC<0.95)
	{
		int x=pos.top().x; pos.pop(); int y=x+1;
		if(y<=n && !vis[y])	ans=max(val[y]=get(y),ans),vis[y]=1,pos.push((node){val[y],y});
		y=x-1; if(y>=1 && !vis[y])	ans=max(val[y]=get(y),ans),vis[y]=1,pos.push((node){val[y],y});
	}
	printf("%d\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 3200kb

input:

10
TACCAAAAGC
ATTCTTCTAT

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 10
Accepted
time: 68ms
memory: 4640kb

input:

300
AAGGTTCCTGTATTCATTGCATTGCTGAACTACGACCGAGAAATGCAGGCCCGTGGTGAATACATTGCCAGCACACAGTATAAGGTTACCAGCGGTACATGTTTCTAGAAGGCACATTGGGCGGCCCCGACTGGCGGAGACGACGATAACTCTTCGCTCACGTTTACAATGTCTACCGTAGCACTGATGAGGTTTTGTCCCGGGGCTCATAACAAGACTGTAATATACAAACCCACGGTATGCACGGACTACCGATGAGACACACAGCTTACCTGCGCACAAAGCAGTATGGAAAC...

output:

197

result:

ok 1 number(s): "197"

Test #3:

score: 10
Accepted
time: 72ms
memory: 4592kb

input:

300
AGGAGTTATCGTTAGAGGTTTCCCAATTGGACGCCTAGATTAGGAAGGGCACCGACAACAGCTGTCCTAAAGCTACGGGCGCCTATAATGAACACTGAACGTTGCGCCAGTGTCGCGCCCTACCCTGTCCGCGCCGTAGGATTGTCTCAGTCCTTTATGTAAGACTTGCGAAGTCCGTATCCGACAACATATTAGAAACAGATAAGTCGACGGCGAGCGTTGGAACAATCTATCGCGCCTGCCTTAATCCAGCCTGCGTATAAGGTACACGCCCGTTTGATCGCGTTTGTTTATCG...

output:

202

result:

ok 1 number(s): "202"

Test #4:

score: 10
Accepted
time: 69ms
memory: 4636kb

input:

300
TCATAAGTTCCTTGTTTAAGAACAAAGATCAAGGTTCTCCTCCCTGCGACAGGCTGTGACCCCGAACACCTATAGCGTCTTGGCGGAGCGGCTGTTTACACAGGGGCGCTGTTCAATCGATCGATCTCTCGCCGAGTCTGAGTAGCTACTCAAGTCCTTGGTTAGGGAGTCCAACAGAGGACCTGTTGTGACAGATCCTGGTGGAGCTATTAACAGAGTTGCACGTCTCCTATCCTCATCCAAAGTCTGCCCGGGTGGATTGCATGCTGTCCCTAGATAGACGACGTCGCCTACGC...

output:

199

result:

ok 1 number(s): "199"

Test #5:

score: 10
Accepted
time: 939ms
memory: 11012kb

input:

1000
ATTTAGCAGCAGGGAAGTTCAATGGACTCGGGCCGAAACCCGGGTGCGCGTCGCCCGAATACAACGTATCCAGCTGAACAGCCGCCCTACGCACGGTCATGTTGGCACCGGAAGCAATGAATACGGGTCCTAGGTGCCATCGTCACAGGTAAAGATATAGGTCTGACGGGTGGACCTGGGTTTCCCTCGGTGCGATCCCAAGAGCGAATATGCATTGCTTTACGCTCCCTATGTTTAAGCTACGTCCTGACCAAGAGACCCTATCGTTGGTGGCATCGCGAATTACTCTGCTCAT...

output:

657

result:

ok 1 number(s): "657"

Test #6:

score: 0
Wrong Answer
time: 942ms
memory: 11120kb

input:

1000
TCTGCTTTGTGCCAATATCTGACAAGAACACGCCGTGGCGGGTCTTCATATTCGCCCGGACCCATCACGGTATCTTACTGTAGACCGAGATTTGTACATTTCAACCTATACAGGGTCTGGGACGCACTCGTGACTAAAATTTCGTACTTTAGTCAGCACGGGACGCGAGGAGAACATCAAATAATCCTTGATGCAGGCATCTCATCCTTGTCTCCATCTGCGATAAGAGCAATGGGAACATTCCTCCTAAGCGCCGAGTTAAAACGGACAAAAGCCTCCCCGGTCAGTATTGGTG...

output:

652

result:

wrong answer 1st numbers differ - expected: '653', found: '652'

Test #7:

score: 10
Accepted
time: 947ms
memory: 11088kb

input:

1000
GTGTGGGCGTGGGTAGTGCTATCCTCATCCACGATTTCTGCCGGCTCGTTTGTACGCCGGCGTTCGCAGATATTCCGGGTATCGAACTATCATTGATAATCATACGTAAACGCAAGAGCTGGAGTCTTCTTAGAAGGATACGGATGGTGGGGGGTGCCCTCGTGCCAACGGTTTGTGTCACAACACACGTTTTCGACGTCCTCTGAGGGCATTACTGATTGACGGATCATTCTCGTCAACGGCCAGCGCAGGGGACCTACTTAGGGACTTGCCGATCCTGTAGAACTTCGGATCT...

output:

656

result:

ok 1 number(s): "656"

Test #8:

score: 10
Accepted
time: 949ms
memory: 18960kb

input:

2000
TTCATGCGCTCAGCCTGGCTTGAGGCACACGGAGGTGCGCCGCAAACACCTGTTGACTCAAGGGAGCCGACTGCTTGCTGATTCAAATATAATATCTGGGTGAGTTTAACAGTCTCTGTATTAGCGGTGCGGCCTTGTTCAAAGTTACTCGTGATAACCCCACGCTGAAAGACTTCGTACTTTCCCAAGGTTTTGATAGACTCTGAGGGAACTCGGACCAGCCTTTTTCCCTCTGGCGAGGAGAGGCCGGACTCTTTTTGGGAGGCACCTCTTAGCTTCGCCTTCTACGCACCAA...

output:

1307

result:

ok 1 number(s): "1307"

Test #9:

score: 0
Wrong Answer
time: 951ms
memory: 18980kb

input:

2000
AGTACTCACTAGAGAATCCCCGACCACCCAAGTATTACAAACGAATGGAGATTTCTCTTTGTTACCGCTGCGATGCAGCGGCCACCCGATTTGTTGCTCTGGCCACTATTGGAGTTACAGTGTGGAGCACGCTAGACCGTGGCCTGTGGAAGCGTGCTGCCCCAAACGTAAGAACGAACTTATTCGGCTGCAATTCATCGGGCAGGGCGTTACGGCGTACGAGGGCAAGACAAGGTAGGTCCCGCGGACACACTTGCCTATGCCGTAGGAACATGACAATATGAAGATCGGTACC...

output:

1307

result:

wrong answer 1st numbers differ - expected: '1311', found: '1307'

Test #10:

score: 10
Accepted
time: 948ms
memory: 18944kb

input:

2000
GACAACCCCCGTCCATCGGCCTCATAATAAGGGGTGCTGATTTGAAAGTTTTTTCCACTACTGCAGTGAAGCTCTTAGCTGCCGTGTTGACCGCCGCCCTACCAAAGCGAATACAAGCTACTAAACTTCGGACAATAGGATTGCATTCCAGCCAGTGAACGTACGGCACTGTCAGAGTTGCCGACTGATGTCGCGTTGAGTTAGGGCCATGGTCTCGATCTAGCAAGACGGTCACTTTCTTATCTTTCGTGACGGCTAATGTATTTTTGTACAGTGGTCTAAGAAACTTAGTTAG...

output:

1316

result:

ok 1 number(s): "1316"