QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#302878 | #7780. Dark LaTeX vs. Light LaTeX | ucup-team173# | AC ✓ | 322ms | 365016kb | C++17 | 2.4kb | 2024-01-11 14:36:58 | 2024-11-25 21:07:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAXN = 5005, Mod1 = 998244353, Mod2 = 1e9 + 7, base = 131;
string S, T;
int n, m;
unordered_map<ll, int> cntS, cntT;
int lcp[MAXN][MAXN];
int f[MAXN][MAXN], g[MAXN][MAXN];
int cnt[MAXN];
int sum[MAXN][MAXN];
void solve() {
cin >> S >> T;
n = S.size(), m = T.size();
ll ans = 0;
memset(lcp, 0, sizeof(lcp));
for(int i = n - 1; i >= 0; i--) {
for(int j = m - 1; j >= 0; j--) {
if(S[i] == T[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
else lcp[i][j] = 0;
}
}
for(int i = 0; i < n; i++) {
memset(cnt, 0, sizeof(cnt));
for(int j = 0; j < m; j++) cnt[lcp[i][j]]++;
for(int j = n - 1; j >= 0; j--) cnt[j] += cnt[j + 1];
for(int j = i; j < n; j++) {
f[i][j] = cnt[j - i + 1], ans += f[i][j];
}
}
for(int i = 0; i < m; i++) {
memset(cnt, 0, sizeof(cnt));
for(int j = 0; j < n; j++) cnt[lcp[j][i]]++;
for(int j = m - 1; j >= 0; j--) cnt[j] += cnt[j + 1];
for(int j = i; j < m; j++) {
g[i][j] = cnt[j - i + 1];
}
}
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
sum[i][j] = (i == 0 ? 0 : sum[i - 1][j]) + f[i][j];
// cout << ans << '\n';
memset(lcp, 0, sizeof(lcp));
for(int l = n - 1; l >= 0; l--) {
for(int r = l + 1; r < n; r++) {
if(S[l] == S[r]) lcp[l][r] = lcp[l + 1][r + 1] + 1; else lcp[l][r] = 0;
if(lcp[l][r] > 0) {
ans += sum[l + lcp[l][r]][r - 1] - sum[l][r - 1];
}
}
}
for(int i = 0; i < m; i++) for(int j = 0; j < m; j++)
sum[i][j] = (i == 0 ? 0 : sum[i - 1][j]) + g[i][j];
memset(lcp, 0, sizeof(lcp));
for(int l = m - 1; l >= 0; l--) {
for(int r = l + 1; r < m; r++) {
if(T[l] == T[r]) lcp[l][r] = lcp[l + 1][r + 1] + 1; else lcp[l][r] = 0;
if(lcp[l][r] > 0) ans += sum[l + lcp[l][r]][r - 1] - sum[l][r - 1];
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 106572kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 25ms
memory: 106124kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 16ms
memory: 107240kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 20ms
memory: 106848kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 21ms
memory: 108228kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 322ms
memory: 364020kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 23ms
memory: 166468kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 23ms
memory: 165392kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: 0
Accepted
time: 202ms
memory: 363676kb
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...
output:
2655796915
result:
ok 1 number(s): "2655796915"
Test #10:
score: 0
Accepted
time: 226ms
memory: 365016kb
input:
ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...
output:
2652657341
result:
ok 1 number(s): "2652657341"
Test #11:
score: 0
Accepted
time: 230ms
memory: 345860kb
input:
uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...
output:
2619083676
result:
ok 1 number(s): "2619083676"
Test #12:
score: 0
Accepted
time: 16ms
memory: 167708kb
input:
ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...
output:
61227979
result:
ok 1 number(s): "61227979"
Test #13:
score: 0
Accepted
time: 92ms
memory: 254016kb
input:
cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...
output:
834307544
result:
ok 1 number(s): "834307544"
Test #14:
score: 0
Accepted
time: 209ms
memory: 348364kb
input:
trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...
output:
2663862697
result:
ok 1 number(s): "2663862697"
Test #15:
score: 0
Accepted
time: 38ms
memory: 164756kb
input:
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 249ms
memory: 349508kb
input:
igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...
output:
1707132
result:
ok 1 number(s): "1707132"
Test #17:
score: 0
Accepted
time: 27ms
memory: 162952kb
input:
jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...
output:
2954810
result:
ok 1 number(s): "2954810"
Test #18:
score: 0
Accepted
time: 29ms
memory: 166616kb
input:
juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...
output:
40401
result:
ok 1 number(s): "40401"
Test #19:
score: 0
Accepted
time: 230ms
memory: 349484kb
input:
lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...
output:
1421341
result:
ok 1 number(s): "1421341"
Test #20:
score: 0
Accepted
time: 19ms
memory: 165064kb
input:
cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...
output:
3118221
result:
ok 1 number(s): "3118221"
Test #21:
score: 0
Accepted
time: 298ms
memory: 361112kb
input:
srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...
output:
75529025
result:
ok 1 number(s): "75529025"
Test #22:
score: 0
Accepted
time: 236ms
memory: 346700kb
input:
onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...
output:
3326939
result:
ok 1 number(s): "3326939"
Test #23:
score: 0
Accepted
time: 31ms
memory: 165352kb
input:
etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...
output:
547040
result:
ok 1 number(s): "547040"
Test #24:
score: 0
Accepted
time: 28ms
memory: 165296kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
38791844792
result:
ok 1 number(s): "38791844792"
Test #25:
score: 0
Accepted
time: 102ms
memory: 252076kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
4804791846049
result:
ok 1 number(s): "4804791846049"
Test #26:
score: 0
Accepted
time: 243ms
memory: 359832kb
input:
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
10043476749324
result:
ok 1 number(s): "10043476749324"
Test #27:
score: 0
Accepted
time: 154ms
memory: 306036kb
input:
yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...
output:
269398620
result:
ok 1 number(s): "269398620"
Test #28:
score: 0
Accepted
time: 146ms
memory: 322176kb
input:
yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...
output:
269769773
result:
ok 1 number(s): "269769773"
Test #29:
score: 0
Accepted
time: 155ms
memory: 310784kb
input:
baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...
output:
287077563
result:
ok 1 number(s): "287077563"
Extra Test:
score: 0
Extra Test Passed