题目链接:洛谷P9934 [NFLSPC #6] 绝不能忘记的事……
我hatelove大力分讨。
这道题先分三种大情况:N
在左边,N
在中间,N
在右边。
声明:以下分类讨论中,a, b, c, d
均为记住的字符串。
记录操作
N
在左边
-
当复制串形如
N a b
,可以用map <string, int>
记录。 -
当复制串形如
N a H
,那么a
就是a H
的非空真前缀,可以将a
顺序加入正串 trie 中。 -
当复制串形如
N Z b
,那么b
就是Z b
的非空真后缀,将b
和Z b
都首尾颠倒后b
就是Z b
的非空真前缀,可以将b
倒序加入反串 trie 中。 -
当复制串形如
N Z H
,那么每个N
在左边的复制串都可以与它匹配,直接累加答案。
N
在右边
我们发现只要将整个字符串颠倒一下,如果有 H
,将 H
变为 Q
,就可以按照 N
在左边的方式处理字符串。
N
在中间
-
当复制串形如
a N b
,可以用map <pair <string, string>, int>
记录。 -
当复制串形如
Q N b
,可以用map <string, int>
记录。 -
当复制串形如
a N H
,可以用map <string,int>
记录。 -
当复制串形如
Q N H
,那么每个N
在中间的复制串都可以与它匹配,直接累加答案。
统计操作
将所有的复制串枚举一遍。
N
在左边
- 当复制串形如
N a b
,那么以下三种情况可以与其匹配:
-
N c d
,其中a + b
=c + d
,直接累加map[a + b]
; -
N c H
,其中c
为a + b
的前缀,比如N abcdefgh
就与N abc H
相匹配,在正串 trie 上求根到a + b
的路径点权和; -
N Z d
,其中d
为a + b
的后缀,比如N abcdefgh
就与N Z defgh
相匹配,在反串 trie 上求根到a + b
的路径点权和。
-
当复制串形如
N a H
,为了不重复计算,只有形如N c H
,其中c
为a
的真前缀时才匹配,在正串 trie 上求根到a
的路径点权和。 -
当复制串形如
N Z b
,为了不重复计算,只有形如N Z d
,其中d
为b
的真后缀时才匹配,在反串 trie 上求根到b
的路径点权和。
答案取第一种情况匹配数、第二三种情况匹配数和的最大值加上一开始统计的 N Z H
的个数。
N
在右边
与记录操作一样,颠倒后按 N
在左边一样统计。
N
在中间
- 当复制串形如
a N b
,那么以下三种情况可以与其匹配:
-
a N b
,直接累加map[pair(a, b)]
; -
a N H
,直接累加map[a]
; -
Q N b
,直接累加map[b]
。
-
当复制串形如
Q N b
,直接累加map[b]
。 -
当复制串形如
a N H
,直接累加map[a]
。
答案取第一种情况匹配数、第二三种情况匹配数和的最大值加上一开始统计的 Q N H
的个数。
这样就分类讨论完了所有情况。
完整代码是真的长:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int ch[5][N][26], red[5][N], tot[5], ans[5], n;
map <string, int> mp, mp5, mp2, mp3;//mp s1 = "N", mp5 s3 = "N", mp3, mp4, mp5 s2 == "N"
map <pair <string, string>, int> mp4;
string tmp, s1, s2, s3;
int num(char c){
return c - 'a' + 1;
}
void insert(int ty){
int u = 1, len = tmp.length();
for(int i = 0; i < len; i++){
int x = num(tmp[i]);
if(ch[ty][u][x] == 0){
ch[ty][u][x] = ++tot[ty];
u = tot[ty];
}
else
u = ch[ty][u][x];
}
red[ty][u]++;
}
int query(int ty){
int u = 1, ans = 0, len = tmp.length();
for(int i = 0; i < len; i++){
int x = num(tmp[i]);
if(ch[ty][u][x]){
ans += red[ty][ch[ty][u][x]];
u = ch[ty][u][x];
} else
break;
}
return ans;
}
/*
ty = 1 : s1 == "N",正串;
ty = 2 : s1 == "N",反串;
ty = 3 : s3 == "N",正串;
ty = 4 : s3 == "N",反串
*/
struct Store{
string t1, t2, t3;
} st[5][N];
int cnt[5];
signed main(){
for(int i = 0; i <= 8; i++)
tot[i] = 1;
scanf("%lld", &n);
for(int i = 1; i <= n; i++){
cin >> s1 >> s2 >> s3;
if(s1 == "N")
st[1][++cnt[1]] = Store{s1, s2, s3};
else if(s2 == "N")
st[2][++cnt[2]] = Store{s1, s2, s3};
else
st[3][++cnt[3]] = Store{s1, s2, s3};
}
for(int i = 1; i <= 3; i++){
int w = 0, cnta = 0, cntb = 0;
if(i == 1){
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s2 != "Z" && s3 != "H"){
tmp = s2 + s3;
mp[tmp]++;
} else if(s2 == "Z" && s3 != "H"){
tmp = s3;
reverse(tmp.begin(), tmp.end());
insert(2);
} else if(s2 != "Z" && s3 == "H"){
tmp = s2;
insert(1);
} else
w++;
}
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s2 != "Z" && s3 != "H"){
int sum = mp[s2 + s3];
tmp = s2 + s3;
tmp.pop_back();
sum += query(1);
tmp = s2 + s3;
reverse(tmp.begin(), tmp.end());
tmp.pop_back();
sum += query(2);
ans[i] = max(ans[i], sum);
} else if(s2 == "Z" && s3 != "H"){
tmp = s3;
reverse(tmp.begin(), tmp.end());
cntb = max(cntb, query(2));
} else if(s2 != "Z" && s3 == "H"){
tmp = s2;
cnta = max(cnta, query(1));
}
}
ans[i] = max(ans[i], cnta + cntb) + w;
} else if(i == 2){
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s1 != "Q" && s3 != "H")
mp4[make_pair(s1, s3)]++;
else if(s1 == "Q" && s3 != "H")
mp3[s3]++;
else if(s1 != "Q" && s3 == "H")
mp2[s1]++;
else
w++;
}
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s1 != "Q" && s3 != "H")
ans[i] = max(ans[i], mp2[s1] + mp3[s3] + mp4[make_pair(s1, s3)]);
else if(s1 == "Q" && s3 != "H")
cntb = max(cntb, mp3[s3]);
else if(s1 != "Q" && s3 == "H")
cnta = max(cnta, mp2[s1]);
}
ans[i] = max(ans[i], cnta + cntb) + w;
} else {
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s1 == "Q")
s1 = "H";
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
string fk = s1;
s1 = s2;
s2 = fk;
st[i][j].t1 = s1;
st[i][j].t2 = s2;
if(s1 != "Z" && s2 != "H"){
tmp = s1 + s2;
mp[tmp]++;
} else if(s1 == "Z" && s2 != "H"){
tmp = s2;
reverse(tmp.begin(), tmp.end());
insert(4);
} else if(s1 != "Z" && s2 == "H"){
tmp = s1;
insert(3);
} else
w++;
}
for(int j = 1; j <= cnt[i]; j++){
s1 = st[i][j].t1;
s2 = st[i][j].t2;
s3 = st[i][j].t3;
if(s1 != "Z" && s2 != "H"){
int sum = mp[s1 + s2];
tmp = s1 + s2;
tmp.pop_back();
sum += query(3);
tmp = s1 + s2;
reverse(tmp.begin(), tmp.end());
tmp.pop_back();
sum += query(4);
ans[i] = max(ans[i], sum);
} else if(s1 == "Z" && s2 != "H"){
tmp = s2;
reverse(tmp.begin(), tmp.end());
cntb = max(cntb, query(4));
} else if(s1 != "Z" && s2 == "H"){
tmp = s1;
cnta = max(cnta, query(3));
}
}
ans[i] = max(ans[i], cnta + cntb) + w;
}
}
printf("%lld", max(max(ans[1], ans[2]), ans[3]));
return 0;
}
标签:map,洛谷,ty,int,题解,s1,P9934,复制,串形
From: https://www.cnblogs.com/JPGOJCZX/p/18422853