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');
	}
}