HAOI 2017 大赏

2020-03-01

HAOI 2017 的神秘弱省省选难度.

2017 年的 HAOI (大概? ) 是一天两试, 上午三题下午两题, 于是只有 5 道题了.

当年还有学长辛酸的故事…

「HAOI2017」新型城市化

题目链接

https://loj.ac/problem/2276

题意简述

给定一张图, 点数为 $n$, 给定 $m$ 条边不连, 满足图可被分成不超过两个完全图.

现在要加入一条原先不存在的边, 使得加入这条边后, 图的最大团大小至少比原图最大团大小至少增加 $1$.

求所有满足该性质的边.

其中, $1 \le n \le 10^4, 0 \le m \le \min \{ 1.5 \times 10^5, \frac{1}{2} n (n+1) \}$.

解题思路

首先可以发现, 给定的图, 也就是给定的不连接的边, 构成一张二分图.

考虑二分图的一些性质:

图的最大团 = 补图的最大独立集
二分图最大独立集 = 点数 - 二分图最小点覆盖
二分图最小点覆盖 = 二分图最大匹配

即使没有看出给定图为二分图, 由性质 1 也容易感性理解了.

根据这些性质, 容易发现我们直接用网络流跑二分图, 那么所求边就是二分图匹配中的必经边.

又有一些结论:

二分图匹配必经边在网络中流量为 $1$, 且两端点在 残量网络 中属于不同的强连通分量.
二分图匹配可行边在网络中流量为 $1$, 且两端点在 残量网络 中属于相同的强连通分量.

所以, 先将二分图黑白染色, 建图跑二分图最大匹配, 然后在残量网络上跑强连通分量, 最后依次判断给定边是否满足条件就好了.

时间复杂度为 $O(n + n \sqrt m + n + m + m \log m) = O(n \sqrt m)$.

~~看来二分图 & 网络流的那一套东西又忘了, 该回去看看了~~

代码实现

> 点击显示 / 隐藏

// LOJ #2276
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef pair<int, int> Pii;
const int MAXN = 1e4+5, MAXM = 15e4+5;
const int MAXV = MAXN, MAXE = MAXN * 2 + MAXM, INF = 0x3f3f3f3f;

int n, m, S, T;
Pii E[MAXM];
int id[MAXM], col[MAXN];
vector<Pii> Ans;

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXM << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }

    void dfs(int u) {
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if (col[v = edges[i].to] != 0) continue;
            col[v] = 3 - col[u], dfs(v);
        }
    }
}

namespace Dinic {
    struct Edge { int nxt, to, cap, flow; } edges[MAXE << 1];
    int head[MAXV], cur[MAXV], depth[MAXV], vis[MAXV], Time, eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline int AddEdge(int from, int to, int cap) {
        edges[++eidx] = (Edge){ head[from], to, cap, 0 };
        head[from] = eidx;
        edges[++eidx] = (Edge){ head[to], from, 0, 0 };
        head[to] = eidx;
        return eidx - 1;
    }

    inline bool BFS() {
        queue<int> Q;
        Q.push(S);
        vis[S] = ++Time, depth[S] = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                const Edge& e = edges[i];
                if (vis[e.to] != Time && e.cap > e.flow)
                    vis[e.to] = Time, depth[e.to] = depth[u] + 1, Q.push(e.to);
            }
        }
        return vis[T] == Time;
    }

    int DFS(int u, int a) {
        if (u == T || !a) return a;
        int f, flow = 0;
        for (int& i = cur[u]; ~i; i = edges[i].nxt) {
            Edge& e = edges[i];
            if (depth[e.to] == depth[u] + 1 && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                flow += f, a -= f, e.flow += f, edges[i^1].flow -= f;
                if (!a) break;
            }
        }
        return flow;
    }

    inline int Maxflow() {
        int flow = 0;
        while (BFS()) memcpy(cur, head, sizeof cur), flow += DFS(S, INF);
        return flow;
    }
}

namespace SCC {
    using namespace Dinic;
    int dfn[MAXV], low[MAXV], SCCidx[MAXV], SCCcnt, dfs_clock;
    int stk[MAXV], top;

