QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#697881#7780. Dark LaTeX vs. Light LaTeX123456zmyAC ✓1362ms346940kbC++171.8kb2024-11-01 16:14:312024-11-01 16:14:32

Judging History

你现在查看的是测评时间为 2024-11-01 16:14:32 的历史记录

  • [2024-11-25 21:19:41]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1367ms
  • 内存:347036kb
  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-11-01 16:14:32]
  • 评测
  • 测评结果:100
  • 用时:1362ms
  • 内存:346940kb
  • [2024-11-01 16:14:31]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
    function<short(vector<vector<short>>&v,string& a, int x, string& b, int y)>
		lcp = [&](vector<vector<short>>&v,string& a, int x, string& b, int y) {
    	if(x>=a.size()||y>=b.size())return (short)0;
		if(v[x][y]!=-1)return v[x][y];
		if(a[x]==b[y])return v[x][y]=(short)1+lcp(v,a,x+1,b,y+1);
		else return v[x][y]=0;
    };
    string s,t;
    cin>>s>>t;
    s=" "+s,t=" "+t;
    vector<vector<short>>cnts(s.size()+1,vector<short>(s.size()+1));
    vector<vector<short>>cntt(t.size()+1,vector<short>(t.size()+1));
	vector<vector<short>>anss=cnts,anst=cntt;
	vector<vector<short>>ss(s.size()+1,vector<short>(s.size()+1,-1));
	vector<vector<short>>st(s.size()+1,vector<short>(t.size()+1,-1));
	vector<vector<short>>tt(t.size()+1,vector<short>(t.size()+1,-1));
	for(int i=1;i<s.size();i++)
	{
		for(int j=1;j<t.size();j++)
		{
			int tmp=lcp(st,s,i,t,j);
			++cnts[i][i];
			--cnts[i][i+tmp];
			++cntt[j][j];
			--cntt[j][j+tmp];
		}
	}
	for(int i=1;i<s.size();i++)
	{
		for(int j=i+1;j<s.size();j++)
		{
			int tmp=min((short)(j-i),lcp(ss,s,i,s,j));
			++anss[i][j-1];
			--anss[i+1+tmp][j-1];
		}
		++anss[i][s.size()-1];
		--anss[i+1][s.size()-1];
	}
	for(int i=1;i<t.size();i++)
	{
		for(int j=i+2;j<t.size();j++)
		{
			int tmp=min((short)(j-i),lcp(tt,t,i,t,j));
			++anst[i+1][j-1];
			--anst[i+1+tmp][j-1];
		}
	}
	int ans=0;
	for(int i=1;i<s.size();i++)
		for(int j=i;j<s.size();j++)
			cnts[i][j]+=cnts[i][j-1],
			anss[i][j]+=anss[i-1][j],
			ans+=1ll*cnts[i][j]*anss[i][j];
	for(int i=1;i<t.size();i++)
		for(int j=i;j<t.size();j++)
			cntt[i][j]+=cntt[i][j-1],
			anst[i][j]+=anst[i-1][j],
			ans+=1ll*cntt[i][j]*anst[i][j];
	printf("%lld\n",ans);
}

signed main()
{
	solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 1362ms
memory: 346908kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 17ms
memory: 17784kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 17ms
memory: 17792kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: 0
Accepted
time: 584ms
memory: 346932kb

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:

2655796915

result:

ok 1 number(s): "2655796915"

Test #10:

score: 0
Accepted
time: 589ms
memory: 346940kb

input:

ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...

output:

2652657341

result:

ok 1 number(s): "2652657341"

Test #11:

score: 0
Accepted
time: 588ms
memory: 346912kb

input:

uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...

output:

2619083676

result:

ok 1 number(s): "2619083676"

Test #12:

score: 0
Accepted
time: 20ms
memory: 17784kb

input:

ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...

output:

61227979

result:

ok 1 number(s): "61227979"

Test #13:

score: 0
Accepted
time: 208ms
memory: 127364kb

input:

cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...

output:

834307544

result:

ok 1 number(s): "834307544"

Test #14:

score: 0
Accepted
time: 566ms
memory: 346932kb

input:

trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...

output:

2663862697

result:

ok 1 number(s): "2663862697"

Test #15:

score: 0
Accepted
time: 30ms
memory: 18164kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 558ms
memory: 346616kb

input:

igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...

output:

1707132

result:

ok 1 number(s): "1707132"

Test #17:

score: 0
Accepted
time: 26ms
memory: 17808kb

input:

jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...

output:

2954810

result:

ok 1 number(s): "2954810"

Test #18:

score: 0
Accepted
time: 14ms
memory: 17744kb

input:

juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...

output:

40401

result:

ok 1 number(s): "40401"

Test #19:

score: 0
Accepted
time: 473ms
memory: 346672kb

input:

lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...

output:

1421341

result:

ok 1 number(s): "1421341"

Test #20:

score: 0
Accepted
time: 29ms
memory: 18108kb

input:

cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...

output:

3118221

result:

ok 1 number(s): "3118221"

Test #21:

score: 0
Accepted
time: 752ms
memory: 346664kb

input:

srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...

output:

75529025

result:

ok 1 number(s): "75529025"

Test #22:

score: 0
Accepted
time: 526ms
memory: 346624kb

input:

onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...

output:

3326939

result:

ok 1 number(s): "3326939"

Test #23:

score: 0
Accepted
time: 25ms
memory: 18036kb

input:

etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...

output:

547040

result:

ok 1 number(s): "547040"

Test #24:

score: 0
Accepted
time: 34ms
memory: 17800kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

38791844792

result:

ok 1 number(s): "38791844792"

Test #25:

score: 0
Accepted
time: 348ms
memory: 127284kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

4804791846049

result:

ok 1 number(s): "4804791846049"

Test #26:

score: 0
Accepted
time: 850ms
memory: 346520kb

input:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

10043476749324

result:

ok 1 number(s): "10043476749324"

Test #27:

score: 0
Accepted
time: 375ms
memory: 241184kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269398620

result:

ok 1 number(s): "269398620"

Test #28:

score: 0
Accepted
time: 396ms
memory: 246996kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269769773

result:

ok 1 number(s): "269769773"

Test #29:

score: 0
Accepted
time: 382ms
memory: 246880kb

input:

baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...

output:

287077563

result:

ok 1 number(s): "287077563"

Extra Test:

score: 0
Extra Test Passed