分治

51Nod 1601 完全图的最小生成树计数

Posted on

分治+字典树+MST 综合好题

标题即题意,但是不一样的是边权是点权的异或。

不可能会出什么边权也是给定的完全图最小生成树计数的啦,现在看来,也算是套路题了。
当然点数不能太多…………

不卡常才是一个好题的前提条件。写 Trie 习惯性用了类,虽然慢了一些,但也不至于太慢。

题意:
给你 n 个点的点权,边权为其异或值,要你求出最小生成树,以及最小生成树的个数。

思路:
这道题的核心思想还是分治。
我们对给定区间的点权进行处理,并假设这个区间的前面 k - 1 位全部相同。那么对于第 k 位,我们根据 01 将其划分为两个集合,这时候两个集合的前 k 位分别相同,再对这两个集合分别进行同样的处理。
其正确性不言而喻。

在处理的过程中,我们需要将两个集合之间建边,因为是MST,所以要找最小的边。将其中一个集合插入 字典树,再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值,再更新答案与边数。
最小生成树的个数只要根据乘法原理将边的数量相乘即可。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;

int n, anscnt, val[maxn], s[maxn], t[maxn];
long long sum;

struct Trie {
    int end[maxn * 30], next[maxn * 30][2];
    int size, root;

    int newNode()
    {
        next[size][0] = next[size][1] = 0;
        end[size++] = 0;
        return size - 1;
    }

    void init()
    {
        size = 0;
        root = newNode();
    }

    void insert(int x)
    {
        int cur = root;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (!next[cur][y])
                next[cur][y] = newNode();
            cur = next[cur][y];
        }
        end[cur]++;
    }

    pii search(int x)
    {
        int cur = root, ans = 0;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (next[cur][y])
                cur = next[cur][y], ans |= (y << i);
            else
                cur = next[cur][y ^ 1], ans |= ((y ^ 1) << i);
        }
        return make_pair(ans ^ x, end[cur]);
    }
} trie;

inline void read(int& x)
{
    char ch = getchar();
    x = 0;
    while (!(ch >= '0' && ch <= '9'))
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
}

int fastPow(int x, int y)
{
    int res = 1;
    while (y) {
        if (y & 1)
            res = 1LL * res * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return res;
}

void dac(int l, int r, int dep)
{
    if (l >= r)
        return;
    if (dep < 0) {
        if (r - l + 1 >= 2)
            anscnt = 1LL * anscnt * fastPow(r - l + 1, r - l - 1) % mod;
        return;
    }
    int lc = 0, rc = 0, ans = inf, cnt = 0;
    for (int i = l; i <= r; i++) {
        if ((val[i] >> dep) & 1)
            s[lc++] = val[i];
        else
            t[rc++] = val[i];
    }
    trie.init();
    for (int i = 0; i < lc; i++)
        val[l + i] = s[i];
    for (int i = 0; i < rc; i++) {
        val[l + lc + i] = t[i];
        trie.insert(t[i]);
    }
    pii tmp;
    for (int i = 0; i < lc; i++) {
        tmp = trie.search(s[i]);
        if (ans > tmp.first)
            ans = tmp.first, cnt = tmp.second;
        else if (ans == tmp.first)
            cnt += tmp.second;
    }
    if (cnt) {
        sum += ans;
        anscnt = 1LL * cnt * anscnt % mod;
    }
    dac(l, l + lc - 1, dep - 1);
    dac(l + lc, r, dep - 1);
}

int main()
{
    anscnt = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", val + i);
    dac(1, n, 30);
    printf("%lld\n%d\n", sum, anscnt);
    return 0;
}
Trie

Trie入门与模板

Posted on

简介

Trie ,又称前缀树或者是字典树,不仅在字符串的应用广泛,在数据结构中也有很多相应的题目,是数据结构中用空间兑换时间的典型。

下面是两个入门题

HDU 1251 统计难题

题意:
给定多个字符串,多个询问,问你以所询问字符串为前缀的字符串数量。

思路:
构造Trie,插入的时候打个顺便再对前缀计数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000005;
int ch[N][30], val[N], sz;

void insert(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k]) {
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 1;
            ch[u][k] = sz++;
        }
        else
            val[ch[u][k]]++;
        u = ch[u][k];
    }
}

int query(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k])
            return 0;
        u = ch[u][k];
    }
    return val[u];
}

int main() 
{
    char str[15];
    memset(ch[0], 0, sizeof(ch[0]));
    sz = 1;
    while (gets(str) && strlen(str) != 0)
        insert(str);
    while (scanf("%s", str) == 1)
        printf("%d\n", query(str));
    return 0;
}

HDU 1075 What Are You Talking About

题意:
给定字符串以及映射的字符串,再给定另几个字符串,让你把映射后的写出来。

思路:
大致的思路都是有的,构建Trie,再对每个单词进行查询。
但是!!!有非常非常多的坑!!!我觉得字符串的坑都这么多!!!
但是我写这篇博文实际上是我A题一周后了,具体哪些我也忘了……想知道,就看代码或者discuss吧。
真的是坑哭了…… 交了22发才A……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 500010;
const int sigma_size = 27;

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};

int main()
{
    Trie trie;
    char str[2][15];
    char buf[3005], ch;
    int id=0;
    scanf("%s", str[0]);
    while (scanf("%s", str[0]) && strcmp(str[0], "END") != 0) {
        scanf("%s", str[1]);
        trie.insert(str[1], str[0]);
    }
    scanf("%s", str[0]);
    getchar();
    while (scanf("%c", &ch)) {
        if (isalpha(ch))
            buf[id++] = ch;
        else {
            buf[id] = '\0';
            id = 0;
            if (strcmp(buf, "END") == 0)
                break;
            trie.query(buf);
            putchar(ch);
        }
    }
    return 0;
}

指针模板

query函数针对的是 hdu 1075

struct TrieNode {
    TrieNode* nxt[sigma_size];
    char* trans;
    char ch;
    bool isEnd;
    TrieNode()
    {
        trans = NULL;
        isEnd = false;
        memset(nxt, 0, sizeof ch);
    }
    ~TrieNode()
    {
        delete trans;
    }
};

struct Trie {
    TrieNode* root;
    Trie()
    {
        root = new TrieNode;
    }
    ~Trie()
    {
        freeTree(root);
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int len = strlen(s), idx;
        TrieNode *cur = root, *tmp;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                tmp = new TrieNode;
                tmp->ch = s[i];
                cur->nxt[idx] = tmp;
            }
            cur = cur->nxt[idx];
        }
        cur->isEnd=true;
        cur->trans = new char[strlen(tar) + 2];
        memcpy((cur->trans), tar, strlen(tar) + 1);
    }

    void query(char* s)
    {
        int len = strlen(s), idx;
        TrieNode* cur = root;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                printf("%s", s);
                return;
            }
            cur = cur->nxt[idx];
        }
        if (cur->isEnd)
            printf("%s", cur->trans);
        else
            printf("%s", s);
    }

    void freeTree(TrieNode* cur)
    {
        for (int i = 0; i < sigma_size; i++)
            if (cur->nxt[i])
                freeTree(cur->nxt[i]);
        delete cur;
    }
};

数组模板

query函数针对的是 hdu 1075

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};