A
板子。
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=1e6+5,M=48;
int n,m,tot;
string s[N];
int trie[N][M],exist[N];void insert(string s){int cur=0;for(int i=0;i<s.size();i++){int ch=s[i]-'a';if(!trie[cur][ch])trie[cur][ch]=++tot;cur=trie[cur][ch];}exist[cur]++;
}
int search(string s){int cur=0,ans=0;for(int i=0;i<s.size();i++){int ch=s[i]-'a';if(!trie[cur][ch])return ans;cur=trie[cur][ch];ans+=exist[cur];}return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i],insert(s[i]);while(m--){string t;cin>>t;cout<<search(t)<<'\n';}return 0;
}
B
01-trie 板子。
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=3e6+5;
int n,tot;
int a[N],trie[N][2];void insert(int x){int cur=0;for(int i=31;i>=0;i--){int k=(x>>i)&1;if(!trie[cur][k])trie[cur][k]=++tot;cur=trie[cur][k];}
}
int search(int x){int ans=0,cur=0;for(int i=31;i>=0;i--){int k=(x>>i)&1;if(trie[cur][k^1])ans+=(k^1)<<i,cur=trie[cur][k^1];elseans+=k<<i,cur=trie[cur][k];}return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);int ans=-1e18;for(int i=1;i<=n;i++){int now=search(a[i])^a[i];ans=max(ans,now);}cout<<ans;return 0;
}
C
见题解。
D
考虑到异或是不进位的加法，说明 \(x \in [0,2 \times 10^6]\)。
我们枚举 \(x\)，这样 \(x,k\) 都能定下来，于是只要确定有多少个 \(a_i\)。
把 \(a_i\) 全部扔进 01-trie 里头，画一下图分析，可分两种情况：若 \(k\) 当前位为 \(1\)，则 \(x\) 的当前位的那个分支上的 \(a_i\) 全都可以选，我们仅需找另外一侧的；若为 \(0\)，则必须走 \(x\) 的当前位的那个分支。
注意，最后需要加上恰好 \(= k\) 的情形。
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=3e7+5;
int n,k,tot;
int a[N],trie[N][2],cnt[N];void insert(int x){int cur=0;for(int i=31;i>=0;i--){int xi=(x>>i)&1;if(!trie[cur][xi])trie[cur][xi]=++tot;cur=trie[cur][xi];cnt[cur]++;}
}
int search(int x){int cur=0,ans=0;for(int i=31;i>=0;i--){int xi=(x>>i)&1,ki=(k>>i)&1;if(ki)ans+=cnt[trie[cur][xi]],cur=trie[cur][xi^1];elsecur=trie[cur][xi];if(!cur)return ans;}if(cur)ans++;return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);int ans=-1e18;for(int x=0;x<=(int)(2e6);x++)ans=max(ans,search(x));cout<<ans;return 0;
}
总结：
- 01-trie 画图与分析技巧：从高到低位依次对齐 01-trie 的每一层，分析如何在树上走（通常需要分类讨论）。