Luogu2922 [USACO08DEC]秘密消息Secret Message （Trie树）

布满荆棘的人生 2021-11-17 05:12 186阅读 0赞

统计以节点\\(i\\)结尾的数量与经过的数量

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define R(a,b,c) for(register int a = (b); a <= (c); ++ a) #define nR(a,b,c) for(register int a = (b); a >= (c); -- a) #define Max(a,b) ((a) > (b) ? (a) : (b)) #define Min(a,b) ((a) < (b) ? (a) : (b)) #define Fill(a,b) memset(a, b, sizeof(a)) #define Abs(a) ((a) < 0 ? -(a) : (a)) #define Swap(a,b) a^=b^=a^=b #define ll long long #define ON_DEBUG #ifdef ON_DEBUG #define D_e_Line printf("\n\n----------\n\n") #define D_e(x) cout << #x << " = " << x << endl #define Pause() system("pause") #define FileOpen() freopen("in.txt","r",stdin); #else #define D_e_Line ; #define D_e(x) ; #define Pause() ; #define FileOpen() ; #endif struct ios{ template<typename ATP>ios& operator >> (ATP &x){ x = 0; int f = 1; char c; for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar(); x*= f; return *this; } }io; using namespace std; const int N = 500007; int sum[N], endd[N], t[N][2], trieIndex; char s[10007]; inline void Insert(char* str, int len){ int rt = 0; R(i,1,len){ int v = str[i] - '0'; if(!t[rt][v]){ t[rt][v] = ++trieIndex; // no return here } rt = t[rt][v]; ++sum[rt]; } ++endd[rt]; } inline int Query(char *str, int len){ int ans = 0; int rt = 0; int flag = false; R(i,1,len){ int v = str[i] - '0'; if(!t[rt][v]){ flag = true; break; } rt = t[rt][v]; // let rt be t[rt][v] first, then add endd[rt] ans += endd[rt]; } if(!flag) ans += sum[rt] - endd[rt]; // sum include endd return ans; } int main(){ //FileOpen(); int n, m; io >> n >> m; R(i,1,n){ int len; io >> len; R(j,1,len){ int x; io >> x; s[j] = x + '0'; } Insert(s, len); } R(i,1,m){ int len; io >> len; R(j,1,len){ int x; io >> x; s[j] = x + '0'; } printf("%d\n", Query(s, len)); } return 0; } /* 4 5 3 0 1 0 1 1 3 1 0 0 3 1 1 0 1 0 1 1 2 0 1 5 0 1 0 0 1 2 1 1 */

![1570282-20190724172916107-1179059538.png][]

转载于:https://www.cnblogs.com/bingoyes/p/11238075.html

[1570282-20190724172916107-1179059538.png]: /images/20211116/3cb1310b74e546b69433d7913e09d7e2.png