day 9 拓扑排序和哈希笔记

洪宇帆 · 2023 年7 月 18 日 10:51

~难度+=114514~

DAG，拓扑排序，哈希

有向无环图

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（ DAG 图）

拓扑排序

拓扑排序对一个 DAG G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若边 <u,v>∈E(G) ，则 u 在线性序列中出现在 v 之前
复杂度 O(n+m)
维护每个点的入度，每次将入度为 0 的点加入队列，并删除该点连出的边
用优先队列替换普通队列可求出字典序最小的拓扑排序
在 DAG 上进行动态规划 dis_u=\min(dis_v+edge(v\to u))

例题

NOI 2010 航空管制

法一：先用dp求出每个点能到达点的最紧要的点的k值
用这个值去贪心求拓扑序
但是第二问很难做:

求出每个航班在所有可行的起飞序列中的最小起飞序号
要求 O(n(n+m))，但是每次判断需要 O(n^3)
法二：令 p_i 表示拓扑序的位置
把 p_i\le k_i 倒过来，反向建图 => q_i=n-p_i+1,q_i\ge n-{k_i}+1
限制就变成：每个元素不能早于某个时刻被加入拓扑序
用两个队列维护，一个维护度数为 0 但是时间不满足的点，一个维护拓扑排序
每一轮新开始的时候，如果第一个队列中的点满足时间限制了就丢回拓扑排序的队列
第二问和第一问很像，在反图里跑拓扑，加个 if ，只有实在不能选了才选这个点

过了的证明

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5, maxm = 1e4 + 5;
int n,m,k[maxn],d[maxn],r[maxn],a[maxn],que[maxm << 2]; vector<int> mp[maxn],v[maxn];
void addEdge(int u,int v) { mp[u].push_back(v); d[v] ++; }
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i ++) { scanf("%d",&k[i]); v[k[i]].push_back(i); }
    for (int i = 1,u,v;i <= m;i ++) {
        scanf("%d%d",&u,&v);
        addEdge(v,u); // make G'
    }
    for (int i = 1;i <= n;i ++) r[i] = d[i] + 1;
    queue<int> q;
    for (int t = n,siz,u;t >= 1;t --) {
        siz = v[t].size();
        for (int j = siz - 1;j >= 0;j --) {
            r[v[t][j]] --;
            if (!r[v[t][j]]) q.push(v[t][j]);
        }
        u = q.front(); q.pop(); a[t] = u;
        for (auto vv : mp[u]) {
            r[vv] --;
            if (!r[vv]) q.push(vv);
        }
    }
    for (int i = 1;i <= n;i ++) printf("%d ",a[i]);
    putchar('\n');
    for (int u = 1,l,h;u <= n;u ++) {
        h = 1, l = 1;
        for (int i = 1;i <= n;i ++) r[i] = d[i] + 1;
        for (int t = n,siz,x;t >= 1;t --) {
            siz = v[t].size();
            for (int j = siz - 1;j >= 0;j --) {
                r[v[t][j]] --;
                if (!r[v[t][j]]) {
                    que[l ++] = v[t][j];
                    if (h < l - 1 && que[l - 2] == u)
                        swap(que[l - 2],que[l - 1]);
                }
            }
            x = que[h ++];
            if (x == u) { printf("%d ",t); break; }
            for (auto v : mp[x]) {
                r[v] --;
                if (!r[v]) {
                    que[l ++] = v;
                    if (h < l - 1 && que[l - 2] == u)
                        swap(que[l - 2],que[l - 1]);
                }
            }
        }
    }
    return 0;
}

Permutation Puzzle

每个点可填的区间为 [l_i,r_i] ，求拓扑序
具体做法和上一题很像，只是上下界有出入

image-20230718094407733657×436 126 KB

AC证明：

