1.

前缀统计：

题目:给定n个字符串 $$S1,S2,S3 … $$，接下来进行m次询问，每次询问给定一个字符串T，求S1,S2,S3

中有多少个字符串是T的前缀

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1e7 + 1;
const int C = 10;

int trie[N][C], tot = 1;
char str[N];
int n;
int a[N];

inline void insert(int x)
{
    int p = 1;
    for(int i = 31;i >= 0;i --)
    {
        int s = (x >> i) & 1;
        if(!trie[p][s]) 
            trie[p][s] = ++tot;
        p = trie[p][s];
    }
}

inline int query(int x)
{
    int p = 1;
    ll nans = 0;
    for(int i = 31;i >= 0;i --)
    {
        int s = ((x >> i) & 1) == 1 ? 0 : 1;
        if(trie[p][s])
            nans += (ll)(1 << i);
        else s = ((x >> i) & 1);
        p = trie[p][s];
    }
    return nans;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        cin >> a[i];
        insert(a[i]);
    }

    ll ans = 0;

    for(int i = 1;i <= n;i ++)
    {
        ans = max(ans, (ll)query(a[i]));
    }

    printf("%lld", ans);

    return 0;
}

$$ 最大异或和 $$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e7 + 1;
typedef long long ll;
struct edge{
    int to;
    int next;
    long long val;
}e[N];

int head[N], idx = 0, tot = 1;
long long dis[N];
int trie[N][10];
bool vis[N];

inline void insert(ll x)
{
    int p = 1;
    for(int i = 31;i >= 0;i --)
    {
        int s = (x >> i) & 1;
        if(!trie[p][s]) 
            trie[p][s] = ++tot;
        p = trie[p][s];
    }
}

inline int query(ll x)
{
    int p = 1;
    ll nans = 0;
    for(int i = 31;i >= 0;i --)
    {
        int s = ((x >> i) & 1) == 1 ? 0 : 1;
        if(trie[p][s])
            nans += (ll)(1 << i);
        else s = ((x >> i) & 1);
        p = trie[p][s];
    }
    return nans;
}

inline void add(int u, int v, long long w)
{
    e[++idx].to = v;
    e[idx].val = w;
    e[idx].next = head[u];
    head[u] = idx;
}

inline void dfs(int x)
{
    for(register int i = head[x]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(vis[v]) continue;
        vis[v] = true;
        dis[v] = dis[x] ^ e[i].val;
        dfs(v);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(register int i = 1;i <= n - 1;i ++)
    {
        int u, v;
        long long w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1);
    for(int i = 1;i <= n;i ++)
        insert(dis[i]);
    long long ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        ans = max(ans, (ll)query(dis[i]));
    }
    printf("%lld",ans);
    return 0;
}

$$ 3.最大异或路径 $$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e7 + 1;
typedef long long ll;

bool bo[N][26];
int trie[N][26];
int tot = 1;

inline void insert(char *s, int num)
{
    int len = strlen(s);
    int p = 1;
    for(int i = 0;i < len;i ++)
    {
        int c = s[i] - 'a';
        if(!trie[p][c]) 
            trie[p][c] = ++ tot;
        p = trie[p][c];
    }
    bo[p][num] = 1;
    return;
}

inline void find(char *s)
{
    int len = strlen(s);
    int p = 1;
    bool flag = false;
    for(int i = 0;i < len; i++)
    {
        int c = s[i] - 'a';
        if(!trie[p][c]){
            flag = true;
            break;
        }
        p = trie[p][c];
    }
    if(flag == false){
        for(int i = 1;i <= n;i ++)
            if(bo[p][i])
                printf("d ", i);
    }
    printf("\n");
    return ;
}

int main()
{
    int n;

}