Neovim-如何使用编辑器的神

字典树模板题

https://www.acwing.com/problem/content/837/

字典树能够在$O(k)$的时间复杂度内查找一个字符串在集合中出现的次数, 其中$k$是字符串的长度.

#include <iostream>

using namespace std;

/* 这个N表示字典树中可能有多少个节点, 等于所有可能插入的字符串的长度之和 */
const int N = 100010;

int idx, cnt[N], son[N][26];

char str[N];

/* 向字典树中插入str */
void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

/* 查找str出现的次数 */
int query()
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;

    while (n --)
    {
        char op[2];
        scanf("%s", op);

        if (*op == 'I')
        {
            scanf("%s", str);
            insert();
        }
        else
        {
            scanf("%s", str);
            cout << query() << endl;
        }
    }
    return 0;
}

最大异或对

https://www.acwing.com/problem/content/145/

在给定的一个数组中, 选取两个数, 使得它们的异或最大.

#include <iostream>

using namespace std;

const int N = 31 * 100010;

int idx, son[N][2];

int n, a[N / 31];

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (son[p][!u])
        {
            res += (1 << i);
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return res;
}

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

    int res = -1;
    for (int i = 0; i < n; i ++) res = max(res, query(a[i]));

    cout << res << endl;
    return 0;
}