    void tarjan(int u) {
        low[u] = dfn[u] = ++dfs_clock, stk[++top] = u;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            // 残量
            if (edges[i].flow == edges[i].cap) continue;
            if (!dfn[v = edges[i].to]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (!SCCidx[v]) low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            ++SCCcnt;
            while (true) {
                int x = stk[top--];
                SCCidx[x] = SCCcnt;
                if (u == x) break;
            }
        }
    }

    inline void solve() {
        for (int u = 1; u <= n + 2; ++u) if (!dfn[u]) tarjan(u);
        for (int i = 1; i <= m; ++i) {
            const int &u = E[i].first, &v = E[i].second;
            if (SCCidx[u] == SCCidx[v] || edges[id[i]].flow < 1) continue;
            Ans.push_back(E[i]);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init(), Dinic::init();
    // input
    read(n), read(m);
    S = n + 1, T = n + 2;
    for (int u, v, i = 1; i <= m; ++i) {
        read(u), read(v);
        if (u > v) swap(u, v);
        E[i] = Pii(u, v);
        Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    }
    // solve
    for (int u = 1; u <= n; ++u)
        if (col[u] == 0) col[u] = 1, Graph::dfs(u);
    for (int i = 1; i <= m; ++i) {
        const int &u = E[i].first, &v = E[i].second;
        if (col[u] == 1) id[i] = Dinic::AddEdge(u, v, 1);
        if (col[u] == 2) id[i] = Dinic::AddEdge(v, u, 1);
    }
    for (int u = 1; u <= n; ++u) {
        if (col[u] == 1) Dinic::AddEdge(S, u, 1);
        if (col[u] == 2) Dinic::AddEdge(u, T, 1);
    }
    Dinic::Maxflow();
    SCC::solve();
    // output
    printf("%lu\n", Ans.size());
    sort(Ans.begin(), Ans.end());
    for (size_t i = 0; i < Ans.size(); ++i)
        printf("%d %d\n", Ans[i].first, Ans[i].second);
    return 0;
}

「HAOI2017」方案数

~~既然有东方的神秘力量, 那么为什么答案对 998244353 取模…~~

题目链接

https://loj.ac/problem/2277

解题思路

~~容易看出来这题是计数 DP + 容斥.~~

先考虑没有障碍怎么做.

可以发现一个性质: 到达某一个点 $(x, y, z)$ 的方案数, 只和每个坐标在二进制表示中 $1$ 的个数有关.

设 $f(x, y, z)$ 表示某个坐标中 $1$ 的个数分别为 $x, y, z$, 那么可以写出转移:

$f(x,\ y,\ z) = \sum_{i=1}^x \binom{x}{i} f(x - i,\ y,\ z) + \sum_{j=1}^y \binom{y}{j} f(x,\ y - j,\ z) \\ + \sum_{k=1}^z \binom{z}{k} f(x,\ y,\ z - k)$

那么 $f(x, y, z)$ 可以在 $O(\log^ 3 n)$ 的时间内计算. ~~听说数据弱, 这样就有 80 pts?~~

考虑加上障碍怎么做.

设 $g(i)$ 表示从出发点到第 $i$ 个障碍的方案数. 如果不考虑其他障碍的影响, 那么直接从 $f(x, y, z)$ 转移就好了. 如果考虑, 则需要减去 $O \rightarrow j \rightarrow i$ 的方案数, 其中 $O \rightarrow j$ 就是 $g(j)$, $j \rightarrow i$ 可以通过 $f(x, y, z)$ 计算.

形式化一点, 即

$g(i) = f(x,\ y,\ z) - \sum_{j} g(j) \cdot f(x', y', z')$

其中的细节参考代码实现.

将终点 $(n, m, r)$ 加入障碍点, 则 $g(o)$ 即为答案.

时间复杂度 $O(\log^3 n + o \log o + o^2) = O(o^2)$. ~~o <= 1e4 当然是按信仰跑.~~

为了便于实现以及方便计算, 将所有障碍点按坐标依次从小到大排序. 并通过预处理加速统计某个数二进制下 $1$ 的个数.

~~感觉以后写 DP 还是发现什么性质就写写方程试试… 万一就对了呢…~~

代码实现

由于实现的问题, 所以我的代码跑得很满, 用时成功 loj 倒数第一.

以及这题数据比较弱, 每次只记录和 $(n, m, r)$ 有关的障碍, 就可以跑得飞快.

> 点击显示 / 隐藏

// LOJ #2277
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 61, BASE = (1 << 16) - 1;
const int MAXO = 1e4+5;
const int P = 998244353;

inline int pls(const int& a, const int& b) { return (a + b < P)? a + b: a + b - P; }
inline int mns(const int& a, const int& b) { return (a - b >= 0)? a - b: a - b + P; }

struct Item {
    LL x, y, z;
    bool operator < (const Item& rhs) const {
        return (x == rhs.x)? ((y == rhs.y)? z < rhs.z: y < rhs.y): x < rhs.x;
    }
} A[MAXO];

LL n, m, r, o;
int Bit[BASE + 1];
int C[MAXN][MAXN], f[MAXN][MAXN][MAXN], g[MAXO];

// 通过预处理, 计算一个 long long 范围数的 popcount
inline LL lowbit(const LL& x) { return x & -x; }
inline int __brute_popcount(LL x) {
    int ret = 0;
    while (x > 0) ++ret, x -= lowbit(x);
    return ret;
}

// 可以将其拆为 4 个小于 BASE 的部分统计
inline int __block_popcount(const LL& x) {
    return Bit[x & BASE] + Bit[(x >> 16) & BASE] + Bit[(x >> 32) & BASE] + Bit[(x >> 48) & BASE];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    for (int i = 1; i <= BASE; ++i) Bit[i] = __brute_popcount(i);
    // input
    read(n), read(m), read(r);
    read(o);
    for (int i = 1; i <= o; ++i) read(A[i].x), read(A[i].y), read(A[i].z);
    A[++o] = (Item){ n, m, r };
    // solve
    C[0][0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
    }
    f[0][0][0] = 1;
    for (int x = 0; x < MAXN; ++x)
        for (int y = 0; y < MAXN; ++y)
            for (int z = 0; z < MAXN; ++z) {
                for (int i = 1; i <= x; ++i)
                    f[x][y][z] = pls(f[x][y][z], 1LL * f[x-i][y][z] * C[x][i] % P);
                for (int j = 1; j <= y; ++j)
                    f[x][y][z] = pls(f[x][y][z], 1LL * f[x][y-j][z] * C[y][j] % P);
                for (int k = 1; k <= z; ++k)
                    f[x][y][z] = pls(f[x][y][z], 1LL * f[x][y][z-k] * C[z][k] % P);
            }
    sort(A+1, A+1+o);
    for (int i = 1; i <= o; ++i) {
        const Item& now = A[i];
        g[i] = f[__block_popcount(now.x)][__block_popcount(now.y)][__block_popcount(now.z)];
        for (int j = 1; j < i; ++j) {
            const Item& nxt = A[j];
            if ((nxt.x & now.x) != nxt.x || (nxt.y & now.y) != nxt.y || (nxt.z & now.z) != nxt.z) continue;
            int x = __block_popcount(now.x ^ nxt.x), y = __block_popcount(now.y ^ nxt.y),
                z = __block_popcount(now.z ^ nxt.z);
            g[i] = mns(g[i], 1LL * f[x][y][z] * g[j] % P);
        }
    }
    // output
    printf("%d\n", g[o]);
    return 0;
}

「HAOI2017」字符串

好久没写 AC 自动机了, 看到这道题人没了 = =

题目链接

https://loj.ac/problem/2278

解题思路

题目中将文本串 $S$ 和多个模式串 $p_i$ 匹配, 容易想到 AC 自动机.

以下涉及到反串的位置, 都是以原串位置为准

考虑题意中的匹配是什么意思. 也就是两个失配位置间隔 $k+1$. 换言之, 假设 $S$ 匹配到了位置 $i$, 那么让 $S$ 以 $i+k+1$ 结尾的反串匹配到当前节点对应模式串 $p$ 的反串就可以了.

这样不好统计, 我们建出 fail 树, 并在 fail 树上统计.

对于 AC 自动机的某个节点 $u$, 假设 $S$ 到达 $u$ 时同某个模式串 $p$ 匹配到位置 $i$, 我们要在 $u$ 在子树中找到某个节点 $v$, 设 $v$ 上 $S$ 匹配到第 $j$ 个位置, 则位置 $j + k + 1$ 对应节点, 要在 $p$ 的反串第 $i + k + 1$ 位对应节点的 fail 树内, 询问这样的 $v$ 的个数.

~~这段话虽然主语混乱, 但是很重要.~~

这就是一个树上数点的问题了, 可以使用树状数组以及差分解决.

还有一个问题, 每次计算 $S$ 上位置 $i$ 以及 $i + k + 1$ 的匹配时, 如果位置 $i + k$ 匹配, 那么会算重, 需要单独计算这部分的贡献来去重.

于是可以得到算法流程:

对所有 $p_i$ 的正反串建 AC 自动机, 把 $S$ 正反两次丢到 AC 自动机上匹配; 建 fail 树, 记录 $p_i$ 和 $S$ 对答案的影响, 也就是修改和查询操作, 并挂在 fail 树对应节点上; 树上差分统计子树信息即可. 因为要去重, 使用两个 BIT 统计.

注意特判 $p$ 长度小于等于 $k$ 的情况, 如果不特判只有 20 pts = =

代码实现

我也想知道为什么我的常数那么大, __stdcall 跑得那么快.

> 点击显示 / 隐藏

// LOJ #2278
// DeP
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 4e5+5, SIGMA = 95;

struct Ask {
    int type, idx, nd;
    Ask(int _t, int _i, int _n): type(_t), idx(_i), nd(_n) { }
};

int n, K;
char S[MAXN], P[MAXN];
int pos[2][MAXN], dfn[MAXN], size[MAXN];

int Ans[MAXN];
vector<Ask> Q[MAXN], M[MAXN];

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    int head[MAXN], eidx, dfs_clock;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }

    void dfs(int u) {
        size[u] = 1, dfn[u] = ++dfs_clock;
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            dfs(v = edges[i].to), size[u] += size[v];
    }
}

namespace AC {
    int ch[SIGMA][MAXN], fail[MAXN], nidx;

    inline void init() { nidx = 1; }

    inline int insert(const int & u, const int& v) {
        return ch[v][u]? ch[v][u]: (ch[v][u] = ++nidx);
    }

    void getFail() {
        queue<int> Q;
        fail[1] = 1;
        for (int c = 0; c < SIGMA; ++c) {
            int& v = ch[c][1];
            if (v) Q.push(v), fail[v] = 1; else v = 1;
        }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int c = 0; c < SIGMA; ++c) {
                int& v = ch[c][u];
                if (v) Q.push(v), fail[v] = ch[c][fail[u]];
                else v = ch[c][fail[u]];
            }
        }
        for (int i = 2; i <= AC::nidx; ++i) Graph::AddEdge(fail[i], i);
    }
}

struct BIT {
    int C[MAXN];

    inline int lowbit(const int& x) { return x & -x; }

    inline void Mdy(const int& d, const int& val) {
        for (int i = d; i <= Graph::dfs_clock; i += lowbit(i)) C[i] += val;
    }

    inline int Qry(const int& d) {
        int ret = 0;
        for (int i = d; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
    inline int Qry(const int& L, const int& R) { return Qry(R) - Qry(L-1); }
} T[2];

void solve(int u) {
    using namespace Graph;
    for (size_t i = 0; i < Q[u].size(); ++i) {
        const Ask& q = Q[u][i];
        Ans[q.idx] -= q.type * T[q.type < 0].Qry(dfn[q.nd], dfn[q.nd] + size[q.nd] - 1);
    }
    for (size_t i = 0; i < M[u].size(); ++i) {
        const Ask& m = M[u][i];
        T[m.type < 0].Mdy(dfn[m.nd], 1);
    }
    for (int i = head[u]; ~i; i = edges[i].nxt) solve(edges[i].to);
    for (size_t i = 0; i < Q[u].size(); ++i) {
        const Ask& q = Q[u][i];
        Ans[q.idx] += q.type * T[q.type < 0].Qry(dfn[q.nd], dfn[q.nd] + size[q.nd] - 1);
    }
}

inline int val(const char& c) { return c - 33; }

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    AC::init(), Graph::init();
    // input
    scanf("%d%s%d", &K, S + 1, &n);
    int Slgt = (int) strlen(S + 1);
    for (int j = 1; j <= n; ++j) {
        scanf("%s", P + 1);
        int Plgt = (int) strlen(P + 1);
        // 80pts = =
        if (Plgt <= K) { Ans[j] = Slgt - Plgt + 1; continue; }
        // AC-automaton
        for (int u = 1, i = 1; i <= Plgt; ++i) pos[0][i] = u = AC::insert(u, val(P[i]));
        for (int u = 1, i = Plgt; i >= 1; --i) pos[1][i] = u = AC::insert(u, val(P[i]));
        // maintain
        pos[0][0] = pos[1][Plgt + 1] = 1;
        for (int i = 0; i <= Plgt - K; ++i)
            Q[pos[0][i]].push_back(Ask(1, j, pos[1][i + K + 1]));
        for (int i = 1; i <= Plgt - K; ++i)
            Q[pos[0][i]].push_back(Ask(-1, j, pos[1][i + K]));
    }
    // solve
    AC::getFail(), Graph::dfs(1);
    // match
    pos[0][0] = pos[1][Slgt + 1] = 1;
    for (int i = 1; i <= Slgt; ++i) pos[0][i] = AC::ch[val(S[i])][pos[0][i - 1]];
    for (int i = Slgt; i >= 1; --i) pos[1][i] = AC::ch[val(S[i])][pos[1][i + 1]];
    // maintain
    for (int i = 0; i <= Slgt - K; ++i)
        M[pos[0][i]].push_back(Ask(1, 0, pos[1][i + K + 1]));
    for (int i = 1; i <= Slgt - K; ++i)
        M[pos[0][i]].push_back(Ask(-1, 0, pos[1][i + K]));
    solve(1);
    // output
    for (int i = 1; i <= n; ++i) printf("%d\n", Ans[i]);
    return 0;
}

「HAOI2017」八纵八横

在学线段树分治的时候, 看到这道题是 HAOI 就没有写, 于是去写了 CF938G Shortest Path Queries.

看到题目后, ???. 不过那场 EDU 是 18 年的… 估计是撞 idea 了 = =

题目链接

https://loj.ac/problem/2312

解题思路

那么这道题的思路就很显然了, 采用线段树分治, 对时间建线段树, 把边的编号挂在对应的节点上.

然后考虑如何计算答案. 由于这张图是连通的, 考虑图上的环, 容易发现可以构造出一条从 $1$ 开始又回到 $1$ 的路径, 使得仅有环上的路径经过奇数次.

那么可以记录环上的路径异或值, 并查询其中可以异或到的最大值. 可以使用并查集以及线性基完成.

不过这屑题中权值二进制位数是 $10^3$ 级别的, 使用 bitset 即可. 考虑到上面都是一些套路性的东西, 于是这道题的难点就是用 bitset 模拟了. = =

时间复杂度大概是 $O(q \frac{len}{w} \log q \log n)$ ?

代码实现

似乎不用写带撤销线性基? 偷懒每次直接大力复制当前线性基到线段树下一节点…

> 点击显示 / 隐藏

// LOJ #2312
// DeP
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 505, MAXM = 2005, MAXL = 1005;

struct Stk { int fu, fv, size; } stk[MAXM];

struct Modify {
    int u, v, L, R; bitset<MAXL> w;
} M[MAXM];

int n, m, q, top;
char str[MAXL];

bitset<MAXL> fix(char* S) {
    bitset<MAXL> ret;
    int lgt = (int) strlen(S);
    reverse(S, S + lgt);
    for (int i = 0; i < lgt; ++i) ret[i] = S[i] - '0';
    return ret;
}

struct LinerBasis {
    bitset<MAXL> A[MAXL];

