QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#687429 | #9522. A Simple String Problem | ucup-team5077 | AC ✓ | 1383ms | 9020kb | C++17 | 3.0kb | 2024-10-29 19:00:40 | 2024-10-29 19:00:41 |
Judging History
This is a historical verdict posted at 2024-10-29 19:00:41.
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-29 19:00:40]
- Submitted
answer
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const int N=2e5+5;
int n;
char s[N], t[N];
int ans=0;
const int m1=998244353, m2=993244853;
struct hsh{
int x, y;
inline hsh operator +(const hsh &t){
return (hsh){(x+t.x)%m1, (y+t.y)%m2};
}
inline hsh operator -(const hsh &t){
return (hsh){(x-t.x+m1)%m1, (y-t.y+m2)%m2};
}
inline hsh operator *(const hsh &t){
return (hsh){(int)((ll)x*t.x%m1), (int)((ll)y*t.y%m2)};
}
inline void operator +=(const hsh &t){
x=(x+t.x)%m1, y=(y+t.y)%m2;
}
inline bool operator ==(const hsh &t){
return x==t.x&&y==t.y;
}
}hs[N], ht[N], pw[N];
const hsh bs=(hsh){137, 13331};
inline hsh gs(int l, int r){
return hs[r]-hs[l-1]*pw[r-l+1];
}
inline hsh gt(int l, int r){
return ht[r]-ht[l-1]*pw[r-l+1];
}
inline int lcs1(int x, int y){
int l=1, r=x, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(gt(x-mid+1, x)==gt(y-mid+1, y)) {ret=mid; l=mid+1;}
else r=mid-1;
}
return ret;
}
inline int lcs2(int x, int y){
int l=1, r=x, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(gs(x-mid+1, x)==gt(y-mid+1, y)) {ret=mid; l=mid+1;}
else r=mid-1;
}
return ret;
}
inline int lcs3(int x, int y){
int l=1, r=x, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(gs(x-mid+1, x)==gs(y-mid+1, y)) {ret=mid; l=mid+1;}
else r=mid-1;
}
return ret;
}
inline int lcp1(int x, int y){
int l=1, r=n-y+1, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(gt(x, x+mid-1)==gt(y, y+mid-1)) {ret=mid; l=mid+1;}
else r=mid-1;
}
return ret;
}
inline int lcp2(int x, int y){
int l=1, r=n-y+1, mid, ret=0;
while(l<=r){
mid=(l+r)>>1;
if(gs(x, x+mid-1)==gs(y, y+mid-1)) {ret=mid; l=mid+1;}
else r=mid-1;
}
return ret;
}
inline void solve(){
pw[0]=(hsh){1, 1};
for(int i=1; i<=n; ++i) pw[i]=pw[i-1]*bs, hs[i]=hs[i-1]*bs+(hsh){s[i], s[i]}, ht[i]=ht[i-1]*bs+(hsh){t[i], t[i]};
for(int i=1; i<n; ++i) if(s[i]==s[i+1]||s[i]==t[i+1]){
ans=max(ans, 2); break;
}
for(int i=2; i<=n/2; ++i){
bool flg=0;
for(int j=1; j+i-1<=n; j+=i){
// if(lcp2(j, j+i)+lcs3(j-1, j+i-1)>=i){
// flg=1; break;
// }
int p2=j-lcs1(j-1, j+i-1);
int p3=j+i+lcp1(j, j+i);
int p1=p2-lcs2(p2-1, p2-1+i);
if(p3-p1>=2*i) {flg=1; break;}
}
if(flg) ans=max(ans, 2*i);
}
}
int main(){
// freopen("D:\\nya\\acm\\A\\test.in","r",stdin);
// freopen("D:\\nya\\acm\\A\\test.out","w",stdout);
read(n);
scanf("%s", s+1);
scanf("%s", t+2);
s[n+1]='?'; t[1]='!';
++n;
solve();
reverse(s+1, s+n+1);
reverse(t+1, t+n+1);
swap(s, t);
solve();
printf("%d\n", ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4292kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4172kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4300kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4288kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4352kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4148kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1219ms
memory: 9020kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 1214ms
memory: 8988kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 1224ms
memory: 8920kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1383ms
memory: 8916kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1252ms
memory: 8984kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 1162ms
memory: 8984kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 1222ms
memory: 8984kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4228kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 4356kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4320kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4304kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed