九省联考 2018 大赏

2020-03-11

高一玩泥巴的时候陪着学长做过… 然而只是暴力的忠实选手.

~~结果现在还是暴力的忠实选手.~~

「九省联考 2018」一双木棋

题目链接

https://loj.ac/problem/2471

解题思路

当年真是菜啊… 看不懂状压.

落子的规则很有意思, 手玩以后可以发现, 落子的形状是一个上三角…

考虑到 $n, m \le 10$, 可以状压表示这个上三角的轮廓. 具体地说, 用一条包含 0 / 1 的序列表示一条从左下角到右上角的轮廓线.

假如用 1 表示轮廓线中横线, 用 0 表示竖线, 那么起始状态就是 ((1 << m) - 1) << n, 最终的状态为 (1 << m) - 1. (从低位到高位, 从左下角到右上角)

此时每落一子就是把形同 10 的位置改为 01. 在扫描状态的同时确定就可以确定落子位置.

接下来就很常规了. 记 $f(S)$ 表示状态 $S$ 最大得分差值. 考虑到转移比较抽象, 于是用记忆化搜索实现, 并记录当前是轮到谁落子, 在转移时对应取 $\max$ / $\min$ 以确保正确性.

代码实现

> 点击显示 / 隐藏

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

const int MAXN = 10;
const int INF = 0x3f3f3f3f;

int n, m;
int A[MAXN][MAXN], B[MAXN][MAXN];

int f[1 << (MAXN << 1)];
bool vis[1 << (MAXN << 1)];

int dfs(int sta, int s) {
    if (vis[sta]) return f[sta];
    int& ret = f[sta];
    ret = s? -INF: INF;
    int x = n, y = 0;
    for (int i = 0; i < n + m - 1; ++i) {
        if ((sta >> i) & 1) ++y; else --x;
        if (((sta >> i) & 3) != 2) continue;
        if (s) ret = max(ret, dfs(sta ^ (3 << i), s ^ 1) + A[x][y]);
        else ret = min(ret, dfs(sta ^ (3 << i), s ^ 1) - B[x][y]);
    }
    return vis[sta] = true, ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) scanf("%d", A[i] + j);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) scanf("%d", B[i] + j);
    // solve
    int ed = (1 << m) - 1;
    vis[ed] = true, f[ed] = 0;
    // output
    printf("%d\n", dfs(((1 << m) - 1) << n, 1));
    return 0;
}

「九省联考 2018」IIIDX

题目链接

https://loj.ac/problem/2472

解题思路

可以发现曲目的解锁顺序构成了一个树形结构, 要求当前节点的权值 $\le$ 其子树内的权值.

于是有一个朴素的想法, 即后序遍历这棵树, 把权值从大到小依次填进去.

但是存在相同权值的时候这个贪心会有问题. 为什么?

考虑一组样例 from HocRiser

1 2	4 2.0 1 1 1 2

这样在填以 $2$ 为根的子树的时候, 节点 $4$ 的点权为 $2$. 但此时 $4$ 的点权为 $1$, 而把权值 $2$ 丢给 $3$ 可以得到更优的答案…

接下来考虑如何避免相等权值的影响.

首先有一个事实, 可能填入权值的节点一定和已经填入权值的节点相邻.

现在我们维护出节点 $u$ 子树大小 size[u]. 并加入一个 “预约” 操作, 也就是把当前可填但未填的节点 (也就是其父亲都填完了) 的子树大小放入线段树中.

将权值从小到大排序, 每次填入一个权值, 处理出相同权值所在区间 $[L, R]$.

在该区间内从后往前枚举, 设当前是从前到后第 $k$ 个相等权值, 在线段树上二分一个位置 $u$, 并将当前权值填入 $u$. 同时把 $u$ 的子树大小从线段树中删去, 再把 $u$ 儿子 $v$ 的子树大小加入线段树.

线段树上二分时, 找到标号从大到小第一个合法节点 $u$, 使其满足线段树上大于 $u$ 标号的子树大小总和 $> k$.

感性解释一下, 每个节点 $u$ 为其子孙预留了 size[u] 个位置, 填相同权值时需要考虑 “预约” 的影响, 并做出最优的选择. 也就是把靠后的位置, 在合法的情况下填入尽量小的权值. 线段树上二分的过程, 就是在满足限制的同时找到这个 “靠后的位置”.

时间复杂度 $O(n \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #2472
// DeP
#include <cmath>
#include <cctype>
#include <cstdio>
#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;

const int MAXN = 5e5 + 5;

int n; double K;
int A[MAXN], Ans[MAXN];

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    int datSum[MAXN << 2];

    void Mdy(int nd, int L, int R, const int& pos, const int& val) {
        datSum[nd] += val;
        if (L == R) return;
        int Mid = (L + R) / 2;
        if (pos <= Mid) Mdy(lc, L, Mid, pos, val);
        else Mdy(rc, Mid+1, R, pos, val);
    }

    int Qry(int nd, int L, int R, const int& k) {
        if (L == R) return L;
        int Mid = (L + R) / 2, d = datSum[rc];
        if (k > d) return Qry(lc, L, Mid, k - d);
        return Qry(rc, Mid+1, R, k);
    }
#undef lc
#undef rc
}

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

    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;
        size[from] += size[to];
    }

    inline void solve() {
        // pre done
        init();
        for (int i = 1; i <= n; ++i) size[i] = 1;
        for (int i = n; i; --i) AddEdge(floor(i / K), i);
        // solve
        for (int v, i = head[0]; ~i; i = edges[i].nxt)
            v = edges[i].to, SGT::Mdy(1, 1, n, v, size[v]);
        sort(A+1, A+1+n);
        for (int L = 1; L <= n; ++L) {
            int R = L;
            while (R < n && A[R+1] == A[L]) ++R;
            for (int j = R - L + 1; j; --j) {
                int u = SGT::Qry(1, 1, n, j);
                Ans[u] = A[L], SGT::Mdy(1, 1, n, u, -size[u]);
                for (int v, i = head[u]; ~i; i = edges[i].nxt)
                    v = edges[i].to, SGT::Mdy(1, 1, n, v, size[v]);
            }
            L = R;
        }
        // output
        for (int i = 1; i <= n; ++i) printf("%d%c", Ans[i], " \n"[i == n]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    scanf("%d%lf", &n, &K);
    for (int i = 1; i <= n; ++i) read(A[i]);
    Graph::solve();
    return 0;
}

「九省联考 2018」秘密袭击

题目链接

https://loj.ac/problem/2473

解题思路

~~首先, 有正解 “线段树合并, 拉格朗日插值, 生成函数, 以及整体 DP“.~~

考虑到本题时限 5s, 以及正解繁杂常数大, 于是暴力碾标算…

枚举 Access Globe 所操控士兵潜入的城市 $u$, 考虑潜入 $u$ 的方案数.

如果节点 $u$ 可以对答案产生贡献, 那么包含 $u$ 的连通块内一定有 $k-1$ 个满足 $d_i > d_u$ 的节点. 把权值小于 $d_u$ 的节点大小标记为 $0$, 把权值大于 $d_u$ 的节点标记为 $1$, 做一个类似于树形背包的 DP 即可.

那么权值等于 $d_u$ 的呢? 为避免对某个节点重复计算, 在权值相等的时候, 仅考虑编号大于等于 (别忘了自己) $u$ 的节点.

具体地说, 设 $f(i, j)$ 表示深度最小节点为 $i$, 大小和为 $j$ 的连通块个数.

枚举每条边 $(u, v)$, 设 $g(i)$ 表示选择 $u$ 其余节点, 以及 $v$ 的子树内节点, 大小总和为 $i$ 的连通块个数, 显然转移是一个卷积的形式, 最后把 $g(i)$ 累加到 $f(u, i)$ 上就好了.

以及一些卡常的方法.

使用 SDOI 2017 苹果树同样的技巧, DP 数组 $f$ 开成一维, 减少 cache miss.
转移数组 $g$ 使用 long long, 减少取模次数.
考虑到树是一个稀疏图, 于是使用 vector 存图, 相比手写链表访问加快.

~~然后没了, 难道要把 g 的转移用 MTT 优化?~~

时间复杂度 $O(nk(n-k))$.

~~如果有机会, 我一定会去学正解~~

代码实现

> 点击显示 / 隐藏

// LOJ #2473
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
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 long long LL;
const int MAXN = 1675, P = 64123;

int n, K, W, T, M;
LL g[MAXN];
int A[MAXN], V[MAXN], f[MAXN * MAXN], size[MAXN];

vector<int> G[MAXN];

void dfs(int u, int fa) {
    memset(f + u * M, 0, T);
    f[u * M + V[u]] = 1, size[u] = V[u];
    for (auto v: G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int j = 0; j <= K && j <= size[u]; ++j)
            for (int k = 0; k <= K && k <= size[v]; ++k)
                g[j + k] += 1LL * f[u * M + j] * f[v * M + k];
        size[u] += size[v];
        for (int j = 0; j <= K && j <= size[u]; ++j)
            f[u * M + j] = (f[u * M + j] + g[j]) % P, g[j] = 0;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(K), read(W);
    M = K + 1, T = M * sizeof (int);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int u, v, i = 1; i < n; ++i)
        read(u), read(v), G[u].push_back(v), G[v].push_back(u);
    // solve
    int ans = 0;
    for (int cnt, u = 1; u <= n; ++u) {
        cnt = 0;
        for (int i = 1; i <= n; ++i)
            V[i] = (A[i] > A[u] || (A[i] == A[u] && i >= u)), cnt += V[i];
        if (cnt < K) continue;
        dfs(u, 0), ans = (ans + A[u] * f[u * M + K] % P) % P;
    }
    // output
    printf("%d\n", ans);
    return 0;
}

「九省联考 2018」劈配

题目链接

https://loj.ac/problem/2477

解题思路

容易发现, 题目要求我们做的就是一个二分图匹配. 考虑用网络流解决这个问题.

对于第一问, 从 $1$ 到 $n$ 依次考虑每个选手 $i$ 的匹配情况.

如果只有一位选手 $i$, 那么

新建源汇 $S$, $T$, 其中 $S$ 对选手 $i$ 连边, 容量为 $1$; 每位导师 $j$ 向 $T$ 连边, 容量为 $b_j$.
枚举选手志愿, $i$ 向该档志愿导师 $j$ 连边, 容量为 $1$.
- 如果此时存在增广路, 那么该选手被该档志愿录取
- 否则继续枚举志愿, 直到选手被录取 / 出局

考虑其他选手的影响. 由录取方案的最优性可知, 只有排名比 $i$ 靠前的选手对 $i$ 有影响, 那么每位选手直接在上一位选手的残量网络上建边即可.

未被枚举到的志愿录取时, 需要及时把此档志愿所建的边回退掉, 以避免多出用不到的废边, 从而影响时间复杂度的正确性…

对于第二问, 可以发现答案可以二分 —- 如果选手到了第 $1$ 名, 还不能达到自己的要求, 那肯定会沮丧了.

我们二分一个答案 $x$, 表示选手 $i$ 不沮丧时的 最小排名. check 的时候前 $x-1$ 名选手的录取情况并不会改变, 再次基础上加入选手 $i$ 的前 $s_i$ 个志愿, 判断新图是否存在增广路即可.

每次都建一次新图, 并把前 $x-1$ 名选手匹配好有些麻烦, 时间复杂度还很高. 考虑到解决第一问时, 已经把这些匹配求过一遍了, 所以记录选手录取情况的前缀图, 每次 check 调用即可. 因为点数很小, 所以可以保证每次暴力复制的复杂度.

时间复杂度大概是 $O( T(n^2m + n^2 \log n) )$?

代码实现

由于这道题的特殊性, Dinic 当前弧优化并不适用.

> 点击显示 / 隐藏

// LOJ #2477
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <vector>
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;

const int MAXN = 205, MAXV = MAXN << 1;
const int INF = 0x3f3f3f3f;

int n, m, C, S, T;
vector<int> A[MAXN][MAXN];
int Ans1[MAXN], Ans2[MAXN], B[MAXN], s[MAXN];