    LinerBasis() { for (int i = 0; i < MAXL; ++i) A[i].reset(); }

    inline void insert(bitset<MAXL> x) {
        for (int i = MAXL-1; i >= 0; --i) if (x[i]) {
            if (!A[i].any()) { A[i] = x; break; }
            x ^= A[i];
        }
    }

    inline void Qry() {
        // max xor
        bitset<MAXL> ret; ret.reset();
        for (int i = MAXL-1; i >= 0; --i) if (!ret[i]) ret ^= A[i];
        // output
        int i = MAXL-1;
        while (i > 0 && !ret[i]) --i;
        while (i >= 0) putchar(ret[i--] + '0');
        putchar('\n');
    }
};

namespace DSU {
    int fa[MAXN], size[MAXN];
    bitset<MAXL> dist[MAXN];

    inline void init() {
        for (int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1, dist[i].reset();
    }

    inline int findfa(int u) {
        while (u != fa[u]) u = fa[u];
        return u;
    }
    inline bitset<MAXL> findist(int u) {
        bitset<MAXL> ret; ret.reset();
        while (u != fa[u]) ret ^= dist[u], u = fa[u];
        return ret;
    }
}

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    using namespace DSU;
    vector<int> dat[MAXM << 2];

    void Mdy(int nd, int L, int R, const int& opL, const int& opR, const int& idx) {
        if (opL <= L && R <= opR) return void( dat[nd].push_back(idx) );
        int Mid = (L + R) / 2;
        if (opL <= Mid) Mdy(lc, L, Mid, opL, opR, idx);
        if (opR > Mid) Mdy(rc, Mid+1, R, opL, opR, idx);
    }

