QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744456 | #7780. Dark LaTeX vs. Light LaTeX | Suhy | WA | 584ms | 16212kb | C++23 | 2.7kb | 2024-11-13 21:58:55 | 2024-11-13 21:58:56 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned int
#pragma GCC optimize(3)
using namespace std;
const int maxn = 10004;
const int b1 = 31;
const int b2 = 37;
int n, m;
int s[maxn], t[maxn];
ull ps1[maxn], ps2[maxn], pt1[maxn], pt2[maxn];
unordered_map <ull, int> mp1;
ull pwb1[maxn], pwb2[maxn];
ll ans;
int f[maxn], cnt[maxn];
//babaa
void wok(int dlt)
{
for(int i = 2, l = 2 + dlt - n + 1, r = dlt; i < n; i ++, l ++)
{
int j = f[i - 1];
while(j > 0 && (s[j + 1 + dlt] != s[i + dlt] || (i + dlt > n && (i + dlt - j <= n || j + dlt >= n))))
j = f[j];
if(s[j + 1 + dlt] == s[i + dlt])
j ++;
f[i] = j;
cnt[i] = 0;
if(j != 0) cnt[i] ++;
cnt[i] += cnt[j];
if(cnt[i] && l > 1 && r - l + 1 <= m)
{
//cout<<l<<' '<<r<<' '<<cnt[i]<<' '<<i<<' '<<f[i]<<' '<<s[i + dlt]<<' '<<s[1 + dlt]<<' ';
// for(int j = l; j <= r; j ++)
// putchar(s[j] + 'a' - 1);
// cout<<endl;
ans += cnt[i] * mp1[ps1[r] - ps1[l - 1] * pwb1[r - l + 1]];
//cout<<ps1[r] - ps1[l - 1] * pwb1[r - l + 1]<<endl;
}
}
}
void work()
{
mp1.clear();
for(int i = 1; i <= m; i ++)
{
for(int j = 1; j <= i; j ++)
{
if(i - j + 1 <= n)
mp1[pt1[i] - pt1[j - 1] * pwb1[(i - j + 1)]] ++;
}
}
for(int i = 1; i <= n; i ++)
s[i + n] = s[i];
for(int i = 1; i < n; i ++)
{
wok(i);
}
}
signed main()
{
char c = getchar();
while('a' <= c && c <= 'z')
s[++ n] = c - 'a' + 1, c = getchar();
while(!('a' <= c && c <= 'z'))
c = getchar();
while('a' <= c && c <= 'z')
t[++ m] = c - 'a' + 1, c = getchar();
for(int i = 1; i <= n; i ++)
{
ps1[i] = ps1[i - 1] * b1 + s[i];
}
for(int i = 1; i <= m; i ++)
{
pt1[i] = pt1[i - 1] * b1 + t[i];
}
pwb1[0] = pwb2[0] = 1;
for(int i = 1; i <= max(n, m); i ++)
{
pwb1[i] = 1ll * pwb1[i - 1] * b1;
}
swap(n, m);
for(int i = 1; i <= max(n, m); i ++)
{
swap(s[i], t[i]);
swap(ps1[i], pt1[i]);
}
work();
//cout<<"-----"<<endl;
swap(n, m);
for(int i = 1; i <= max(n, m); i ++)
{
swap(s[i], t[i]);
swap(ps1[i], pt1[i]);
}
work();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= i; j ++)
{
if(i - j + 1 <= m)
{
ull hsh1 = ps1[i] - ps1[j - 1] * pwb1[(i - j + 1)];
ans += mp1[hsh1];
}
}
}
cout<<ans<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 584ms
memory: 4144kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: -100
Wrong Answer
time: 137ms
memory: 16212kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60717809
result:
wrong answer 1st numbers differ - expected: '60716448', found: '60717809'