QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302429#7780. Dark LaTeX vs. Light LaTeXzzuqyML 1365ms461108kbC++142.9kb2024-01-10 21:11:022024-01-10 21:11:03

Judging History

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

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-01-10 21:11:03]
  • 评测
  • 测评结果:ML
  • 用时:1365ms
  • 内存:461108kb
  • [2024-01-10 21:11:02]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <deque>
#include <unordered_map>
#include <map>
#define P 31525197391593473ll
#define ll long long
#define l(p) t[p].l
#define sum(p) t[p].sum
#define cnt(p) t[p].cnt
#define r(p) t[p].r
#define mod 998244353
#define sc(A) scanf("%d",&A)
#define rep(A,B,C) for(int C=A;C<=B;++C)
#define fep(A,B,C) for(int C=A;C>=B;--C)
#define put(x) printf("%d\n",x)
#define db double
using namespace std;
const int MAXN = 5010,N=40000007,base1=29;
int n, m, q, x, maxx = 62, top;

char a[MAXN], b[MAXN];
int nex[MAXN];
int w[MAXN];
int c1[MAXN][MAXN];
int c2[MAXN][MAXN];
struct wy
{
	int lin[N],nex[MAXN*MAXN],e[MAXN*MAXN];
	ll ver[MAXN*MAXN];
	int len=0;
	inline void add(ll y)
	{
		int x=y%N;
		ver[++len]=y;
		nex[len]=lin[x];
		lin[x]=len;
		e[len]=1;
	}
	int find(ll y,int w)
	{
		int x=y%N;
		for(int i=lin[x];i;i=nex[i])
		{
			ll tn=ver[i];
			if(tn==y){e[i]+=w;return e[i];}
		}
		return 0;
	}
	void clear(){
		fill(lin,lin+N,0);len=0;
		/*
		fill(nex,nex+MAXN*MAXN,0);
		fill(e,e+MAXN*MAXN,0);
		fill(ver,ver+MAXN*MAXN,0);*/ 
	} 
}H;

signed main() {
	//freopen("1.in", "r", stdin);
	//freopen("1.out", "w", stdout);
	scanf("%s", a + 1);
	scanf("%s", b + 1);
	int n = strlen(a + 1);
	int m = strlen(b + 1);
	rep(1, n, i) {
		ll s1 = 0;
		rep(i, n, j) {
			s1 = ((ll)s1 * base1 + a[j]) % P;
			if(H.find(s1,1)==0)H.add(s1);
		}
	}

	ll ans = 0;
	rep(1, m, i) {
		ll s1 = 0;
		rep(i, m, j) {
			s1 = ((ll)s1 * base1 + b[j]) % P;
			c2[i][j]=H.find(s1,0);
			ans +=c2[i][j];
		}
	}
	H.clear();
	rep(1, m, i) {
		ll s1 = 0;
		rep(i, m, j) {
			s1 = ((ll)s1 * base1 + b[j]) % P;
			if(H.find(s1,1)==0)H.add(s1);
		}
	}

	rep(1, n, i) {
		ll s1 = 0;
		rep(i, n, j) {
			s1 = ((ll)s1 * base1 + a[j]) % P;
			c1[i][j] = H.find(s1,0);
		}
	}


	int now;
	rep(2, n-1, j) {
		now=j;
		w[j + 1] = 1;
		w[j] = 0;
		nex[j + 1] = j;
		nex[j]=j;
		int ww=min(2*j,n);
		rep(j + 2, ww, i) {
			while (now != j && a[i] != a[now + 1])
				now = nex[now];
			if (a[i] == a[now + 1])
				++now;
			nex[i] = now;
			w[i] = w[now] + 1;

		}
		now = j;
		rep(1, j - 1, i) {
			while (now != j && a[i] != a[now + 1])
				now = nex[now];
			if (a[i] == a[now + 1])
				++now;
			ans += (ll)w[now] * c1[i + 1][j];
		}
	}

	rep(2, m-1, j) {
		now = j;
		w[j + 1] = 1;
		w[j] = 0;
		nex[j + 1] = j;
		nex[j]=j;
		int ww=min(2*j,m);
		rep(j + 2, ww, i) {
			while (now != j && b[i] != b[now + 1])
				now = nex[now];
			if (b[i] == b[now + 1])
				++now;
			nex[i] = now;
			w[i] = w[now] + 1;
		}
		now = j;
		rep(1, j - 1, i) {
			while (now != j && b[i] != b[now + 1])
				now = nex[now];
			if (b[i] == b[now + 1])
				++now;
			ans += (ll)w[now] * c2[i + 1][j];
		}
	}

	printf("%lld\n", ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 168700kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 3ms
memory: 169172kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

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

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 4ms
memory: 168368kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 11ms
memory: 169960kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 453ms
memory: 362432kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 51ms
memory: 211552kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 53ms
memory: 212944kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: 0
Accepted
time: 1338ms
memory: 461108kb

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:

2655796915

result:

ok 1 number(s): "2655796915"

Test #10:

score: 0
Accepted
time: 1351ms
memory: 459500kb

input:

ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...

output:

2652657341

result:

ok 1 number(s): "2652657341"

Test #11:

score: 0
Accepted
time: 1365ms
memory: 459016kb

input:

uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...

output:

2619083676

result:

ok 1 number(s): "2619083676"

Test #12:

score: 0
Accepted
time: 63ms
memory: 211784kb

input:

ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...

output:

61227979

result:

ok 1 number(s): "61227979"

Test #13:

score: 0
Accepted
time: 389ms
memory: 319812kb

input:

cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...

output:

834307544

result:

ok 1 number(s): "834307544"

Test #14:

score: 0
Accepted
time: 1321ms
memory: 454788kb

input:

trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...

output:

2663862697

result:

ok 1 number(s): "2663862697"

Test #15:

score: 0
Accepted
time: 19ms
memory: 210464kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: -100
Memory Limit Exceeded

input:

igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...

output:

1707132

result: