HUSTFC 2023
题目来源：Luogu P9769~P9782
J. 基因编辑
tag：Trie
因为 \(i,j\) 没有限制，所以题目求的其实等价于枚举一个串 \(k\) 以及一个位置 \(x\)，求正好可以匹配 \(k\) 的前 \(x\) 位的串数量乘上至少可以匹配 \(k\) 的后 \(|S_k|-x\) 位的串的数量，这里一个至少一个正好可以不重不漏得算出每一种情况，然后就可以用 Trie 维护了。
//P9778
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int n, ch[2][N][4], sum[2][N], cnt[2], le[N], ri[N];
string s[N];
typedef long long ll;
ll ans = 0;
int cg(char c){
return c == 'A' ? 0 : c == 'C' ? 1 : c == 'G' ? 2 : 3;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++ i){
cin >> s[i];
int nw = 0;
int l = s[i].size();
for(int j = 0; j < l; ++ j){
if(!ch[0][nw][cg(s[i][j])]){
ch[0][nw][cg(s[i][j])] = ++ cnt[0];
}
nw = ch[0][nw][cg(s[i][j])];
}
++ sum[0][nw];
nw = 0;
for(int j = l-1; j >= 0; -- j){
if(!ch[1][nw][cg(s[i][j])]){
ch[1][nw][cg(s[i][j])] = ++ cnt[1];
}
nw = ch[1][nw][cg(s[i][j])];
}
++ sum[1][nw];
}
for(int i = cnt[0]; i >= 0; -- i){
for(int j = 0; j < 4; ++ j){
if(ch[0][i][j]){
sum[0][i] += sum[0][ch[0][i][j]];
}
}
}
for(int i = cnt[1]; i >= 0; -- i){
for(int j = 0; j < 4; ++ j){
if(ch[1][i][j]){
sum[1][i] += sum[1][ch[1][i][j]];
}
}
}
for(int i = 1; i <= n; ++ i){
int nw = 0;
int l = s[i].size();
le[0] = sum[0][nw] - 1;
for(int j = 0; j < l; ++ j){
nw = ch[0][nw][cg(s[i][j])];
le[j+1] = sum[0][nw] - 1;
}
for(int j = 0; j <= l-1; ++ j){
le[j] -= le[j+1];
}
nw = 0;
ri[l] = sum[1][nw] - 1;
for(int j = l-1; j >= 0; -- j){
nw = ch[1][nw][cg(s[i][j])];
ri[j] = sum[1][nw] - 1;
}
for(int j = l; j > 0; -- j){
ri[j] -= ri[j-1];
}
ll sum = 0;
for(int j = 0; j <= l; ++ j){
sum += ri[j];
ans += sum * le[j];
}
}
printf("%lld\n", ans);
return 0;
}
K. 不定项选择题
tag：数学
显然，\(n\) 项不定项选择题若没有全部不选，则有 \(2^n-1\) 种可能的答案，输出 \(2^n-1\) 即可。
//P9779
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
cout << (1 << n) - 1;
return 0;
}