    void Divide(int nd, int L, int R, LinerBasis S) {
        if (L > R) return;
        int k = top;
        for (size_t i = 0; i < dat[nd].size(); ++i) {
            const int& idx = dat[nd][i];
            int fu = findfa(M[idx].u), fv = findfa(M[idx].v);
            bitset<MAXL> w = M[idx].w ^ findist(M[idx].u) ^ findist(M[idx].v);
            if (fu == fv) S.insert(w);
            else {
                if (size[fu] < size[fv]) swap(fu, fv);
                fa[fv] = fu, size[fu] += size[fv], dist[fv] = w;
                stk[++top] = (Stk){ fu, fv, size[fv] };
            }
        }
        if (L == R) S.Qry();
        else {
            int Mid = (L + R) / 2;
            Divide(lc, L, Mid, S), Divide(rc, Mid+1, R, S);
        }
        while (top > k) {
            Stk u = stk[top--];
            dist[u.fv].reset(), fa[u.fv] = u.fv, size[u.fu] -= u.size;
        }
    }
#undef lc
#undef rc
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d%d", &n, &m, &q);
    LinerBasis S;
    DSU::init();
    for (int u, v, i = 1; i <= m; ++i) {
        scanf("%d%d%s", &u, &v, str);
        using namespace DSU;
        int fu = findfa(u), fv = findfa(v);
        bitset<MAXL> w = fix(str) ^ findist(u) ^ findist(v);
        if (fu == fv) S.insert(w);
        else {
            if (size[fu] < size[fv]) swap(fu, fv);
            fa[fv] = fu, size[fu] += size[fv], dist[fv] = w;
        }
    }
    S.Qry();
    // solve
    // 指定编号就很难受 = =
    int idx = 0, ex = 550;
    for (int i = 1; i <= q; ++i) {
        static int x, y, k; static char opt[16];
        scanf("%s", opt);
        switch (opt[1]) {
            case 'd':
                scanf("%d%d%s", &x, &y, str);
                M[++idx] = (Modify){ x, y, i, -1, fix(str) };
                break;
            case 'a': scanf("%d", &k), M[k].R = i - 1; break;
            case 'h':
                scanf("%d%s", &k, str);
                M[++ex] = M[k];
                M[ex].R = i - 1, M[k].L = i, M[k].w = fix(str);
                break;
            default: fprintf(stderr, "ERR\n");
        }
    }
    // output
    for (int i = 1; i <= idx; ++i) {
        if (M[i].R == -1) M[i].R = q;
        if (M[i].L <= M[i].R) SGT::Mdy(1, 1, q, M[i].L, M[i].R, i);
    }
    for (int i = 551; i <= ex; ++i)
        if (M[i].L <= M[i].R) SGT::Mdy(1, 1, q, M[i].L, M[i].R, i);
    // DSU::init();
    SGT::Divide(1, 1, q, S);
    return 0;
}

「HAOI2017」供给侧改革

出题人终于承认数据是他用脚随的了.

题目链接

https://loj.ac/problem/2313

解题思路

~~根据题目中 “串 S 中的每一位都是在 0 和 1 之间随机产生的” 可以猜测, 这道题适合瞎搞.~~

既然数据随机, 那么很多不对劲的算法就可以拿过来用了.

~~似乎可以直接猜最长 LCP 长度然后大力枚举?~~

还是考虑一种看起来对劲的做法, 先建出原串的后缀树. 这里采用对反串建 SAM, 后缀链接就是原串的后缀树了.

将所有询问离线, 按 $R$ 从小到大排序, 扫描 $S$ 的每一位, 每次在后缀树上更新一条链, 在后缀树上维护最长 LCP 大小 MaxLCP, 以及节点和前缀长度对应到 $S$ 上的最靠后位置, 分别记作 idx[u] 和 Lidx[l].

如果当前扫描位置包含了某个询问的区间, 就把这个询问拿出来计算答案. 从大到小枚举最长 LCP 长度, 如果当前长度 $i$ 对应的 Lidx[i] 比记录的上一次更新位置 lst 要大就更新答案.

由于答案的单调性, 也就是 $[L, R]$ 的答案一定大于等于 $[L+1, R], \ldots, [R-1, R]$, 所以分块计算的正确性可以得到保证.

时间复杂度 $O(\texttt{玄学})$.

代码实现

> 点击显示 / 隐藏

// LOJ #2313
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1e5+5;

struct Ask {
    int idx, L, R;
    bool operator < (const Ask& rhs) const {
        return R < rhs.R || (R == rhs.R && L < rhs.L);
    }
} Q[MAXN];

int n, q;
char S[MAXN];
int pos[MAXN], Ans[MAXN];

namespace SAM {
    const int MAXN = ::MAXN << 1, SIGMA = 2;
    int ch[SIGMA][MAXN], lnk[MAXN], len[MAXN], nidx, last;
    int idx[MAXN], Lidx[MAXN], MaxLCP;

