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;
}
N. A+B problem
tag:数学
签到题。
//P9782
#include <bits/stdc++.h>
using namespace std;
int main(){
char s[5], t[5];
scanf("%s%s", s, t);
int a = s[0] + t[0] - 'A' - 'A';
if(a <= 25){
putchar(a+'A');
} else {
putchar(a/26+'A');
putchar(a%26+'A');
}
}
标签:ch,int,华中科技大学,sum,cg,++,补题,2023,nw
From: https://www.cnblogs.com/KiharaTouma/p/17810038.html