QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744353 | #7780. Dark LaTeX vs. Light LaTeX | Suhy | TL | 590ms | 16536kb | C++17 | 2.7kb | 2024-11-13 21:38:07 | 2024-11-13 21:38:07 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#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; i < n; i ++)
{
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];
int l = i + dlt - n + 1;
int r = dlt;
if(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: 1ms
memory: 3536kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 590ms
memory: 4028kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 112ms
memory: 16144kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 118ms
memory: 16536kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: -100
Time Limit Exceeded
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...