    inline void init() { nidx = last = 1; }

    inline int insert(int val) {
        int nd = ++nidx, p = last;
        len[nd] = len[last] + 1;
        while (p && !ch[val][p]) ch[val][p] = nd, p = lnk[p];
        if (!p) lnk[nd] = 1;
        else {
            int q = ch[val][p];
            if (len[q] == len[p] + 1) lnk[nd] = q;
            else {
                int nxt = ++nidx;
                len[nxt] = len[p] + 1, lnk[nxt] = lnk[q];
                ch[0][nxt] = ch[0][q], ch[1][nxt] = ch[1][q];
                while (p && ch[val][p] == q) ch[val][p] = nxt, p = lnk[p];
                lnk[q] = lnk[nd] = nxt;
            }
        }
        return last = nd;
    }

    inline void Upd(int R) {
        for (int u = pos[R]; u > 1; u = lnk[u]) {
            if (idx[u]) {
                MaxLCP = max(MaxLCP, len[u]);
                Lidx[len[u]] = max(Lidx[len[u]], idx[u]);
            }
            idx[u] = max(idx[u], R);
        }
    }

    inline int Qry(int L) {
        int ret = 0;
        for (int lst = L - 1, i = MaxLCP; i >= 1; --i)
            if (lst < Lidx[i]) ret += i * (Lidx[i] - lst), lst = Lidx[i];
        return ret;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    SAM::init();
    // input
    scanf("%d%d%s", &n, &q, S+1);
    for (int L, R, i = 1; i <= q; ++i)
        scanf("%d%d", &L, &R), Q[i] = (Ask){ i, L, R };
    // solve
    for (int i = n; i; --i) pos[i] = SAM::insert(S[i] - '0');
    sort(Q+1, Q+1+q);
    for (int idx = 1, i = 1; i <= n; ++i) {
        SAM::Upd(i);
        while (idx <= q && Q[idx].R <= i)
            Ans[Q[idx].idx] = SAM::Qry(Q[idx].L), ++idx;
    }
    // output
    for (int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
    return 0;
}

DepletedPrism's Blog

HAOI 2017 大赏

「HAOI2017」新型城市化

题目链接

题意简述

解题思路

代码实现

「HAOI2017」方案数

题目链接

解题思路

代码实现

「HAOI2017」字符串

题目链接

解题思路

代码实现

「HAOI2017」八纵八横

题目链接

解题思路

代码实现

「HAOI2017」供给侧改革

题目链接

解题思路

代码实现