struct Edge {
    int to, flow, cap;
    Edge() { }
    Edge(int _v, int _c): to(_v), cap(_c) { flow = 0; }
};

struct Graph {
    vector<Edge> edges;
    vector<int> G[MAXV];
    int depth[MAXV], vis[MAXV], Time;

    inline void init() {
        edges.clear();
        for (int i = 0; i <= n + m + 1; ++i) G[i].clear();
    }

    inline void AddEdge(int from, int to, int c) {
        edges.push_back(Edge(to, c)), edges.push_back(Edge(from, 0));
        int eidx = edges.size() - 1;
        G[from].push_back(eidx - 1), G[to].push_back(eidx);
    }
    inline void DelEdge(int from, int to) {
        G[from].pop_back(), G[to].pop_back();
    }

    bool BFS() {
        queue<int> Q;
        Q.push(S), vis[S] = ++Time, depth[S] = 1;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (size_t i = 0; i < G[u].size(); ++i) {
                const Edge& e = edges[G[u][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 (size_t i = 0; i < G[u].size(); ++i) {
            Edge& e = edges[G[u][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[G[u][i]^1].flow -= f;
                if (!a) break;
            }
        }
        return flow;
    }
} G[MAXN];

inline bool check(int Mid, const int& u) {
    static Graph now;
    now = G[Mid - 1], now.AddEdge(S, u, 1);
    for (int j = 1; j <= s[u]; ++j)
        for (size_t k = 0; k < A[u][j].size(); ++k) now.AddEdge(u, n + A[u][j][k], 1);
    return now.BFS();
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti), read(C);
    while (Ti--) {
        read(n), read(m);
        // init
        S = 0, T = n + m + 1;
        G[0].init();
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= m; ++j) A[i][j].clear();
        // input
        for (int i = 1; i <= m; ++i) read(B[i]);
        for (int x, i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) read(x), A[i][x].push_back(j);
        for (int i = 1; i <= n; ++i) read(s[i]);
        // solve
        for (int i = 1; i <= m; ++i) G[0].AddEdge(n + i, T, B[i]);
        // Q1
        for (int i = 1; i <= n; ++i) {
            Ans1[i] = 0;
            G[i] = G[i - 1], G[i].AddEdge(S, i, 1);
            for (int j = 1; j <= m; ++j) {
                for (size_t k = 0; k < A[i][j].size(); ++k) G[i].AddEdge(i, n + A[i][j][k], 1);
                if (G[i].BFS()) { G[i].DFS(S, INF), Ans1[i] = j; break; }
                for (size_t k = 0; k < A[i][j].size(); ++k) G[i].DelEdge(i, n + A[i][j][k]);
            }
            if (!Ans1[i]) Ans1[i] = m + 1;
        }
        // Q2
        for (int i = 1; i <= n; ++i) {
            Ans2[i] = 0;
            if (s[i] >= Ans1[i]) continue;
            int L = 1, R = i - 1, ans = -1;
            while (L <= R) {
                int Mid = (L + R) / 2;
                if (check(Mid, i)) ans = Mid, L = Mid + 1; else R = Mid - 1;
            }
            Ans2[i] = (ans == -1)? i: i - ans;
        }
        // output
        for (int i = 1; i <= n; ++i) printf("%d%c", Ans1[i], " \n"[i == n]);
        for (int i = 1; i <= n; ++i) printf("%d%c", Ans2[i], " \n"[i == n]);
    }
    return 0;
}

「九省联考 2018」林克卡特树

人生第一道 DP 凸优化…

题目链接

https://loj.ac/problem/2478

解题思路

首先对题意做一步转化, 所求即为选择 $K+1$ 条不相交的链, 所得的最大边权和.

此时有一个朴素的 DP, 设 $f(i, j, k)$ 表示以节点 $i$ 为根的子树内, 选择 $j$ 条链, 且节点 $i$ 度数为 $k \in \{ 0, 1, 2 \}$ 的最大边权和. (度数为 $0$ 的情况就是单独一个节点被视作一条链了)

此时枚举儿子大力讨论即可列出转移… 转移相当繁琐 = =

这个 DP 的时间复杂度为 $O(nk^2)$, 看起来没有什么优化的余地了, 真的是这样吗?

通过某些神秘手段可以得知, 选择 $K+1$ 条链的最优解是上凸的. 换句话说, 以选择链数 $k$ 为横坐标, 最大边权和为纵坐标, 得到的函数图像是上凸的 (其实图像是个点集… 感性理解). 再者就是导函数单调 / 差分单调了…

感性理解一下这个上凸, 刚开始选择一些边作为链, 可以把某些对答案贡献较小情况的避开. 当要求选择的链数逐渐增加时, 这个 “避开” 的应用范围就逐渐缩小, 而不得不减小答案来满足限制.

接着考虑 DP 凸优化.

我们二分一个权值 $s$, 并限定每新增一条链, 就在把边权和减去 $s$. 此时不限定选择多少条链.

丢掉对链个数的限制, 容易得到一个 $O(n)$ 的 DP:

设 $f(i, j)$ 表示以节点 $i$ 为根的子树内, 且节点 $i$ 度数为 $j \in \{ 0, 1, 2 \}$ 的最大边权和, 以及达到该边权和所用的最少链数.

首先有初值

$f(u, 0) = 0,\ f(u, 1) = 0$ $f(u, 2) = \max\{ 0, -s \}$

记边 $(u, v)$ 边权为 $w(u, v)$, 那么转移为

$f(u, 0) = \max\{ f(u, 0),\ f(u, 0) + f(v, 0) \}$ $f(u, 1) = \max\{ f(u, 1),\ f(u, 1) + f(v, 0),\ f(u, 0) + f(v, 1) + w(u, v) \}$ $f(u, 2) = \max\{ f(u, 2),\ f(u, 2) + f(v, 0),\ f(u, 1) + f(v, 1) + w(u, v) - s \}$

以及一个节点 DP 完后, 还需要合并答案.

$f(u, 0) = \max\{ f(u, 0),\ f(u, 1) - s,\ f(u, 2) \}$

这样就能解释通了… 只用度数考虑 ~~会发现解释不通~~

这一步的 DP 就相当于拿一条斜率为 $s$ 的直线去切这个图像, 并得到凸包上一点 $(k, f(1, 0))$. 接着根据 $k$ 和 $K+1$ 的关系来调整斜率, 直到同凸包交点为 $(K+1, f(1, 0))$.

时间复杂度 $O(n \log w)$. 其中 $w$ 为答案上下界之差.

代码实现

> 点击显示 / 隐藏

// LOJ #2478
// DeP
#include <cctype>
#include <cstdio>
#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 long long LL;
const int MAXN = 3e5 + 5;

struct Item {
    LL a; int b;
    Item(LL _a = 0, int _b = 0): a(_a), b(_b) { }
    bool operator < (const Item& rhs) const {
        return a < rhs.a || (a == rhs.a && b > rhs.b);
    }
    Item operator + (const Item& rhs) const { return Item(a + rhs.a, b + rhs.b); }
};

int n, K;
Item f[MAXN][3];

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

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

    void dfs(int u, int fa, const LL& s) {
        f[u][0] = f[u][1] = Item(0, 0);
        f[u][2] = max(Item(0, 0), Item(-s, 1));
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == fa) continue;
            dfs(v, u, s);
            f[u][2] = max(f[u][2], max(f[u][2] + f[v][0], f[u][1] + f[v][1] + Item(edges[i].w - s, 1)));
            f[u][1] = max(f[u][1], max(f[u][1] + f[v][0], f[u][0] + f[v][1] + Item(edges[i].w)));
            f[u][0] = max(f[u][0], f[u][0] + f[v][0]);
        }
        // 此处合并答案
        f[u][0] = max(f[u][0], max(f[u][1] + Item(-s, 1), f[u][2]));
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n), read(K), ++K;
    LL L = 0, R = 0;
    for (int u, v, w, i = 1; i < n; ++i) {
        read(u), read(v), read(w);
        L = min(L, -1LL * w), R += max(0, w);
        Graph::AddEdge(u, v, w), Graph::AddEdge(v, u, w);
    }
    // solve
    LL ans = -1;
    while (L <= R) {
        LL Mid = (L + R) / 2;
        Graph::dfs(1, 0, Mid);
        if (f[1][0].b <= K) ans = Mid, R = Mid - 1; else L = Mid + 1;
    }
    Graph::dfs(1, 0, ans);
    // output
    printf("%lld\n", f[1][0].a + ans * K);
    return 0;
}