image-20230718181829696729×220 11.3 KB

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int ind[maxn], T, out[maxn], l[maxn], r[maxn], ans[maxn], id[maxn], n, m;
vector<int> mp[maxn], mpp[maxn]; bool cmp(int a, int b) { return l[a] < l[b]; }
void addEdge(int u,int v) { mp[u].push_back(v); mpp[v].push_back(u); ind[v] ++, out[u] ++; }
int main() {
    scanf("%d", &T);
    while (T --) {
        scanf("%d%d", &n, &m);
        for (int i = 1, x;i <= n;i ++) {
            scanf("%d", &x);
            if (x) l[i] = r[i] = x;
            else l[i] = 1, r[i] = n;
            mp[i].clear(); mpp[i].clear(); 
            ind[i] = out[i] = 0;
        }
        for (int i = 1,u,v;i <= m;i ++) {
            scanf("%d%d", &u, &v);
            addEdge(u,v);
        }
        queue<int> q;
        for (int i = 1;i <= n;i ++) if (!ind[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            // cout << u << '\n';
            for (auto v : mp[u]) {
                l[v] = max(l[v], l[u] + 1); ind[v] --;
                if (!ind[v]) q.push(v);
            }
        }
        for (int i = 1;i <= n;i ++) if (!out[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            // cout << u << '\n';
            for (int v : mpp[u]) {
                r[v] = min(r[v], r[u] - 1); out[v] --;
                if (!out[v]) q.push(v);
            }
        }
        for (int i = 1;i <= n;i ++) id[i] = i;
        sort(id + 1, id + n + 1, cmp);
        // for (int i = 1;i <= n;i ++) cout << id[i] << ' ';
        set<pair<int, int> > s; bool flag = true;
        for (int i = 1,pos = 1;i <= n;i ++) {
            while (pos <= n && l[id[pos]] <= i) {
                s.insert({r[id[pos]], id[pos]});
                pos++;
            }
            if (!s.size() || s.begin()->first < i) {
                flag = 0;
                break;
            }
            ans[s.begin() -> second] = i;
            s.erase(s.begin());
        }
        if (!flag) printf("-1");
        else { for (int i = 1;i <= n;i ++) printf("%d ", ans[i]); putchar('\n'); }
    }
    return 0;
}

哈希

哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射，将任意长度的输入消息 M 映射成为一个较短的定长哈希值 H(M) ，也叫散列值 (HashValue) 、杂凑值或消息摘要
我们定义一个把字符串映射到整数的函数，这个函数称为是 Hash 函数
在 Hash 函数值不一样的时候，两个字符串一定不一样
在 Hash 函数值一样的时候，两个字符串不一定一样
字符串不会变换 => 可以用前缀和维护任一子串的哈希值
字符串会变换 => 线段树维护哈希值：

hash[u]=hash[lc[u]]\times p^{size(rc[u])}+hash[rc[u]]
哈希的实现细节：
模数的选取
双哈希

例题

子串匹配问题

枚举匹配位置，哈希前缀和去验证

最长回文子串

枚举回文中心，二分两边能延伸到多长，check 用哈希检验（正串哈希值要等于反串哈希值）

最小表示法

BJOI 2015 树的同构

树哈希模板题
有根树：每个根节点可以被其子树的哈希值表示
把 a_1,a_2,a_3(若干子树的哈希值) 排序，按照字符串的方法把哈希值粘在一起
无根树：以每个树的重心为根求有根树哈希
但有一个问题：重心在边上
可以新建一个虚点，把贡献 size 设置为 0

P4503 [CTSC2014] 企鹅 QQ

枚举哪一位会被删掉，用类似于线段树哈希维护删掉的操作，最后判断剩下的是否相同

等差子序列

给一个 1 到 N 的排列 ${A_i}$ ，询问是否存在

1\le p_1<p_2<p_3<p_4<p_5<\dots <p_{Len}\le N(Len \ge3)

( Len 不是输入的数据) 使得 A{p_1},A{p_2},A{p_3},\dots,A{p_{Len}} 是一个等差序列

对于一个数值 x ，如果能作为等差中项，假设 x 在原序列的 p 位置，则两边如果用01序列表示那就是回文串
用线段树 + 哈希维护

P3333 [ZJOI2013] 丽洁体

枚举第一个单词最前面出现在哪里，结束位置尽可能靠前，答案就是最优的
最后一个单词同理
枚举B的开头位置，如果B匹配成功，就把不满足条件的全删掉

课后习题

电子表格计算器

此题题意没有讲清楚，不做也没关系 awa

杂物

从准备工作向完成前需要完成这个工作的工作连边，拓扑排序时 dp 更新每个任务完成的最小时间

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int n,t[maxn],d[maxn],w[maxn],ans; vector<int> mp[maxn]; queue<int> q;
void addEdge(int u,int v) { mp[v].push_back(u); d[u] ++; }
int main() {
    scanf("%d",&n);
    for (int i = 1,u,v;i <= n;i ++) {
        scanf("%d%d",&u,&t[i]);
        while (true) {
            scanf("%d",&v);
            if (!v) break;
            addEdge(u,v);
        }
    }
    for (int i = 1;i <= n;i ++)
        if (d[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop(); t[u] += w[u];
        // cout << u << ' ' << t[u] << '\n';
        for (auto v : mp[u]) {
            w[v] = max(w[v],t[u]);
            d[v] --;
            if (!d[v]) q.push(v);
        }   
    }
    for (int i = 1;i <= n;i ++) ans = max(ans,t[i]);
    printf("%d",ans);
    return 0;
}

第二饭堂

从左到右扫一遍，记录当前字符串正着的哈希值和反着的哈希值，如果相等则更新答案 f_i=f_{i/2}+1

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;

const int maxn = 5000005; const int base = 31,P = 1e9 + 7;
char t[maxn]; int m,f[maxn],ans = 0,S,T,e = 1;
int main() {
    scanf("%s",t + 1); m = strlen(t + 1);
    for (int i = 1;i <= m;i ++) {
        S = S * base + t[i]; T += t[i] * e; e *= base;
        if (S == T) f[i] = f[i >> 1] + 1; ans += f[i];
    }
    printf("%d",ans);
    return 0;
}

图的逆变换

通过手推几组样例可以得到： D 存在，当且仅当 E 中每个连通块中的点两两都有连边

然后就好判断力

#include<bits/stdc++.h>
using namespace std;
const int maxn = 305;
int T,m,k,mp[maxn][maxn]; bool x,y;
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d",&m,&k); memset(mp,0,sizeof(mp));
        for (int i = 1,x,y;i <= k;i ++) {
            scanf("%d%d",&x,&y);
            mp[x + 1][y + 1] ++; // 从1开始
        }
        bool flag = true;
        for (int i = 1;i <= m;i ++)
            for (int j = i + 1;j <= m;j ++) {
                x = false, y = false;
                for (int k = 1;k <= m;k ++) {
                    if (mp[i][k] && mp[j][k]) x = true;
                    if (mp[i][k] != mp[j][k]) y = true;
                    if (x && y) { flag = false; break; }
                }
            }
        if (flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

王睿樊 · 2023 年7 月 18 日 11:15

tjl

洪宇帆 · 2023 年7 月 18 日 11:16

DAG，拓扑排序，哈希

有向无环图

拓扑排序

例题

哈希

例题

子串匹配问题

最长回文子串

最小表示法

等差子序列

课后习题

我是蒟蒻