【题解】P2922 [USACO08DEC]秘密消息Secret Message

\(\text{Tags}\)
- 字典树，统计

题意：
- 给出两组\(\text{0/1}\)串\(\text{A,B}\)，求解\(\text{A}\)中某串是\(\text{B}\)中某串的前缀，和\(\text{B}\)中某串是\(\text{A}\)中某串的前缀的数量之和。
分析：
- 对于\(\text{A}\)建立字典树。另外附加两个数组：
- \(\text{int Son[i]}\)表示节点 \(\text{i}\) 点\(\text{Son[i]}\)儿子。
- \(\text{int End[i]}\)表示有\(\text{End[i]}\)个字符串终结于\(\text{i}\)。
- 对于每个询问，沿着字典树向下走，累加沿途的\(\text{End[i]}\) 。
- 如果不能匹配，返回累加值。
- 如果整个询问都匹配成功，还要加上最后一个节点的儿子数量。

参考代码：

#include <stdio.h>

#include <string.h>

#define re register

#define GC getchar()

#define Clean(X,K) memset(X,K,sizeof(X))

int Qread () {

	int X = 0 ;

	char C = GC ;

	while (C > '9' || C < '0') C = GC ;

	while (C >='0' && C <='9') {

		X = X  * 10 + C - '0' ;

		C = GC ;

	}

	return X ;

}

const int Maxn = 500005 , Base = 2;

int T[Maxn][Base] , Tot = 0 , M , N , End[Maxn] , Son[Maxn] , A[Maxn];

void Add (int Now) {

	int P = 0 ;

	for (re int i =  0 ; i < Now ; ++ i) {

		if (!T[P][A[i]]) T[P][A[i]] = ++ Tot;

		++ Son[P] ;

		P = T[P][A[i]] ;

	}

	++ End[P] ;

}

int Ask (int Now) {

	int P = 0 , Ans = 0;

	for (re int i = 0 ; i < Now ; ++ i) {

		if (!T[P][A[i]]) return Ans ;

		P = T[P][A[i]] ;

		Ans += End[P] ;

	}

	return Ans + Son[P] ;

}

int main () {

	M = Qread () , N = Qread () ;

	Clean(T , 0) , Clean(End , 0) , Clean (Son , 0) ;

	for (re int i = 1 ; i <= M; ++ i) {

		int Now = Qread () ;

		for (re int j = 0 ; j < Now ; ++ j) A[j] = Qread () ;

		Add (Now) ;

	}

	for (re int i = 1 ; i <= N; ++ i) {

		int Now = Qread () ;

		for (re int j = 0 ; j < Now ; ++ j) A[j] = Qread () ;

		printf ("%d\n" , Ask (Now)) ;

	}

	fclose (stdin) , fclose (stdout) ;

	return 0 ;

}

巴特西

【题解】P2922 [USACO08DEC]秘密消息Secret Message

\(\text{Tags}\)

题意：

分析：

参考代码：

Thanks!

最新文章

热门文章