「九省联考 2018」制胡窜

题目链接

https://loj.ac/problem/2479

解题思路

有着很复杂的分类讨论, 以及相当繁琐的细节…

~~还是 Labelray 讲地好哇.~~

还是拿 Labelray 的题解再展开说一点东西.

对于 Case 2.1, 我个人认为最终的答案应为

$\sum_{i=1}^{n-1} (r_{i+1} - l_n) \cdot (l_{i+1} - l_i)$

化简之后可以得到

$\sum_{i=1}^{n-1} r_{i+1} (r_{i+1}-r_i) - l_n \cdot \sum_{i=1}^{n-1} (r_{i+1} - r_i)$

以及 Case 3, 在满足限制 $l_n < r_{i+1} < r_1 + len - 1$ 时, 直接在线段树上查询区间 $(l_n, r_1 + len - 1]$, 则会缺失左边界.

具体地说, 由于使用右端点 $r_i$ 的差代替左端点 $l_i$ 的差, 在计算时会漏掉 $r_i < l_n < r_{i+1}$ 的情况, 但此时对应左边一刀切在 $(l_i, l_{i+1})$ 的情况仍然合法. 于是在统计中需要加入 $[1, l_n]$ 的最大端点, 同线段树查询结果合并即可.

时间复杂度 $O(n \log n + q \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #2479
// DeP
#include <cctype>
#include <cstdio>
#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 long long LL;
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5, LOG = 19;

inline LL C2(int n) { return 1LL * n * (n-1) / 2; }

int n, q;
char S[MAXN];
int rt[MAXM], pos[MAXN], pre[LOG][MAXM];

struct Data {
    int mx, mn; LL s1, s2;

    Data() { mx = -MAXN, mn = MAXN, s1 = s2 = 0; }
    Data(int _mx, int _mn, LL _s1, LL _s2): mx(_mx), mn(_mn), s1(_s1), s2(_s2) { }

    Data operator + (const Data& rhs) const {
        if (mx == -MAXN && mn == MAXN) return rhs;
        if (rhs.mx == -MAXN && rhs.mn == MAXN) return *this;
        return Data(rhs.mx, mn, s1 + rhs.s1 + 1LL * rhs.mn * (rhs.mn - mx),
                s2 + rhs.s2 + (rhs.mn - mx));
    }
};

namespace SGT {
    struct Node {
        int lc, rc; Data d;
        Node() { lc = rc = 0; d = Data(); }
    } dat[MAXM << 5];
    int nidx;

    inline void maintain(int nd) {
        const int &lc = dat[nd].lc, &rc = dat[nd].rc;
        dat[nd].d = dat[lc].d + dat[rc].d;
    }

    void Mdy(int nd, int L, int R, const int& pos) {
        if (L == R) return void( dat[nd].d.mn = dat[nd].d.mx = pos );
        int Mid = (L + R) / 2;
        if (pos <= Mid) {
            if (!dat[nd].lc) dat[nd].lc = ++nidx;
            Mdy(dat[nd].lc, L, Mid, pos);
        } else {
            if (!dat[nd].rc) dat[nd].rc = ++nidx;
            Mdy(dat[nd].rc, Mid+1, R, pos);
        }
        maintain(nd);
    }

    int Mrg(int x, int y) {
        if (!x || !y) return x + y;
        int nd = ++nidx;
        dat[nd].lc = Mrg(dat[x].lc, dat[y].lc);
        dat[nd].rc = Mrg(dat[x].rc, dat[y].rc);
        return maintain(nd), nd;
    }

    Data Qry(int nd, int L, int R, const int& opL, const int& opR) {
        if (!nd) return Data();
        if (opL <= L && R <= opR) return dat[nd].d;
        int Mid = (L + R) / 2;
        if (opR <= Mid) return Qry(dat[nd].lc, L, Mid, opL, opR);
        if (opL > Mid) return Qry(dat[nd].rc, Mid+1, R, opL, opR);
        return Qry(dat[nd].lc, L, Mid, opL, opR) + Qry(dat[nd].rc, Mid+1, R, opL, opR);
    }

    LL Qry(int nd, int lgt) {
        int r1 = dat[nd].d.mn, ln = dat[nd].d.mx - lgt + 1;
        Data d = Qry(nd, 1, n, 1, ln);
        LL ret = 0;
        // Case 1
        if (d.mx - lgt + 1 >= r1) return 0;
        // Case 2
        if (r1 > ln) {
            ret += dat[nd].d.s1 - 1LL * ln * dat[nd].d.s2;
            ret += 1LL * (r1 - ln) * (n - lgt) + C2(r1 - ln);
            return ret;
        }
        // Case 3
        if (ln < r1 + lgt - 1) {
            Data p = Data(d.mx, 0, 0, 0) + Qry(nd, 1, n, ln + 1, r1 + lgt - 1);
            ret += p.s1 - 1LL * ln * p.s2;
        }
        int ri = Qry(nd, 1, n, 1, r1 + lgt - 1).mx, ri1 = Qry(nd, 1, n, r1 + lgt, n).mn;
        if (ri != -MAXN && ri1 != MAXN) ret += max(0LL, 1LL * (r1 - (ri-lgt+1)) * (ri1 - ln));
        return ret;
    }
}

namespace SAM {
    int ch[MAXM][10], len[MAXM], lnk[MAXM], nidx, last;
    int cnt[MAXM], idx[MAXM];

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

    inline void insert(int val, int i) {
        int nd = ++nidx, p = last;
        len[nd] = len[last] + 1, SGT::Mdy(rt[nd] = ++SGT::nidx, 1, n, i);
        while (p && !ch[p][val]) ch[p][val] = nd, p = lnk[p];
        if (!p) lnk[nd] = 1;
        else {
            int q = ch[p][val];
            if (len[q] == len[p] + 1) lnk[nd] = q;
            else {
                int nxt = ++nidx;
                len[nxt] = len[p] + 1, lnk[nxt] = lnk[q];
                memcpy(ch[nxt], ch[q], sizeof ch[nxt]);
                while (p && ch[p][val] == q) ch[p][val] = nxt, p = lnk[p];
                lnk[nd] = lnk[q] = nxt;
            }
        }
        last = nd;
    }

    void build() {
        for (int i = 1; i <= nidx; ++i) ++cnt[len[i]];
        for (int i = 1; i <= n; ++i) cnt[i] += cnt[i-1];
        for (int i = 1; i <= nidx; ++i) idx[cnt[len[i]]--] = i;
        for (int u, i = nidx; i > 1; --i)
            u = idx[i], rt[lnk[u]] = SGT::Mrg(rt[lnk[u]], rt[u]);
        for (int i = 1; i <= nidx; ++i) pre[0][i] = lnk[i];
        for (int j = 1; j < LOG; ++j)
            for (int i = 1; i <= nidx; ++i)
                pre[j][i] = pre[j-1][pre[j-1][i]];
    }

    inline int Jump(int u, const int& lgt) {
        for (int j = LOG-1; j >= 0; --j)
            if (pre[j][u] && len[pre[j][u]] >= lgt) u = pre[j][u];
        return u;
    }

    LL Qry(const int& L, const int& R) {
        int u = Jump(pos[R], R - L + 1);
        return SGT::Qry(rt[u], R - L + 1);
    }
}

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

DepletedPrism's Blog

九省联考 2018 大赏

「九省联考 2018」一双木棋

题目链接

解题思路

代码实现

「九省联考 2018」IIIDX

题目链接

解题思路

代码实现

「九省联考 2018」秘密袭击

题目链接

解题思路

代码实现

「九省联考 2018」劈配

题目链接

解题思路

代码实现

「九省联考 2018」林克卡特树

题目链接

解题思路

代码实现

「九省联考 2018」制胡窜

题目链接

解题思路

代码实现