AC自动机

HDU 2825 Wireless Password

Posted on

AC自动机+状压DP的入门题
虽然不是很好意思,但我的确是先看了kuangbin的代码再敲的。
从AC自动机构建矩阵开始起的出现的那个结点状态,在之后做题中越來越显著。
因为AC自动机本身也没多少地方可以改了,这是一个成熟的算法。而考研我们的运用就只能在理解熟悉它的状态,并运用它的状态。
关于状态应用最明显的就是DP了。

这题之后尽量不看题解……

说了一堆废话,下面放题解。

题意:
有一个长度为 n 的密码,给你一个 m 个字符串的集合。告诉你这个密码必定会包含这集合中的 k 个。
问密码的种数。

思路:
这道题应该是给出一个状态就很好理解了。
开一个三维数组,记 \( dp\left[ i \right] \left[ j \right] \left[ k \right] \) 为长度为 \( i \) ,在第\( j \) 个结点,含有字符串数量的状态为 \( k \) 的可构字符串数量。
每次在AC自动机上跑的时候更新一下状态,最后再将包含字符串数量大于等于 k 的状态数量累加即可。

相信我,真的是入门级的……

AC Code

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

using namespace std;

typedef unsigned long long ull;

const int mod = 20090717;
const int max_n = 110;
const int max_c = 26;
char buf[max_n];

int n, m, k;

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

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

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

    inline void insert(char str[], int id)
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (next[now][c] == -1)
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1 << id;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            end[now] |= end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_c + 2][max_n][1 << 10];

    int solve()
    {
        int ans = 0, ni, nj, ns;
        memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < size; j++)
                for (int state = 0; state < (1 << m); state++)
                    if (dp[i][j][state]) {
                        for (int x = 0; x < max_c; x++) {
                            ni = i + 1, nj = next[j][x], ns = state | end[nj];
                            dp[ni][nj][ns] = (dp[ni][nj][ns] + dp[i][j][state]) % mod;
                        }
                    }
        for (int state = 0; state < (1 << m); state++) {
            if (__builtin_popcount(state) < k)
                continue;
            for (int i = 0; i < size; i++)
                ans = (ans + dp[n][i][state]) % mod;
        }
        return ans;
    }
} aho;

int main()
{
    while (scanf("%d %d %d", &n, &m, &k) != EOF) {
        if (n == 0 && m == 0 && k == 0)
            break;
        aho.init();
        for (int i = 0; i < m; i++) {
            scanf("%s", buf);
            aho.insert(buf, i);
        }
        aho.build();
        printf("%d\n", aho.solve());
    }
    return 0;
}
最短路

HDU 1599 find the mincost route

Posted on

昨天晚上从Yasola那里偷来的一道题……

为什么Yasola这么优秀啊!!!!!
求求你别学了,我已经完全跟不上了……

因为看着题目并不是很难我也就写了一蛤,然后自以为是无脑题就疯狂WA……

emmmm…… 其实仔细想想还是挺简单的。

题意:
给你一张无向图,要你找出最小环。

点数 \( n \leq 100 \)

思路:
对 floyd 进行简单增加一点代码。
floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前,将其固定为环上的一个点,这点必定不会被所有最短路夹在中间。


有一个非常显然的问题就是,当我固定一个中间结点的时候,我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。

比如说
存在一个 ABCA 的环与一个 BCDB,其中 \( BD + DC < BC , AB + AC < BC \),而当我使 A 为固定结点,而我的 D 还不曾成为固定结点,也就不会被加入 BC 的最短路。

然而实际上并不要担心,这个环仍然会在floyd后期进行更新,因为对一个环来说,总存在最后一个被作为固定结点。
假设最糟糕的情况,D 结点是 ABCD 结点中最后一个被作为固定结点,那么不也能成功加入 BAC这条最短路径么。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 1e8;
const int maxn = 105;

int G[maxn][maxn];
int dis[maxn][maxn];

int main()
{
    int n, m, u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        range(i, 1, n) range(j, 1, n) G[i][j] = i == j ? 0 : inf;
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            G[u][v] = G[v][u] = min(G[u][v], w);
        }
        range(i, 1, n) range(j, 1, n) dis[i][j] = G[i][j];
        int ans = inf;
        range(k, 1, n)
        {
            range(i, 1, k - 1) range(j, i + 1, k - 1) ans = min(ans, dis[i][j] + G[i][k] + G[k][j]);
            range(i, 1, n) range(j, 1, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
        ans == inf ? printf("It's impossible.\n") : printf("%d\n", ans);
    }
    return 0;
}
Hash

BZOJ 4337 树的同构

Posted on

昨天的多校有一道需要树Hash的基础,于是就找到了这题。这题应该算得上是树Hash的裸题了。

树Hash的方法其实十分简单。有兴趣的看一下我的这篇 博文
然而上面那片博文是定根结点的,如果根节点固定,对于树的形态进行Hash,实际上是非常简单的。

再次简单说一下树Hash的原理,对于有根树,我们Hash的是树的形态,而树的形态则有每一层的结点个数与结点所连接的相同父亲结点所决定。
因此我们对于同一层的并且是同一个父亲的结点作一个相同的Hash,那么就得到了我们要得答案。

不过也有一个简单也正确的写法,就是将同一层并且具有相同孩子结点数量作同一个Hash,也可得到我们想要的结果。

但上述方法是针对有根树而言,如果不定根,则不好判断。
这是我们可以对小数据选择枚举所有结点,对较大数据选择寻找树的重心(不会超过两个)。

下面放上题解。

2017-8-14更新: 该理论用于有根树已经被推翻,对于无根树,也就是这道题,莫名适用,也许是数据水……

题意:
给你\( n \) 棵树,每棵树用给定每个结点的父亲予以表示。问对于每一棵树,与它同构的并且序号最小的是哪一棵。

思路:
数据非常小,只有不到50。我这里用了枚举 而且不也不会找重心
对于第 \( n \) 棵树,它的答案必然小于等于 \( n \)。

值得注意的是,这是无根树,\( 0 \) 结点不计其中。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

typedef long long ll;

const int maxn = 52;

int m, n;
int father;
int h[maxn][maxn], dep[maxn];

int prime[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277
};

int cnt[maxn];
vector<int> G[maxn];
queue<int> que;

int getHash(int root)
{
    memset(dep, 0, sizeof dep);
    int ret = 0, u;
    que.push(root), dep[root] = 1;
    while (!que.empty()) {
        u = que.front(), que.pop();
        ret += G[u].size() * prime[dep[u]];
        int sz = G[u].size();
        for (int i = 0; i < sz; i++) {
            if (!dep[G[u][i]]) {
                que.push(G[u][i]);
                dep[G[u][i]] = dep[u] + 1;
            }
        }
    }
    return ret;
}

int main()
{
    scanf("%d", &m);
    range(k, 1, m)
    {
        scanf("%d", &n);
        cnt[k] = n;
        range(i, 1, n) G[i].clear();
        range(i, 1, n)
        {
            scanf("%d", &father);
            if (father)
                G[father].push_back(i), G[i].push_back(father);
        }
        range(i, 1, n) h[k][i] = getHash(i);
        sort(h[k] + 1, h[k] + n + 1);
        range(i, 1, k) if (cnt[i] == n)
        {
            int j = 1;
            while (j <= n && h[k][j] == h[i][j])
                j++;
            if (j > n) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}