今天不小心溜出去了...晚上先复健一哈

trie模板：拨号 The xor-longest Path

trie

快速插入、查找

模板：

int n,m; int trie[maxn][30],tot=1; int en[maxn]; string sn; void inser(string s){//trie插入 int ch,len=s.length(),p=1; for(int i=0;i<len;i++){ ch=s[i]-'a'; if(trie[p][ch]==0)trie[p][ch]=++tot; p=trie[p][ch]; } en[p]=1; } int sear(string s){//检索字符串是否存在 int len=s.length(),p=1,ch,sum=0; for(int i=0;i<len;i++){ ch=s[i]-'a'; p=trie[p][ch]; if(p==0)return false; } return en[p]; }

拨号

HDU 1671 Phone List 小心maxn开的不够大

int n,m; int trie[maxn][30],tot=1; int en[maxn]; char cun[maxn][30]; void inser(char s[]){//trie插入 int ch,len=strlen(s),p=1; for(int i=0;i<len;i++){ ch=s[i]-'0'; if(trie[p][ch]==0)trie[p][ch]=++tot; p=trie[p][ch]; } en[p]++; } bool sear(char s[]){//检索字符串是否存在 int len=strlen(s),p=1,ch,sum=0; for(int i=0;i<len;i++){ ch=s[i]-'0'; p=trie[p][ch]; if(en[p]==0)continue; if(en[p]==1&&i==len-1)continue; return false; } return true; } int main(){ int t,flag; scanf("%d",&t); while(t--){ flag=1; for(int i=1;i<=tot;i++)mem(trie[i],0); tot=1; mem(en,0); sci(n); for(int i=1;i<=n;i++){ scanf("%s",cun[i]); inser(cun[i]); } for(int i=1;i<=n;i++){ if(!sear(cun[i]))flag=0; } if(flag)puts2(); else puts3(); } return 0; }

The xor-longest Path

难啊

int n, d[N], trie[N*33][2], tot; vector<pair<int, int> > e[N]; int Head[N], Edge[N*2], Leng[N*2], Next[N*2], num; bool v[N]; void dfs(int x) { for (int i = Head[x]; i; i = Next[i]) { int y = Edge[i], z = Leng[i]; if (v[y]) continue; v[y] = 1; d[y] = d[x] ^ z; dfs(y); } } void add(int x, int y, int z) { Edge[++tot] = y; Leng[tot] = z; Next[tot] = Head[x]; Head[x] = tot; } void The_xor_longest_Path() { memset(d, 0, sizeof(d)); memset(trie, 0, sizeof(trie)); memset(v, 0, sizeof(v)); memset(Head, 0, sizeof(Head)); num = 0; v[0] = 1; tot = 1; for (int i = 1; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } dfs(0); int ans = 0; for (int i = 0; i < n; i++) { int p = 1; for (int j = 31; j >= 0; j--) { int k = (d[i] >> j) & 1; if (!trie[p][k]) trie[p][k] = ++tot; p = trie[p][k]; } p = 1; if (i) { int w = 0; for (int j = 31; j >= 0; j--) { int k = (d[i] >> j) & 1; if (trie[p][k^1]) { w = (w << 1) + (k ^ 1); p = trie[p][k^1]; } else { w = (w << 1) + k; p = trie[p][k]; } } ans = max(ans, w ^ d[i]); } } cout << ans << endl; }