讨论详情 - Hydro

fhq_treap LV 5 @ 2022-3-15 11:18:23

#017 2022.3.15

[APIO2016] 烟火表演

标签：动态规划，可合并堆，凸包。

题意

给定一颗树，称其的叶子节点为关键点 $w_{1....m}$ . 同时给定树上每条边边权，你可以调整一条边的边权由 $x \to y$ ,其中需要花费 $|x - y|$ 的代价。你的目标是满足下列条件： $\forall (w_i,w_j),dis(w_i,LCA(w_i,w_j)) = dis(w_j,LCA(w_i,w_j))$

题解

分析

先考虑基础的做法。

设 $f_{i,j}$ 表示 $i$ 的子树内所有叶子到 $i$ 的距离为 $j$ 的最小代价。

不妨将此 $dp$ 看作一个函数，可知其为一个下凸函数。

我们再来思考一下如何把 $f_{i,...}$ 这个函数转成给父亲的贡献 (因为要考虑 $(i,fa_i)$ 这条边的权)，我们设其为 $g_{i,...}$ .

那可知 $f_{u,...} = \sum g_{v,...}$

那我们只要考虑如何求出 $g_{v,...}$

考虑 $f_{i,...}$ 为一个下凸壳，我们考虑记 $[L,R]$ 为 $\min f_{i,...}$ 对应的下标。

那么有

$l = val(i,fa_i)$

$g_{i,x}= \left\{ \begin{array}{rcl} f_{i,x} + l & & {x\leq L}\\ f_{i,L} + (l - (x - L)) & & {L<x\leq L + l}\\ f_{i,L} & & {L + l < x\leq R + l}\\ r_{i,L} + ((x - R) - L) & & {R + l < x} \end{array} \right. $

我们思考这四种操作的本质。

我们将 $\leq L$ 的部分向上平移了 $l$ 个单位，将 $[L,R]$ 的部分向右平移了 $l$ 单位，插入了一条 $[L,L + r]$ 上斜率为 $-1$ 的直线，将 $> R + l$ 的部分改为 $1$ .

考虑各个转折点的位置间的斜率每次递增 $1$ (假如有一个斜率不存在，我们将这个转折点复制一个，表示不存在的斜率)，我们只存下转折点。

那么我们合并时只要把转折点移动，并合并儿子即可。

最后计算答案时，显然 $f_{1,0} = \sum l_i$ ,那么可以遍历转折点找到最低段就能算出答案了。

代码

//晦暗的宇宙，我们找不到光，看不见尽头，但我们永远都不会被黑色打倒。——Quinn葵因
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, ans, tot;
int a[600010], f[600010], L[600010], deg[600010], rt[600010], l[600010], r[600010], dis[600010];
int read() {
    int r = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c <= '9' && c >= '0')
        r = (r << 1) + (r << 3) + c - '0', c = getchar();

    return r * f;
}
void put(int x) {
    if (x < 0) {
        putchar('-');
        x = ~x + 1;
    }

    if (x > 9)
        put(x / 10);

    putchar(x % 10 + '0');
}
int merge(int x, int y) {
    if (!x || !y)
        return x + y;

    if (a[x] < a[y])
        swap(x, y);

    r[x] = merge(r[x], y);

    if (dis[l[x]] < dis[r[x]])
        swap(l[x], r[x]);

    dis[x] = dis[r[x]] + 1;
    return x;
}
int pop(int x) {
    return merge(l[x], r[x]);
}
signed main() {
    n = read(), m = read();

    for (int i = 2; i <= n + m; i++)
        f[i] = read(), L[i] = read(), deg[f[i]]++, ans += L[i];

    for (int i = n + m; i > 1; i--) {
        int l = 0, r = 0;

        if (i <= n) {
            deg[i]--;

            while (deg[i])
                deg[i]--, rt[i] = pop(rt[i]);

            r = a[rt[i]], rt[i] = pop(rt[i]);
            l = a[rt[i]], rt[i] = pop(rt[i]);
        }

        a[++tot] = l + L[i], a[++tot] = r + L[i];
        rt[i] = merge(rt[i], merge(tot - 1, tot));
        rt[f[i]] = merge(rt[f[i]], rt[i]);
    }

    while (deg[1])
        deg[1]--, rt[1] = pop(rt[1]);

    while (rt[1])
        ans -= a[rt[1]], rt[1] = pop(rt[1]);

    put(ans);
    puts("");
    return 0;
}

👍 2

❤️ 1

fhq_treap LV 5 @ 2022-3-12 8:00:50

#016 2022.3.12

[CTSC2018]暴力写挂

标签：点分治，虚树，动态规划。

题意

给定两颗以 $1$ 为根的树 $A,B$ ，其树边带权。定义点对 $(i,j)$ 的权值为两点到 $1$ 的距离减去两点在 $A,B$ 两树上的 $LCA$ 到对应树根 $1$ 的距离，求出最大的点对的权值。使用形式化的语言即求 $\max dep_A(i) + dep_A(j) - dep_A(LCA_A(i,j)) - dep_B(LCA_B(i,j))\\dep_A(i) = dis_A(1,i),dep_B(i) = dis_B(1,i)$。

$n \leq 366666,|v| \leq 2017011328$

题解

分析

考虑这种形式我们较难处理，我们一个自然的想法是把信息压缩下来，我们不妨把 $dep_A(i),dep_A (j),dep_A(LCA_A(i,j))$ 压缩成一种信息即 $dis_A(i,j)$ 。

那么有改写形式为 $\frac{1}{2}\max dis_A(i,j) + dep_A(i) + dep_A(j) - 2*dep_B(LCA_B(i,j))$,我们发现这样更改的一个显著进步即我们把从原本的两个非线性关系 $(dep_A(LCA_A(i,j)),dep_B(LCA_B(i,j)))$ 变成了只剩后者，考虑 $dep_A(i),dep_A(j)$ 可类比于常数，那我们要做的实际上是在限定 $dis(i,j)$ 的同时,在 $B$ 这颗树上做一类点对统计问题。考虑限制 $dis(i,j)$ 的一个经典的方法，我们使用点分治，那么我们发现 $dis(i,j)$ 同样可以拆贡献到点，设我们当前的分治中心为 $mid$ ,那么把 $dis(i,j) = dis(i,mid) + dis(mid,j)$ 就能把这个权值分配到点上，那么我们此时要做的任务即在 $B$ 上枚举 $LCA$ ，在其不同子树里找到 $val(i) + val(j)$ 的最大值即能用 $val(i) + val(j) - 2 * dep_B(LCA),val(x) = dep_A(x) + dis(x,mid)$ 更新答案。

但是我们还有一些限制：

一：首先，我们选择的 $B$ 子树里的 $i,j$ 必须在 $mid$ 分属两侧，即其要跨越 $mid$ ,我们把 $mid$ 的每一个子树内的点染上不同颜色即可，在 $B$ 中上进行树上动态规划，维护其子树内的权值最大点与 和最大权值对应点的颜色不一样的权值次大点，在儿子更新父亲的这两点时更新答案。

二：我们显然不能每次分治都进行一个满的 $O(n)$ 的树上动态规划，否则时间复杂度将退化为 $O(n^2)$ ,但我们发现，我们称点分治时 $mid$ 管理的点为关键点，我们可以在 $B$ 上构建这些关键点对应的虚树，那么直接对虚树进行 $dp$ 即可，由于虚树大小和关键点点集大小线性相关，所以保证了复杂度。

代码

//晦暗的宇宙，我们找不到光，看不见尽头，但我们永远都不会被黑色打倒。——Quinn葵因
#include <bits/stdc++.h>
#define ll long long
#define N 1000000
using std::vector;
using std::pair;

int n;

#define pil pair<int,ll>
#define mp std::make_pair

vector<pil>A[N], B[N]; //tree

ll depa[N], depb[N];
int dep[N];

inline void dfsa(int u, int fa) {
    for (auto it : A[u]) {
        int x = it.first;
        ll v = it.second;
        if (x == fa)
            continue;
        depa[x] = depa[u] + v;
        dfsa(x, u);
    }
}

int F[N][20];

int dfn[N];
int cnt;

inline void dfsb(int u, int fa) {
    F[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 1; i <= 19; ++i)
        F[u][i] = F[F[u][i - 1]][i - 1];
    dfn[u] = ++cnt;
    for (auto it : B[u]) {
        int x = it.first;
        ll v = it.second;
        if (x == fa)
            continue;
        depb[x] = depb[u] + v;
        dfsb(x, u);
    }
}

int sum, siz[N], root;
int maxn[N];

ll val[N];
int c[N];
int vis[N];

inline void find(int u, int fa) {
    siz[u] = 1;
    maxn[u] = 1;
    for (auto it : A[u]) {
        int v = it.first;
        if (v == fa || vis[v])
            continue;
        find(v, u);
        siz[u] += siz[v];
        maxn[u] = std::max(maxn[u], siz[v]);
    }
    maxn[u] = std::max(maxn[u], sum - siz[u]);
    if (maxn[u] < maxn[root])
        root = u;
}

vector<int>P;

inline void dis(int u, int fa) {
    c[u] = c[fa];
    for (auto it : A[u]) {
        int v = it.first;
        ll vi = it.second;
        if (vis[v] || v == fa)
            continue;
        val[v] = val[u] + vi;
        dis(v, u);
    }
    val[u] = val[u] + depa[u];
    P.push_back(u);
}

inline int lca(int x, int y) {
    if (dep[x] < dep[y])
        std::swap(x, y);
    for (int i = 19; i >= 0; --i) {
        if (dep[F[x][i]] >= dep[y])
            x = F[x][i];
    }
    if (x == y)
        return x;
    for (int i = 19; i >= 0; --i) {
        if (F[x][i] != F[y][i])
            x = F[x][i], y = F[y][i];
    }

    return F[x][0];
}

inline bool cmp(int x, int y) {
    return dfn[x] < dfn[y];
}

ll f[N][2];

bool key[N];

int Fi[N];

ll ans = -1e18;

#define pii pair<ll,int>

vector<pii>M;

inline void merge(int x, int y) { //y -> x
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            if (c[f[x][i]] != c[f[y][j]])
                ans = std::max(ans, val[f[x][i]] + val[f[y][j]] - 2 * depb[x]);
    M.clear();
    M.push_back(mp(-val[f[x][0]], f[x][0]));
    M.push_back(mp(-val[f[x][1]], f[x][1]));
    M.push_back(mp(-val[f[y][0]], f[y][0]));
    M.push_back(mp(-val[f[y][1]], f[y][1]));
    std::sort(M.begin(), M.end());
    f[x][0] = M[0].second;

    for (int i = 1; i <= 3; ++i) {
        if (c[M[i].second] != c[f[x][0]]) {
            f[x][1] = M[i].second;
            return ;
        }
    }
}

inline int iread(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline ll lread(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline void build() {
    val[0] = -1e18;
    c[0] = -1;
    std::sort(P.begin(), P.end(), cmp);
    for (int i = 0; i < P.size(); ++i)
        key[P[i]] = 1;
    int k = P.size();
    for (int i = 1; i < k; ++i)
        P.push_back(lca(P[i], P[i - 1]));
    std::sort(P.begin(), P.end(), cmp);
    P.erase(unique(P.begin(), P.end()), P.end());
    for (int i = 1; i < P.size(); ++i)
        Fi[P[i]] = lca(P[i], P[i - 1]);
    for (int i = 0; i < P.size(); ++i) {
        if (!key[P[i]])
            f[P[i]][0] = f[P[i]][1] = 0;
        else
            f[P[i]][0] = P[i], f[P[i]][1] = 0;
    }
    for (int i = P.size() - 1; i >= 1; --i) {
        int u = P[i];
        merge(Fi[u], u);
    }
    for (int i = 0; i < P.size(); ++i)
        key[P[i]] = 0;
}

inline void solve(int u) {
    vis[u] = 1;
    find(u, 0);
    val[u] = depa[u];
    c[u] = u;
    P.clear();
    P.push_back(u);
    for (auto it : A[u]) {
        int v = it.first;
        ll vi = it.second;
        if (vis[v])
            continue;
        val[v] = vi;
        c[v] = v;
        dis(v, v);
    }
    build();
    for (auto it : A[u]) {
        int v = it.first;
        sum = siz[v], root = 0;
        if (vis[v])
            continue;
        find(v, 0);
        solve(root);
    }
}

signed main() {
    //  freopen("q.in","r",stdin);
    //  freopen("q.out","w",stdout);
//    scanf("%d", &n);
	n = iread();
    for (int i = 1; i < n; ++i) {
        int x = iread(), y = iread();
        ll v = lread();
        A[x].push_back(mp(y, v));
        A[y].push_back(mp(x, v));
    }

    for (int i = 1; i < n; ++i) {
        int x = iread(), y = iread();
        ll v = lread();
        B[x].push_back(mp(y, v));
        B[y].push_back(mp(x, v));
    }

    dfsa(1, 0);
    dfsb(1, 0);
    maxn[0] = n * 2;
    root = 0;
    sum = n;
    find(1, 0);
    solve(root);
    ans = ans / 2;

    for (int i = 1; i <= n; ++i)
        ans = std::max(ans, 2ll * depa[i] - depa[i] - depb[i]);

    std::cout << ans << "\n";
}

/*
6
1 2 2
1 3 0
2 4 1
2 5 -7
3 6 0
1 2 -1
2 3 -1
2 5 3
2 6 -2
3 4 8
*/

👍 4

Macesuted QWQ LV 10 SU @ 2022-3-4 7:16:04

#015 2022.3.4

CF1500F Cupboards Jumps

标签：动态规划，构造。

题意

给出长度为 $n - 2$ 的数组 $w_i$ ，请你构造一个长度为 $n$ 的数组 $a$ 满足 $\forall i \in [1,~n - 2],~\max(a_i,~a_{i + 1},~a_{i + 2}) - \min(a_i,~a_{i + 1},~a_{i + 2}) = w_i$。若不能构造输出 NO。

$n \le 10^6,~0 \le w_i \le 10^{12},~0 \le a_i \le 10^{18}$

题解

分析

考虑令 $c_i = a_{i + 1} - a_i$ ，则 $w_i = \max(|c_i|,~|c_{i + 1}|,~|c_i + c_{i + 1}|)$ 。

在确定 $c_i$ 考虑 $w_i$ 对 $c_{i + 1}$ 的限制时我们发现，我们可以通过将 $a_1 \sim a_{i + 1}$ 全部乘上 $-1$ 以使得 $c_1 \sim c_i$ 全都乘上 $-1$ ，容易发现这并不会影响 $w_1 \sim w_{i - 1}$ 带来的所有限制。因此我们发现我们在研究该限制时并不关心 $c_i$ 的符号，我们令 $d_i = |c_i|$ ，则 $w_i = \max(d_i,~d_{i + 1},~d_i + d_{i + 1})$ 。

考虑对该限制分别考虑最大值在哪一项上取到。设状态 $f_{i,~j}$ 表示考虑了 $d_1 \sim d_i$ ，且 $d_i = j$ 的方案是否合法。则对于所有合法情况 $f_{i,~j}$ ，有：

若 $j = w_i$ ，则 $\forall k \in [0,~w_i],~f_{i + 1,~k} = \text{True}$ 。
若 $0 < j \le w_i$ ，则 $f_{i + 1,~w_i} = \text{True}$ 。
若 $0 < j \le w_i$ ， $f_{i + 1,~w_i - j} = \text{True}$ 。

仔细观察，我们发现若 $f_{i,~w_i} = \text{True}$ ， $f_{i + 1}$ 数组中全部能取到的部分都为 $\text{True}$ ，不需要考虑其他两个情况；若 $f_{i}$ 数组中存在一项为 $\text{True}$ 那么 $f_{i + 1,~w_i}$ 为 $\text{True}$ 。这两种情况均可快速判断，而情况 3 则需要将所有合法状态 $j$ 转换为 $w_i - j$ 。

考虑维护 $f_i$ 数组中连续的 $\text{True}$ 段，则对于一个段 $[l,~r]$ ，其转移后为 $[w_i - r,~w_i - l]$ 。容易发现其由一个翻转操作和一个平移操作构成。因此每次从 $i$ 转移到 $i + 1$ 时，只需判断情况 1 和 2，然后再全局修改连续段的翻转和平移情况即可。若在转移到 $n - 1$ 前连续段集合为空，则无解，否则有解。

考虑如何构造 $d$ 数组。我们可以在最终的连续段集合中任取一个点的值作为 $d_{n - 1}$ ，考虑从后往前构造出整个 $d$ 数组，发现只有三种情况：

若 $d_i$ 可以等于 $w_i$ ，则令 $d_i = w_i$ 。因为若 $d_i = w_i$ ，则 $d_{i + 1}$ 可以取任意可以取到的值，所以这么做并不会影响正确性。
若 $d_{i + 1} = w_i$ ，则令 $d_i$ 为任意可以取到的小于 $w_i$ 的值。
若不满足上面的两个条件，则令 $d_i = w_i - d_{i + 1}$ 。

需要注意的是这里需要用到“任意可以取到的小于 $w_i$ 的值”，这需要实现中在转移 $f$ 时提前记录该项和 $d_i$ 能否取到 $w_i$ 值。

构造完 $d$ 数组后，考虑如何构造 $c$ 。这则相对简单，判断 $d_i + d_{i + 1}$ 是否等于 $w_i$ 。若不等于，则 $c_i$ 与 $c_{i + 1}$ 需异号，否则需同号。

最后根据 $c$ 数组随意构造出满足每个元素均为非负整数的 $a$ 数组即可。

代码

View On GitHub

/**
 * @file 1500F.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-03-03
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf1500f
 *
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 1000005

typedef pair<long long, long long> pll;

long long a[maxn], d[maxn], w[maxn], v[maxn], limd[maxn];
set<pll> S;

void solve(void) {
    int n = read<int>();
    long long C = read<long long>();
    for (int i = 1; i < n; i++) limd[i] = numeric_limits<long long>::max();
    for (int i = 1; i <= n - 2; i++)
        w[i] = read<long long>(), limd[i] = min(limd[i], w[i]), limd[i + 1] = min(limd[i + 1], w[i]);
    S.emplace(0, limd[1]);
    long long A = +1, B = 0;
    for (int i = 1; i <= n - 1; i++) {
        if (A == +1) {
            while (!S.empty() && S.rbegin()->first + B > limd[i]) S.erase(--S.end());
            if (!S.empty() && S.rbegin()->second + B > limd[i]) {
                int l = S.rbegin()->first;
                S.erase(--S.end()), S.emplace(l, limd[i] - B);
            }
        } else {
            while (!S.empty() && -S.begin()->second + B > limd[i]) S.erase(S.begin());
            if (!S.empty() && -S.begin()->second + B > limd[i]) {
                int r = S.begin()->second;
                S.erase(S.begin()), S.emplace(B - limd[i], r);
            }
        }
        long long tw = (w[i] - B) / A;
        auto p = S.lower_bound({tw + 1, tw + 1});
        if (p != S.begin() && (--p)->second >= tw) {
            v[i] = w[i];
            S.clear(), S.emplace(0, limd[i + 1]), A = +1, B = 0;
            continue;
        }
        if (S.empty()) return putstr("NO\n");
        v[i] = S.begin()->first * A + B;
        if (i == n - 1) break;
        A = -A, B = w[i] - B;
        tw = (w[i] - B) / A;
        p = S.lower_bound({tw + 1, tw + 1});
        if (p == S.begin() || (--p)->second < tw) S.emplace(tw, tw);
    }
    d[n - 1] = v[n - 1];
    putstr("YES\n");
    for (int i = n - 2; i; i--)
        if (v[i] == w[i])
            d[i] = w[i];
        else if (d[i + 1] == w[i])
            d[i] = v[i];
        else
            d[i] = abs(w[i] - d[i + 1]);
    long long minVal = 0, pre = 0;
    for (int i = 2, id = +1; i <= n - 1; i++) {
        if (abs(d[i - 1]) + abs(d[i]) != w[i - 1]) id = -id;
        d[i] *= id;
        minVal = min(minVal, pre += d[i]);
    }
    a[1] = -minVal;
    for (int i = 2; i <= n; i++) a[i] = a[i - 1] + d[i - 1];
    for (int i = 1; i <= n; i++) write(a[i]), putch(" \n"[i == n]);
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

👍 8

Macesuted QWQ LV 10 SU @ 2022-2-24 21:23:17

#014 2022.2.24

CF1307G Cow and Exercise

标签：线性规划，网络流。

题意

给出一个 $n$ 个点 $m$ 条边的有向有边权图。你可以对任意一条边执行操作使得该边边权加一。有 $q$ 个询问，每个询问给出一个 $x$ ，求在操作次数不超过 $x$ 的情况下 $1$ 到 $n$ 最短路的最大值。

$n \le 50,~m \le n \times (n-1),~w_i \le 10^6,~q \le 10^5,~x \le 10^5$

题解

分析

先按照最短路定义以及题目要求列出不等式：

$$\text{maximize}~d_n - d_1 \\ \begin{cases} d_j - d_i - a_{i,~j} \le w_{i,~j} \\ \sum a_{i,~j} \le x \\ d_i,~a_{i,~j} \ge 0 \end{cases} $$

以 $n = 3$ 为例可以画出下面的线性规划矩阵：

$$\begin{array}{ccccccccccc} d_1 & d_2 & d_3 & a_{1,~2} & a_{1,~3} & a_{2,~1} & a_{2,~3} & a_{3,~1} & a_{3,~2} & & \\ \hline -1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \le & w_{1,~2} \\ -1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & \le & w_{1,~3} \\ +1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & \le & w_{2,~1} \\ 0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & \le & w_{2,~3} \\ +1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & \le & w_{3,~1} \\ 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & \le & w_{3,~2} \\ 0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & \le & x \\ -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & \ge & Ans \\ \end{array} $$

我们纵向看该矩阵求出其对偶线性规划：

$$\begin{array}{c|cccccccccc} p_{1,~2} & -1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & w_{1,~2} \\ p_{1,~3} & -1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & w_{1,~3} \\ p_{2,~1} & +1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & w_{2,~1} \\ p_{2,~3} & 0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & w_{2,~3} \\ p_{3,~1} & +1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & w_{3,~1} \\ p_{3,~2} & 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & w_{3,~2} \\ q & 0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & x \\ & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \le \\ & -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & Ans \\ \end{array} $$

即：

$$\text{minimize}~ \bigg( \sum w_{i,~j} \times p_{i,~j} \bigg) + x \times q \\ \begin{cases} \sum_j p_{j,~i} - \sum_j p_{i,~j} \ge \begin{cases} -1,& i=1 \\ 0,& 1 < i < n \\ +1,& i=n \\ \end{cases}\\ -p_{i,~j} + q \ge 0 \\ p_{i,~j},~q \ge 0 \end{cases} $$

发现其形式非常类似于最小费用最大流：令 $p_{i,~j}$ 为边 $i \to j$ 流量，第一条不等式限制除 $1$ 和 $n$ 以外的其他所有结点入流量不超过出流量，且 $1$ 号点出流量比入流量大 $1$ ， $n$ 号点入流量比出流量大 $1$ ；第二条不等式限制每条边流量均不超过上限 $q$ ；令 $w_{i,~j}$ 为边 $i \to j$ 的费用，则最终答案即为网络总费用加上 $x \times q$ 。

为方便处理，我们将对偶线性规划矩阵最后一行乘上 $flow$ ，倒数第二行除以 $q$ ，网络流限制变为：源点 $1$ 到汇点 $n$ 的流量为 $flow$ ，每条边的最大流量为 $1$ ，每条边的费用为 $w_{i,~j}$ 。令网络在流量为 $flow$ 时最小费用为 $cost$ ，则答案即为 $\dfrac {cost + x} {flow}$ 。

做最小费用最大流过程中维护每一个流量对应的费用即可，利用其凸性可以预处理并快速解决询问。总时间复杂度 $O(n \times m^2 + q \times \log m)$ 。

代码

View On GitHub

/**
 * @file 1307G.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-02-24
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf1307g
 *
 */

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 55
#define maxm 2505

typedef pair<long long, int> pli;

class Dinic {
   private:
    struct Edge {
        int to, cap, cost, rev;
    };

    vector<vector<Edge>> graph;
    vector<long long> dist;
    vector<int> pre;
    vector<bool> vis;
    queue<int> que;
    int n;

   public:
    void resize(int _n) { return n = _n, graph.resize(n + 1), vis.resize(n + 1), dist.resize(n + 1), pre.resize(n + 1); }
    void addEdge(int from, int to, int cap, int cost) {
        return graph[from].push_back(Edge{to, cap, cost, (int)graph[to].size()}),
               graph[to].push_back(Edge{from, 0, -cost, (int)graph[from].size() - 1});
    }
    long long maxFlow(int S, int T) {
        for (int i = 1; i <= n; i++) dist[i] = numeric_limits<int>::max(), vis[i] = false;
        que.push(S), dist[S] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            vis[p] = false;
            for (auto i : graph[p])
                if (i.cap && dist[i.to] > dist[p] + i.cost) {
                    dist[i.to] = dist[p] + i.cost, pre[i.to] = i.rev;
                    if (!vis[i.to]) vis[i.to] = true, que.push(i.to);
                }
        }
        if (dist[T] == numeric_limits<int>::max()) return 0;
        int p = T;
        while (p != S) {
            int x = graph[p][pre[p]].to;
            graph[x][graph[p][pre[p]].rev].cap--, graph[p][pre[p]].cap++;
            p = x;
        }
        return dist[T];
    }
} net;

long long cost[maxm], lim[maxm];

void solve(void) {
    int n = read<int>(), m = read<int>();
    net.resize(n);
    for (int i = 1, x, y, c; i <= m; i++) {
        x = read<int>(), y = read<int>(), c = read<int>();
        net.addEdge(x, y, 1, c);
    }
    int flow = 0;
    long long ret = net.maxFlow(1, n);
    while (ret) cost[flow + 1] = cost[flow] + ret, flow++, ret = net.maxFlow(1, n);
    for (int i = 1; i < flow; i++) lim[i] = cost[i + 1] * i - cost[i] * (i + 1);
    cout << setprecision(8);
    int q = read<int>();
    while (q--) {
        int x = read<int>(), p = lower_bound(lim + 1, lim + flow, x) - lim;
        cout << 1. * (cost[p] + x) / p << endl;
    }
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

👍 11

❤️ 7

🕊️ 4

Macesuted QWQ LV 10 SU @ 2022-2-23 7:31:29

#013 2022.2.23

标签：思维。

题目大意

给出一个 $n$ 个点的 DAG，满足 $1,~2,~3,~\dots,~n$ 为它的一个拓扑序。问有多少对满足条件的二元组 $(x,~y)$ 满足 $x < y$ 且在原图上加入一条 $y \to x$ 的有向边后原图存在哈密顿路径。

$n,~m \le 1.5 \times 10^5$

题解

分析

若原图本身存在哈密顿路径，则答案即为 $n \choose 2$ 。

否则我们可以从原图上找出两条链，满足每个点均在其中一条链上，将这两条链首尾相连即可得到哈密顿路径。令最终我们加入的边为 $y \to x$ ，则哈密顿路径应形如：

$1 \to 2 \to 3 \to \cdots \to (x - 1)$
$(x - 1) \to \cdots \to y$
$y \to x$
$x \to \cdots \to (y + 1)$
$(y + 1) \to (y + 2) \to \cdots \to n$

其中 2、4 两部分包括 $(x-1) \sim (y + 1)$ 之间的所有结点，且 $(x - 1)$ 与 $y$ 在同一条链上， $x$ 与 $(y + 1)$ 在另一条链上。若采用状态 $(x,~y)$ 表示 $x$ 与 $1$ 在同一条链上， $y$ 与 $n$ 在另一条链上，当 $(x-1,~x)$ 和 $(y,~y+1)$ 状态在同一方案中同时存在时连接 $y \to x$ 为一种合法方案。

将所有结点 $a$ 与结点 $(a + 1)$ 所在链不同的情况拿出，令 $S_x = (x,~x + 1),~T_x = (x + 1,~x)$ 。将这 $O(n)$ 个状态看为结点，在同时出现于同一方案中的相邻状态对应的结点间连边。不难发现相邻两状态的关系一定形如这样：

即在 $(x + 1)$ 可向右以步长 $1$ 走到 $y$ 且存在边 $x \to (y + 1)$ 时 $S_x = T_y$ 。通过此方法可以在这 $O(n)$ 个状态间连上 $O(m)$ 条边。最终答案即为：满足下面条件的数对 $(x,~y)$ 数量：

可从 $1$ 号点以步长 $1$ 走到 $x$ 。
可从 $(y + 1)$ 以步长 $1$ 走到 $n$ 。
$S_x = S_y$

官方题解给出了一种巧妙地方法计算这样的数对的数量：由于原图中不存在哈密顿路径，所以必然存在至少一个点 $p$ 满足不存在边 $p \to (p + 1)$ 。不难发现对于每一对相连的 $S_x,~S_y$ ，它们两点之间的路径上必然存在 $S_p$ 或 $T_p$ 。因此建完图后从 $S_p$ 和 $T_p$ 开始分别向左和向右遍历连通块，将左侧连通块内满足条件 1 的结点数量与右侧连通块内满足条件 2 的结点相乘即可。由于可能存在 $S_x$ 与 $S_y$ 同时在 $S_p$ 和 $T_p$ 两侧的连通块中的情况，因此最终需容斥减去算重的部分。

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

代码

View on GitHub

/**
 * @file 1616G.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-02-22
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 150005

bool cons[maxn], vis[2][maxn * 2];

vector<vector<int>> graph, g, gr;

void dfs(int p, vector<vector<int>>& graph, int id) {
    vis[id][p] = true;
    for (auto i : graph[p])
        if (!vis[id][i]) dfs(i, graph, id);
    return;
}

void solve(void) {
    int n = read<int>() + 2, m = read<int>();
    graph.clear(), g.clear(), gr.clear(), graph.resize(n + 1), g.resize(2 * n + 1), gr.resize(2 * n + 1);
    for (int i = 1; i <= n; i++) cons[i] = false, vis[0][i] = vis[1][i] = vis[0][n + i] = vis[1][n + i] = false;
    for (int i = 3; i < n; i++) graph[1].push_back(i), graph[i - 1].push_back(n);
    cons[1] = cons[n - 1] = true;
    for (int i = 1; i <= m; i++) {
        int x = read<int>() + 1, y = read<int>() + 1;
        if (x + 1 == y)
            cons[x] = true;
        else
            graph[x].push_back(y);
    }
    int p = 0, l = 0, r = 0;
    for (int i = 1; i < n; i++)
        if (!cons[i]) {
            if (!p) p = l = i;
            r = i;
        }
    if (p == 0) return write(1LL * (n - 2) * (n - 3) / 2), putch('\n');
    for (int i = n, r = n; i > 1; i--) {
        if (!cons[i]) r = i;
        for (auto j : graph[i - 1])
            if (j <= r + 1)
                g[i - 1].push_back(n + j), g[n + i].push_back(j - 1), gr[n + j].push_back(i - 1), gr[j - 1].push_back(n + i);
    }
    dfs(p, g, 0), dfs(p, gr, 0), dfs(n + p + 1, g, 1), dfs(n + p + 1, gr, 1);
    long long ans = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= l; i++) cnt1 += vis[0][i];
    for (int i = r; i < n; i++) cnt2 += vis[0][i];
    ans += cnt1 * cnt2, cnt1 = cnt2 = 0;
    for (int i = 1; i <= l; i++) cnt1 += vis[1][i];
    for (int i = r; i < n; i++) cnt2 += vis[1][i];
    ans += cnt1 * cnt2, cnt1 = cnt2 = 0;
    for (int i = 1; i <= l; i++) cnt1 += (vis[0][i] & vis[1][i]);
    for (int i = r; i < n; i++) cnt2 += (vis[0][i] & vis[1][i]);
    ans -= cnt1 * cnt2;
    return write(ans - (l == r)), putch('\n');
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = read<int>();
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

👍 6

寒鸽儿 LV 10 MOD @ 2022-2-22 18:08:03

#012 2022.2.22

CF938G Shortest Path Queries

题目大意

给一张 $n$ 点 $m$ 条边的图，动态加边删边，询问给出两点求异或最短路（非简单路）。
保证过程中任意时刻不存在重边自环。

$1 \leq n, q \leq 2 \times 10^5, 1 \leq w < 2^{30}$ ， $w$ 代表边权。

题解

1. 静态 xor 最短路

先考虑对全局静态的图询问 xor 最短路怎么做。

一条非简单路径，我们考虑它由若干个圈加链构成（由 xor 的性质，用到圈只算一圈)。

由 xor 性质，我们发现很多链的部分被抵消了，无论图的形态如何，最终留下的是一条直达的链（简单路径）和圈。

易知原图中的所有圈都可以计入贡献，由于连通，从链条走一条简单路到圈再原路返回即可。

简单路径的选取方式看起来很抽象，实际上只需要随便选一条：如果存在更佳的选择，一定与原先选的构成一个环，这个环会被计入贡献。

结论：用线性基维护所有环的值，求任意简单路与之的异或 $\min$ 即可。

2. 考虑动态加边删边做这个东西：

一条边仅作用于一段连续的时间，对时间线段树分治，变成：加边撤回维护环的贡献。

求环可以用并查集来实现，支持加边，不带路径压缩支持撤回的，加边复杂度 $\mathcal{O}(\log n)$ ，撤回 $\mathcal{O}(1)$ 。

线性基插入和复制的代价是 $\mathcal{O}(\log w)$ 的。回撤直接用之前复制出来的信息复制进去即可。

这样就能维护线段树分治过程中所需的信息。

复杂度 $\mathcal{O}((n + q) \log (n + q) (\log n + \log w))$ 。

code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;

const int maxn = 2e5 + 10;

struct xorBase {
	#define dig 30
	int p[dig + 1];
	bool zero;
	xorBase() { memset(p, 0, sizeof(p)); zero = false; }
	void insert(int x) {
		for(int i = dig; ~i; -- i)
			if(x & (1 << i)) {
				if(p[i]) x ^= p[i];
				else { p[i] = x; return ; }
			}
		zero = true;
	}
	int totmin(int ans = 0) {
		for(int i = dig; ~i; -- i)
			if((ans & (1 << i)) && p[i]) ans ^= p[i];
		return ans;
	}
} xb;

inline void copy(xorBase &lhs, xorBase &rhs) {
	lhs.zero = rhs.zero;
	memcpy(lhs.p, rhs.p, sizeof(lhs));
}

struct DSU {
	vector<int> fa, dis, rank;
	vector< pair<int, bool> > hist;
	void init(int n) {
		fa.resize(n + 1, 0); rep(i,1,n) fa[i] = i;
		dis.resize(n + 1, 0); rep(i,1,n) dis[i] = 0;
		rank.resize(n + 1, 0); rep(i,1,n) rank[i] = 1;
	}
	int find(int x, int &disCnt) {
		if(x == fa[x]) return x;
		int ret = find(fa[x], disCnt);
		disCnt ^= dis[x];
		return ret;
	}
	bool link(int x, int y, int w) {
		int dx = 0, dy = 0;
		x = find(x, dx);
		y = find(y, dy);
		if(x == y) return false;
		if(rank[x] < rank[y]) swap(x, y), swap(dx, dy);
		pair<int, bool> h = {y, 0};
		if(rank[x] == rank[y]) ++ rank[x], h.second = true;
		fa[y] = x, dis[y] = w ^ dx ^ dy;
		hist.push_back(h);
		return true;
	}
	void undo() {
		auto &it = hist.back();
		if(it.second) -- rank[fa[it.first]];
		fa[it.first] = it.first;
		dis[it.first] = 0;
		hist.pop_back();
	}
} dsu;

struct edge {
	int x, y;
	bool operator < (const edge &o) const {
		return x < o.x || x == o.x && y < o.y;
	}
};

struct ed {
	int x, y, w;
};

struct segTdiv {
	vector<ed> opr[maxn << 2];
	vector< pair<int, int> > qry[maxn];
	vector<int> ans;

	void insert(int p, int lp, int rp, int l, int r, ed e) {
		if(l <= lp && rp <= r) {
			opr[p].push_back(e);
			return ;
		}
		register int mid = (lp + rp) >> 1, ls = p << 1, rs = ls | 1;
		if(l <= mid) insert(ls, lp, mid, l, r, e);
		if(r > mid) insert(rs, mid + 1, rp, l, r, e);
	}

	void dfs(int p, int lp, int rp) {
		for(ed &e : opr[p]) {
			int w = e.w;
			if(dsu.link(e.x, e.y, w) == false) {
				dsu.find(e.x, w); dsu.find(e.y, w);
				xb.insert(w);
			}
		}
		if(lp == rp) {
			for(auto it : qry[lp]) {
				int dis = 0;
				dsu.find(it.first, dis);
				dsu.find(it.second, dis);
				ans.push_back(xb.totmin(dis));
			}
			return ;
		}
		register int mid = (lp + rp) >> 1;
		int sz = dsu.hist.size();
		xorBase tmp; copy(tmp, xb);
		dfs(p << 1, lp, mid);
		while(dsu.hist.size() > sz) dsu.undo();
		copy(xb, tmp);
		dfs(p << 1 | 1, mid + 1, rp);
	}
} tree;

map< edge, pair<int, pair<int, int> > > mp;

int main() {
	int n, m; 
	scanf("%d %d", &n, &m);
	dsu.init(n);
	int opt, x, y, w;
	int timer = 1;
	rep(i,1,m) {
		scanf("%d %d %d", &x, &y, &w);
		if(x > y) swap(x, y);
		mp[{x, y}] = {w, {1, 0}};
	}
	int q;
	scanf("%d", &q);
	rep(qr,1,q) {
		scanf("%d", &opt);
		if(opt != 3) ++ timer;
		if(opt == 1) {
			scanf("%d %d %d", &x, &y, &w);
			if(x > y) swap(x, y);
			mp[{x, y}] = {w, {timer, 0}};
		} else if(opt == 2) {
			scanf("%d %d", &x, &y);
			if(x > y) swap(x, y);
			mp[{x, y}].second.second = timer - 1;
		} else {
			scanf("%d %d", &x, &y);
			if(x > y) swap(x, y);
			tree.qry[timer].push_back({x, y});
		}
	}
	for(auto &it : mp) {
		if(it.second.second.second == 0) it.second.second.second = timer;
		tree.insert(1, 1, timer, it.second.second.first, it.second.second.second, {it.first.x, it.first.y, it.second.first});
	}
	tree.dfs(1, 1, timer);
	for(int a : tree.ans) printf("%d\n", a);
	return 0;
}

👍 4

Macesuted QWQ LV 10 SU @ 2022-2-1 21:44:06

#011 2022.2.1

标签：动态规划，概率期望。

题目大意

给出一个长度为 $n$ 的序列，你需要进行 $k$ 次操作，第 $i$ 次操作将会任意选择一个序列元素，将它的值加入到答案后将该数减去其模 $i$ 的值。求 $k$ 次操作后你的答案的期望。

$n \le 10^7,~k \le 17,~a_i < 998244353$

题解

分析

我们发现若第 $x_1,~x_2,\dots,~x_n$ 次操作均在某一值为 $v$ 的元素上进行，该元素最终值为 $v - v \bmod \mathrm{lcm} _i ~ x_i$ 。由于操作数量不超过 $17$ ，容易发现数组内的每一个元素在结束后都一定不小于 $v - v \bmod \mathrm{lcm} _{1 \le i \le 17} ~ i$ 。

我们令 $L = \mathrm{lcm}_{1 \le i \le k}~i$ 。则我们可以将每个元素 $v$ 分为两部分，第一部分为 $v - v \bmod L$ ，第二部分为 $v \% L$ 。考虑对这两部分分开进行计算。

第一部分由于在经过任意操作后该数的第一部分均不会发生变化，因此第一部分对答案的贡献即为该数被操作到的期望数，即 $(v - v \bmod L) \times \frac {k \times n^{k-1}} {n^k}$。

第二部分值小于 $L$ ，由于值域较小而数组元素数量较多，考虑使用桶进行计数。不难计算出 $f[i][j]$ 表示所有使用了 $i$ 次操作的方案（共 $n^i$ 种）中的值为 $j$ 的元素数量之和，通过对每一个状态统计下次操作若操作到该值时该状态对总答案的贡献即可求出答案： $\frac 1 {n^k} \times \sum_i \sum_j j \times f[i][j] \times n^{k-i-1}$。

当 $k=17$ 时 $L$ 可能过大以至于 DP 时间复杂度不可接受。容易发现第 $k$ 次操作的修改操作对总答案无影响，因此令 $L = \mathrm{lcm}_{1 \le i < k}~i$ 即可。

总时间复杂度 $O(n + k \times \mathrm{lcm}_{1 \le i < k}~i)$ 。

代码

View on GitHub

/**
 * @file 1626F.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-02-01
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My tutorial: https://macesuted.moe/article/cf1626f
 */

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxk 18
#define maxn 10000005
#define maxL 720725
#define mod 998244353

int a[maxn];
long long f[maxk][maxL];

long long Pow(long long a, long long x) {
    long long ans = 1;
    while (x) {
        if (x & 1) ans = ans * a % mod;
        a = a * a % mod, x >>= 1;
    }
    return ans;
}

void solve(void) {
    int n = read<int>(), a0 = read<int>(), x = read<int>(), y = read<int>(), k = read<int>(), M = read<int>();
    a[1] = a0;
    for (int i = 2; i <= n; i++) a[i] = (1LL * a[i - 1] * x % M + y) % M;
    int L = 720720;
    long long ans = 0, coeff = k * Pow(n, k - 1) % mod;
    for (int i = 1; i <= n; i++) {
        int rest = a[i] % L;
        f[0][rest]++;
        ans = (ans + 1LL * (a[i] - rest) * coeff) % mod;
    }
    for (int i = 0; i < k; i++) {
        long long t = Pow(n, k - i - 1);
        for (int j = 0; j < L; j++)
            if (f[i][j]) {
                f[i + 1][j] = (f[i + 1][j] + 1LL * f[i][j] * (n - 1) % mod) % mod;
                f[i + 1][j - j % (i + 1)] = (f[i + 1][j - j % (i + 1)] + f[i][j]) % mod;
                ans = (ans + 1LL * j * f[i][j] % mod * t) % mod;
            }
    }
    cout << ans << endl;
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

👍 4

moyujiang 菜狗 LV 10 @ 2022-1-30 20:18:14

#010 2022.1.30

CF1588F Jumping Through the Array

题目大意

给定序列 $a_{1\cdots n}$ 与排列 $p_{1\cdots n}$ ，进行 $q$ 次操作如下：

1 l r，询问 $\sum_{i=l}^r a_i$ 的值；
2 v x，临时连边 $i\to p_i$ ，将 $v$ 能到达的所有点 $u$ 的 $a_u\gets a_u+x$ ；
3 x y，交换 $p_x,p_y$ 。

$1\leq n,q\leq 2\times 10^5$ ， $-10^8\leq a_i\leq 10^8$ 。

题解

分析

图由若干个环构成，交换 $p_x,p_y$ 性质很不优美，并且显然修改的方式不便于上线段树，所以考虑上根号复杂度的处理。为了更符合思维习惯，我们先考虑没有 $3$ 操作的简化版本。

先考虑序列分块，但因为修改对于查询来说的无序而没啥用，所以考虑操作分块，每 $S$ 个操作统一处理一次，总共处理 $O(\frac qS)$ 次。那么我们计算答案的方式就是先有一个前缀和数组，对于这 $S$ 个操作中的询问，它的答案是前缀和相减再加上这个询问之前块内操作对它的贡献，很容易想到把有修改操作的环提出来，修改操作就在环上打标记，询问操作就暴力遍历所有在块内被修改了的环来计算贡献，这个贡献就是点数乘上标记，标记直接用，点数可以考虑在每个环的点的集合（STL::set）里二分得到。然后处理完操作之后再对于每个环把 add 标记打在点上，更新前缀和数组。至此我们得到了一个带根号还带 $\log$ 的算法，它还不能处理 $3$ 操作，但是没有关系。

有了 $3$ 操作之后仍然保留整体处理的思想，把所有 $2,3$ 操作中的 $v,x,y$ 设置为关键点，一条链定义为从一个关键点的后继出发，直到遇到第一个关键点为止，那么这条链始终处于同一个环中，且只有 $O(S)$ 个，我们将其缩起来以链为基础单位来处理，每次统一处理操作时标记每个点所处的链，复杂度 $O(n)$ 。为什么要这么做呢？因为 $3$ 操作最大的影响是破坏了环的完整结构，而我们如果还要继续利用整体处理的思想，就需要另外找到一个不变的东西，不难发现这一条链中只有链尾是可能改变 $p$ 的，即它的结构在有了 $3$ 操作后依然保持相对不变。

于是维护一个到这次处理之前的前缀和，顺序遍历操作， $2$ 操作遍历目前环上的每条链，在链上打 add 的标记，复杂度 $O(S)$ ， $3$ 操作只需要直接交换 $p$ 即可，复杂度 $O(1)$ 。

接下来考虑 $1$ 操作的答案就是前缀和算出来的答案再加上块内之前修改的贡献，那么需要枚举每一条链对这次询问的贡献，其等于这条链当前的 add 标记乘上其中有多少个点在 $[l,r]$ 内，add 标记可以直接查，求链中有多少点编号在区间内这一步如果按照之前直接二分来搞的话可以做到 $O(S\log n)$ ，那么总复杂度就是 $O(\frac qS \cdot n+qS\log n)$ ，将 $n,q$ 视为同阶，则在 $S=\sqrt \frac {n}{\log n}$ 时取得理论最优复杂度 $O(n\sqrt{n\log n})$ ，貌似可以通过。

但是我们有简单的办法可以去掉这只 $\log$ ，具体可以考虑先将其预处理出来：得到每个点所在的链之后按编号从小到大遍历每一个点，并给其所在的链的权值 +1，则遍历到 $i$ 时链的权值的意义就是链中编号属于 $[1,i]$ 的点的个数，于是把询问拆成前缀相减来做就可以做到总复杂度 $O(n\sqrt n)$ 。

我写的代码跑的不是很快，但是应该比较简洁，代码长度不到 2kb，属实是操作分块练习好题。

代码

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=3e5+10,S=500;
int n,a[N],p[N],q,c[N],lim,s[N],in[N],add[N];
struct qry{int op,x,y;}b[S];int now;
struct node{
	int id,op,x;
	bool operator < (const node &X) const {return x<X.x;}
}d[S<<1];int top;
int num[S][S<<1],po[N],h,db[N];
int st[N],stop;
#define mem(arr) memset(arr,0,sizeof arr)
void work(){
	mem(in),mem(c),mem(add),mem(num),top=h=0;
	For(i,1,now){
		int op=b[i].op,x=b[i].x,y=b[i].y;
		if(op==1){if(x-1)d[++top]=(node){i,-1,x-1};d[++top]=(node){i,1,y};}
		if(op==2)c[x]=1;
		if(op==3)c[x]=c[y]=1;
	}For(i,1,n)if(c[i])po[++h]=i;
	For(i,1,h){int u=p[po[i]];stop=0;
		while(1){st[++stop]=u;if(c[u])break;u=p[u];}
		db[i]=u=st[stop];while(stop)in[st[stop--]]=u;
	}
	int t=0;sort(d+1,d+1+top);For(i,1,top){
		while(t<d[i].x)add[in[++t]]++;
		For(j,1,h)num[d[i].id][j]+=d[i].op*add[db[j]];
	}mem(add);
	For(i,1,now){
		int op=b[i].op,x=b[i].x,y=b[i].y;
		if(op==1){
			int ans=s[y]-s[x-1];
			For(j,1,h)ans+=num[i][j]*add[db[j]];
			printf("%lld\n",ans);
		}
		if(op==2){int u=in[x];do add[u]+=y,u=in[p[u]];while(u!=in[x]);}
		if(op==3)swap(p[x],p[y]);
	}
	For(i,1,n)a[i]+=add[in[i]],s[i]=s[i-1]+a[i];now=0;
}
signed main(){
	For(i,1,n=read())s[i]=s[i-1]+(a[i]=read());
	For(i,1,n)p[i]=read();q=read(),lim=sqrt(q);
	while(q--){
		int op=read(),x=read(),y=read();
		b[++now]=(qry){op,x,y};
		if(now==lim)work();
	}if(now)work();
	return 0;
}

👍 4

Macesuted QWQ LV 10 SU @ 2022-1-29 22:32:34

#009 2022.1.29

标签：动态规划，笛卡尔树。

题目大意

在一个排列中我们定义 $x$ 是好的当且仅当排列中所有包含 $x$ 的子串中恰好有 $m$ 种不同的子串内元素最大值。询问恰好有 $k$ 个好元素的 $n$ 排列数量。

$m,k \le n \le 100$

题解

分析

不难发现排列中包含 $x$ 的子串的不同的子串内最大值数量等于 $x$ 向左的最长上升子序列长度加上向右的最长上升子序列长度，而这个值是等于对原序列建立笛卡尔树后 $x$ 到树根之间的距离。询问转化为询问有多少个 $n$ 排列满足其笛卡尔树上恰好有 $k$ 个结点深度为 $m$ 。

考虑笛卡尔树的建立过程，我们每次从整个序列中取出最大值，然后从这个最大值所在的位置将原序列分为两半递归构造。我们可以考虑进行区间 DP， $f[l][r][m][k]$ 表示 $l$ 到 $r$ 之间的满足笛卡尔树上恰好有 $k$ 个点深度为 $m$ 的排列数量。转移时我们枚举一个 $m \in [l,~r]$ ，钦定他为区间内的最大值，然后将区间分为两半，再暴力枚举这 $k$ 个深度为 $m$ 的点中有几个是在左区间，最终使用组合数将左右区间的两个排列合并起来即可。进一步我们发现 $l$ 和 $r$ 的具体值我们并不关心，因此仅记录区间长度即可。

时间复杂度 $O(n^2 \times m \times k^2)$ ，空间复杂度 $O(n \times m \times k)$ 。需要加上一些剪枝。

代码

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define maxn 105

typedef pair<int, int> pii;

int f[maxn][maxn][maxn];
int C[maxn][maxn], fac[maxn];

int n, m, k, mod;

int dp(int len, int up, int cnt) {
    if (!len) return cnt == 0;
    if (up == 1) return cnt == 1 ? fac[len] : 0;
    if ((cnt - 1) * 2 > len) return 0;
    if (f[len][up][cnt] >= 0) return f[len][up][cnt];
    int answer = 0;
    for (int mid = 0; mid < len; mid++)
        for (int t = 0; t <= cnt; t++)
            answer = (answer +
                      dp(mid, up - 1, t) * dp(len - mid - 1, up - 1, cnt - t) % mod * C[len - 1][mid]) %
                     mod;
    return f[len][up][cnt] = answer;
}

void work(void) {
    memset(f, -1, sizeof(f));
    cin >> n >> m >> k >> mod;
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
    for (int i = 0; i < maxn; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    cout << dp(n, m, k) << endl;
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cout << setiosflags(ios::fixed) << setprecision(11);
    int _ = 1;
    // cin >> _;
    while (_--) work();
    return 0;
}

Macesuted QWQ LV 10 SU @ 2022-1-28 10:43:07

#008 2022.1.28

题目大意

给出一个长度为 $2 \times n$ 的初始由 ( 和 ) 构成的字符串 $s$ 。你需要处理 $q$ 个操作，操作类型如下：

给出 $l,~r$ ，保证 $\forall i \in (l,~r),~s[i]='.'$ ，将 $s[l]$ 和 $s[r]$ 换为 .。
给出 $l,~r$ ，保证 $s[l] \sim s[r]$ 为一个合法的括号序列，求其中满足两端不为 . 的合法括号串的数量。

$n,q \le e \times 10^5$

题解

分析

考虑将输入的字符串 $s$ 按括号包含关系建树，1 操作即为删掉一个叶子节点，2 操作为询问连续若干兄弟节点的答案和。

考虑如何计算树上每一个节点子树内的答案。不难发现每一个节点对应子树上的答案即为其所有孩子节点的答案加上 $\binom {\text{孩子数量}} 2$ 再加一（即选取整个子树）。2 操作询问时只需要将所有被询问包含的兄弟节点的答案相加后再加上 $\binom {\text{兄弟节点数量-1}} 2$ 即可算出答案。

考虑如何计算区间内兄弟节点的数量。我们可以在每一个节点上建立一个树状数组，并记录每个节点是他父亲的第几个孩子。初始时树状数组上每一个位置均为 $1$ ，在某个孩子被删掉后将树状数组上对应位置改为 $0$ 。询问时通过计算树状数组上 $l$ 对应的位置与 $r$ 对应的位置之间 $1$ 的数量即可得出其间包含多少兄弟节点。

如何在 1 操作后维护每个节点的答案呢。考虑在树上进行差分，即每个节点仅记录 $\binom {\text{孩子数量}} 2$ ，不再加上孩子节点的答案和。计算答案时只需要计算连续若干棵子树的总和即可。按照 DFS 序建序列并使用树状数组维护即可解决问题。在 1 操作删除叶子节点时只需要单点修改其父亲节点的答案即可。

总时间复杂度 $O((n + m) \log n)$ 。

代码

/**
 * @file 1625E2.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-01-27
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 300005

typedef pair<int, int> pii;

class FenwickTree {
   private:
    vector<long long> tree;

   public:
    void resize(int n) { return tree.resize(n + 1); }
    void add(int p, long long val) {
        for (int i = p; i < (int)tree.size(); i += i & -i) tree[i] += val;
        return;
    }
    long long sum(int p) {
        long long sum = 0;
        for (int i = p; i; i -= i & -i) sum += tree[i];
        return sum;
    }
} FT, sons[maxn];

bool a[maxn];
pii b[maxn];
int bel[maxn], cnt = 0;
int dfni[maxn], dfno[maxn], fa[maxn], son[maxn], dfnCnt = 0;

vector<set<int>> graph;

void dfs(int p, int pre = -1, int sonId = 0) {
    fa[p] = pre, son[p] = sonId;
    dfni[p] = ++dfnCnt;
    FT.add(dfni[p], (long long)graph[p].size() * ((long long)graph[p].size() + 1) / 2);
    sons[p].resize(graph[p].size());
    int cnt = 0;
    for (auto i : graph[p]) dfs(i, p, ++cnt), sons[p].add(cnt, 1);
    dfno[p] = dfnCnt;
    return;
}

void solve(void) {
    int n = read<int>(), m = read<int>();
    graph.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        char c = getch();
        while (c != '(' && c != ')') c = getch();
        a[i] = (c == '(');
    }
    stack<int> S;
    for (int i = 1; i <= n; i++)
        if (a[i])
            S.push(i);
        else if (!S.empty())
            bel[S.top()] = bel[i] = ++cnt, b[cnt] = {S.top(), i}, S.pop();
    while (!S.empty()) S.pop();
    for (int i = n; i; i--)
        if (a[i] && bel[i]) {
            while (!S.empty() && b[S.top()].second < b[bel[i]].second) graph[bel[i]].insert(S.top()), S.pop();
            S.push(bel[i]);
        }
    while (!S.empty()) graph[0].insert(S.top()), S.pop();
    FT.resize(cnt + 1);
    dfs(0);
    while (m--) {
        int t = read<int>(), l = read<int>(), r = read<int>(), f = fa[bel[l]];
        if (t == 1) {
            FT.add(dfni[f], -(long long)graph[f].size() * ((long long)graph[f].size() + 1) / 2);
            graph[f].erase(bel[l]);
            FT.add(dfni[f], +(long long)graph[f].size() * ((long long)graph[f].size() + 1) / 2);
            sons[f].add(son[bel[l]], -1);
        } else {
            long long cnt = sons[f].sum(son[bel[r]]) - sons[f].sum(son[bel[l]] - 1);
            write(FT.sum(dfno[bel[r]]) - FT.sum(dfni[bel[l]] - 1) + cnt * (cnt + 1) / 2), putch('\n');
        }
    }
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

undefined 可爱！ LV 10 SU @ 2022-1-28 13:37:04

爷爷你关注的帖子更新啦

Maplisky 枫 LV 10 @ 2021-11-4 17:51:30

#007 2021.11.4

[JOI 2021 Final] ロボット

题目大意

给出一张 $n$ 个点 $m$ 条边的简单无向图，每条边带有 $1\sim m$ 中的一种颜色。从 $1$ 号点出发，每次指示一种颜色，如果所在顶点恰有一条该颜色的边，就沿这条边前进。每条边给定一个固定的修改颜色的费用 $P_i$ 。最小化到 $n$ 号点的费用。

$2\le n\le 10^5$ ， $1\le m \le 2\times 10^5$ ， $1\le P_i \le 10^9$ 。

题解

Analysis

本题本质上就是一个最短路问题，关键在于考虑改变道路的颜色。我们计算新的花费以重建一张图来跑最短路。

仅有一条与当前路口相连的路是要走的颜色，那么直接走过去即可，花费为 $0$ 。
否则分为两种情况，记当前与当前路口相连的颜色为 $c$ 的道路的总花费为 $sum_c$ ，要去的点为 $y$ ，花费为 $p_y$ 。
1. 将要走的边改为独有的颜色，单次花费为 $p_y$ 。
2. 改变与当前路口相连且与要走的路颜色相同的其他道路，单次花费为 $sum_c-p_y$ 。

为了简便我们可以直接用 std::map 记录每种颜色对应的花费 ~~（给了 2s 这不随便乱用）~~，后面不再赘述。

自然地，以上朴素想法引发了一些问题。

Q1：是否存在一种情况，使得不能将一条边改为独有的颜色？

显然不存在。注意到一共有 $m$ 条边， $m$ 种颜色，那么显然每条边都可以改为独有的颜色。或者考虑菊花图的情况，这时一个点占有的颜色种类最多。但此时无需改变颜色。

Q2：一条边会不会被重复改变颜色？

不会。一条边走两次显然不是最优解。

Q3：何时无法到达？

当点 $1$ 与点 $n$ 不连通时。由于原图所有边都是无向边，且不存在无法抵达相邻点的情况，因此只有不连通时才无法到达。

明确以上三个基本问题以后就可以开始做题了。

对于 $\text{subtask 1}$ ，直接暴力拆点，将每个点拆成 $m$ 个点对应 $m$ 种不同颜色，然后重新计算边权即可。

对于 $\text{subtask 2}$ ，我们发现无论怎么跑每条边的花费一定是 $1$ ，因此直接当最短路跑就行了。

对于 $\text{subtask 3}$ ，我们发现基于原有的边直接跑最短路是有问题的。简单的说，在边权不同时，通过修改一条边抵达另一个点的操作存在“后效性”。

考虑一种最简单的图形。

我们发现输出是 $5$ ，而手模发现答案是 $4$ ，即改变 $1 \leftrightarrow 4$ 这一条边。

每次修改边的颜色，会对与目标点相连的边的颜色状态产生影响。且影响的边是和被改变边原来颜色相同的边。也就是说，如果我们改变当前边，那么从目标点 $y$ 继续走颜色为 $c$ 的道路，相当于跳过中间点，直接抵达另一个点。

对每个点已拥有的颜色建立虚点，增加每个点对相应虚点的虚边即可。这里同样使用 std:set 记录。

因为对每条边至多建两个虚点，加上初始的 $n$ 个点，所以整张图最多有 $n+2\times m$ 个点。每两个通过非虚边连接的点 $x,y$ 及其对应颜色的虚点 $x',y'$ 至多连三条无向边，即 $x \leftrightarrow y$ ， $x\leftrightarrow y'$ ， $x'\leftrightarrow y$ ，因此最多有 $3\times m$ 条边。由于链式前向星连的是单项边，因此要开 $6\times m$ 条边。

最后跑个最短路即可。时间复杂度 $\mathcal{O}((n+m)\times \log(n+m))$ 。

Code:

#include <bits/stdc++.h>
#define ld double
#define eps (1e-8)
#define ll long long
#define lld long double
#define ull unsigned long long
#define Min(x, y) ((x) > (y) and ((x) = (y)))
#define Max(x, y) ((x) < (y) and ((x) = (y)))
#define Add(x,y) (((x)+=(y))>=mod and ((x)-=mod))
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define PF(i, a, b) for (int i = (a); i >= (b); --i)
#define For(i, x) for (int i = head[(x)]; i; i = net[(i)])
using namespace std;
bool beginning;
inline int read();
const int N=5e5+5,E=N<<3;//赛时防挂，不要在意
int n,m;
int ver[E],net[E],head[N],tot;
ll edge[E];
inline void add(int x,int y,ll z) {
	ver[++tot]=y,net[tot]=head[x],edge[head[x]=tot]=z;
}
struct P {
	int to,c;
	ll p;
	P(int x=0,int y=0,ll z=0) {
		to=x,c=y,p=z;
	}
};
vector<P>f[N];
ll dis[N];
struct Hp {
	int d;
	ll dis;
	bool operator <(const Hp &a)const {
		return dis>a.dis;
	}
};
bool vis[N];
inline void dij() {
	memset(dis,0x3f,sizeof(dis));
	priority_queue<Hp>q;
	dis[1]=0;
	q.push({1,0});
	Hp t;
	while(!q.empty()){
		t=q.top();
		q.pop();
		if(vis[t.d])continue;
		vis[t.d]=1;
		For(i,t.d){
			int &y=ver[i];
			if(dis[y]>dis[t.d]+edge[i]){
				dis[y]=dis[t.d]+edge[i];
				q.push({y,dis[y]});
			}
		}
	}
	printf("%lld\n",dis[n]==dis[0]?-1:dis[n]);
}
map<int,ll>mp,vtl[N];
bool ending;
int main() {
	cerr<<1.0*(&beginning-&ending)/1024/1024<<"MB\n----------\n";
	n=read(),m=read();
	int a,b,c,p;
	F(i,1,m) {
		a=read(),b=read(),c=read(),p=read();
		f[a].emplace_back(P<%b,c,p%>);
		f[b].emplace_back(P<%a,c,p%>);
	}
	int cnt=n;
	F(i,1,n){
		for(P y:f[i])if(!mp[y.c])vtl[i][y.c]=++cnt,mp[y.c]=1;
		for(P y:f[i])mp[y.c]=0;
	}
	mp.clear();
	F(i,1,n) {
		for(P y:f[i])mp[y.c]+=y.p;

		for(P y:f[i]) {
			add(i,y.to,min(y.p,mp[y.c]-y.p));
			add(i,vtl[y.to][y.c],0);
			add(vtl[i][y.c],y.to,mp[y.c]-y.p);
		}

		for(P y:f[i])mp[y.c]=0;
	}
	
	dij();
	return 0;
}
inline int read() {
	int x = 0;
	bool f = 1;
	char c = getchar();
	while (!isdigit(c)) {
		f = c ^ 45;
		c = getchar();
	}
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? x : -x;
}

新建的边切记要开 long long。

Maplisky 枫 LV 10 @ 2021-11-4 17:52:33

来填坑了（
HappyCode @ 2021-11-4 18:30:09

更新了！
_JY_ @ 2021-11-12 9:40:46

每日一题（x）每周一题（√）
Maplisky 枫 LV 10 @ 2021-11-12 13:28:18

@

Macesuted QWQ LV 10 SU @ 2021-10-10 15:42:55

#006 2021.10.10

题目大意

给出一个 $n$ 个点 $m$ 条边的无向联通图，有 $q$ 组询问，每组询问给出 $x,~y,~l,~r$ ，询问是否存在一个点 $p$ 满足：

存在一条从 $x$ 到 $p$ 的路径满足路径上所有节点（包含两个端点）编号均不小于 $l$ 。
存在一条从 $p$ 到 $y$ 的路径满足路径上所有节点（包含两个端点）编号均不大于 $r$ 。

$n,~q \le 2 \times 10^5,~m \le 4 \times 10^5$

题解

分析

由于对 $x \to p$ 和 $p \to y$ 的路径的限制均为“均不小于 $x$ ”或“均不大于 $x$ ”的形式，我们考虑使用 Kruskal 重构树解决这一问题。因为当我们将每条边的边权设为其两端端点的较大值时重构树上两点的 LCA 的权值即为这两点在原图上点权最大值最小的路径所对应的路径点权最大值。维护最大的路径最小值的方法同理。

由于我们无法同时满足这两个限制，因此我们考虑建两棵 Kruskal 重构树，第一棵维护路径上最大的最小值，第二棵维护路径上最小的最大值。对于一组询问，考虑合法的 $p$ 可能在什么位置：

$p$ 在第一棵树上位于 $x$ 的深度最小的满足 $\ge l$ 的祖先 $fx$ 的子树中。
$p$ 在第二棵树上位于 $y$ 的深度最小的满足 $\le r$ 的祖先 $fy$ 的子树中。

考虑在两棵树上分别求出所有节点的 dfs 序 dfn[0/1][i]，对于节点 $i$ 将其视为坐标系上一个位于 $(dfn[0][i],~dfn[1][i])$ 的点。则每个询问等同于询问坐标系上一个矩形内是否存在点。将所有询问离线后二维数点即可。

代码

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c <= '9' && c >= '0'; c = getchar())
        x = x * 10 + (c & 15);
    return x * f;
}

#define maxn 200005
#define maxlgn 20

typedef pair<int, int> pii;

class KruskalTree {
   private:
    int f[maxn];
    bool vis[maxn];

    int getfa(int p) { return f[p] == p ? p : f[p] = getfa(f[p]); }

   public:
    vector<vector<int>> tree;
    int fa[maxn][maxlgn], dfni[maxn], dfno[maxn], tim = 0;
    void dfs(int p, int pre) {
        dfni[p] = ++tim;
        fa[p][0] = pre;
        for (int i = 1; i < maxlgn; i++) fa[p][i] = fa[fa[p][i - 1]][i - 1];
        for (auto i : tree[p]) dfs(i, p);
        dfno[p] = tim;
        return;
    }
    void build(int n, const vector<vector<int>>& graph, int p[]) {
        for (int i = 1; i <= n; i++) vis[i] = false, f[i] = i;
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            vis[p[i]] = true;
            for (auto j : graph[p[i]])
                if (vis[j] && getfa(p[i]) != getfa(j))
                    tree[p[i]].push_back(getfa(j)), f[getfa(j)] = p[i];
        }
        return dfs(p[n], p[n]);
    }
} T[2];
class BIT {
   private:
    int tree[maxn];

   public:
    void add(int p, int v) {
        for (int i = p; i < maxn; i += i & -i) tree[i] += v;
        return;
    }
    int sum(int p) {
        int sum = 0;
        for (int i = p; i; i -= i & -i) sum += tree[i];
        return sum;
    }
} bit;

struct Ask {
    int l, r, id, op;
};

int p[maxn];

vector<vector<int>> graph;
vector<Ask> asks[maxn];
int points[maxn];
int answer[maxn];

int main() {
    ios::sync_with_stdio(false);
    cout << setiosflags(ios::fixed) << setprecision(8);
    int n = read<int>(), m = read<int>(), q = read<int>();
    graph.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int x = read<int>() + 1, y = read<int>() + 1;
        graph[x].push_back(y), graph[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) p[i] = n - i + 1;
    T[0].build(n, graph, p), reverse(p + 1, p + n + 1), T[1].build(n, graph, p);
    for (int i = 1; i <= n; i++) points[T[0].dfni[i]] = T[1].dfni[i];
    for (int i = 1; i <= q; i++) {
        int S = read<int>() + 1, E = read<int>() + 1, l = read<int>() + 1, r = read<int>() + 1;
        for (int i = maxlgn - 1; ~i; i--)
            if (T[0].fa[S][i] >= l) S = T[0].fa[S][i];
        for (int i = maxlgn - 1; ~i; i--)
            if (T[1].fa[E][i] <= r) E = T[1].fa[E][i];
        if (T[0].dfni[S] - 1) asks[T[0].dfni[S] - 1].push_back({T[1].dfni[E], T[1].dfno[E], i, -1});
        asks[T[0].dfno[S]].push_back({T[1].dfni[E], T[1].dfno[E], i, +1});
    }
    for (int i = 1; i <= n; i++) {
        bit.add(points[i], +1);
        for (auto j : asks[i]) answer[j.id] += j.op * (bit.sum(j.r) - bit.sum(j.l - 1));
    }
    for (int i = 1; i <= q; i++) cout << (answer[i] >= 1) << endl;
    return 0;
}

Thujoars LV 10 @ 2021-10-10 19:33:30

zc!
HappyCode @ 2021-11-1 17:06:12

每日一题 -> 每月一题？
都快一个月没更新了
Maplisky 枫 LV 10 @ 2021-11-4 18:00:28

@ 大家也来贡献点么/kel

Macesuted QWQ LV 10 SU @ 2021-9-25 13:25:18

#005 2021.9.25

题意

问满足下列条件的 $n \times m$ 的 01 矩阵 $a$ 的数量：

$\exists [l,~r] (1 \le l \le r \le n)$ ，满足 $\forall i \in [l,~r],~\sum_j a_{i,j} =2$ 且 $\forall i \notin [l,~r],~\sum_j a_{i,j}=0$ 。
设 $[l,~r]$ 中的每一行的第一个值为 $1$ 的位置的下标为 $x_i$ ，第二个值为 $1$ 的位置的下标为 $y_i$ ，则： $\exists t \in [l,~r]$ ，满足 $\forall i \in [l,~t-1],~x_i \ge x_{i+1},~y_i \le y_{i+1}$ 且 $\forall i \in [t,~r-1],~x_i \le x_{i+1},~y_i \ge y_{i+1}$。

题解

分析

考虑使用 DP 解决本题。

令 $f[i][j]$ 表示考虑洞的前 $i$ 行（该 $i$ 行都在洞的中间位置 $t$ 的上方）且第 $i$ 行的 $y_i-x_i+1=j$ 时该洞的构造方案（不考虑洞在矩阵中的摆放位置）。

考虑枚举第 $i-1$ 行的长度以及与第 $i$ 行的相对位置，得出转移方程：

f[i][j]=\sum_{t=0}^{j}f[i-1][t] \times (j-t+1)

尝试使用该数据描述最终答案 $Ans$ ，考虑枚举中间位置 $t$ 的行编号以及该行 $y_i-x_i+1$ 的大小。同时由于可能存在构造洞的方案满足第 $t$ 行与相邻的几行的形态完全相同，为了防止算重，考虑令 $t$ 为洞的最大的满足 $y_i-x_i+1$ 最大的行数，同时枚举 $t+1$ 行的长度（小于 $t$ 行长度），算出最终答案：

$$\begin{aligned} Ans&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{l=1}^{i} f[i-l+1][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{r=i+1}^{n} f[r-i][b] \big) \times (a - b + 1))\\\\ &=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{t=1}^{i} f[t][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{t=1}^{n-i} f[t][b] \big) \times (a - b + 1)) \end{aligned} $$

令 $g[i][j] = \sum_{k=1}^{i} f[k][j]$ 。

$$Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + \sum_{b=0}^{a-1} g[n-i][b] \times (a-b+1)) $$

令 $h[i][j]=\sum_{k=0}^{j-1} g[i][k] \times (j-k+1)$ 。

$$Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + h[n-i][a]) $$

处理 $f[i][j]$ 前缀和优化到 $O(nm)$ ，处理 $g[i][j]$ $O(nm)$ ，处理 $h[i][j]$ 前缀和优化到 $O(nm)$ ，计算答案 $Ans$ $O(nm)$ 。

总时间复杂度 $O(nm)$ 。

代码

/**
 * @author Macesuted (macesuted@outlook.com)
 * @copyright Copyright (c) 2021
 * @brief
 *      My solution: https://www.macesuted.cn/article/cf295d/
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (register int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
inline T read() {
    register T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
inline void write(const T& t) {
    register T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 2005
#define mod 1000000007

long long f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], cac[maxn][maxn];

int main() {
    int n = read<int>(), m = read<int>();
    for (register int i = 0; i <= m - 2; i++) f[1][i] = 1;
    for (register int i = 2; i <= n; i++) {
        f[i][0] = cac[i][0] = f[i - 1][0];
        for (register int j = 1; j <= m - 2; j++)
            cac[i][j] = (cac[i][j - 1] + f[i - 1][j]) % mod, f[i][j] = (f[i][j - 1] + cac[i][j]) % mod;
    }
    for (register int i = 1; i <= n; i++)
        for (register int j = 0; j <= m - 2; j++)
            g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
    memset(cac, 0, sizeof(cac));
    for (register int i = 1; i < n; i++)
        for (register int j = 1; j <= m - 2; j++)
            cac[i][j] = (cac[i][j - 1] + g[i][j - 1]) % mod, h[i][j] = (h[i][j - 1] + cac[i][j] + g[i][j - 1]) % mod;
    long long answer = 0;
    for (register int i = 1; i <= n; i++)
        for (register int j = 0; j <= m - 2; j++)
            answer = (answer + (m - j - 1) * g[i][j] % mod * (1 + h[n - i][j])) % mod;
    write(answer), putch('\n');
    return 0;
}

Rratic LV 5 @ 2021-9-25 16:25:27

你们开始卷快速I/O了/kk
alpha1022 LV 4 @ 2021-10-28 13:07:27

要不括号加上 \left \right 吧（（

Maplisky 枫 LV 10 @ 2021-9-18 16:10:54

#004 2021.9.18

bzoj3836 Tourism

题意简述

给定 $n$ 个点， $m$ 条边的无向图，第 $i$ 个点建旅游站的费用为 $c_i$ 。保证任意两点间不存在长度超过 $10$ 的路径。

问最小的费用，使得每个点建立了旅游站，或与其直接相连的点里有至少一个建立了旅游站。

题解

Analysis

显然是个 NP 问题，然而题目保证「任意两点间不存在节点数超过 $10$ 的简单路径」，就有了一定可操作性。

先考虑图为树的简化版。就是一个最小覆盖集的问题。经典的树形 dp，用 $dp_{i,s=\{0/1/2\}}$ 表示满足 $i$ 的子树（不包含 $i$ ）被完全覆盖，选择了 $i$ 、未选 $i$ 且未被覆盖、未选 $i$ 但已经被覆盖的情况。事实上就是简单的状压。

由于每个连通快的搜索树的深度最大只有 $10$ ，且非树边一定是 Back edge，因此同样可以考虑状压。同样记 $dp_{i,s}$ 表示 $i$ 点的状态。由于从树上问题变为图上问题，一个点同时会被其子树中的点影响，也会被其祖先影响，因此这里 $dp$ 的定义有一点点不同。

定义 $dp_{i,s}$ 为，满足 $i$ 的“子树”被覆盖（不包含 $i$ ），且 dfs 序比 $i$ 小的点被覆盖（不包含 $i$ 到“根”路径上的点）， $i$ 到“根”的路径上每个点的状态为 $s$ 的最小代价。状态 $s$ 中，其第 $j$ 位为 $i$ 到根的路径上深度为 $j$ 的点的状态。与树上的情形类似，状态有三种：

1.选了 $i$ ；

2.没选 $i$ ，且 $i$ 未被覆盖；

3.没选 $i$ ，且 $i$ 已被覆盖。

由于祖先和儿子相互影响，每个点的状态需要更新两次。即 $father \to son$ 和 $son\to father$ 。首先用父亲来更新儿子。

若 $i$ 不选，若有直接与 $i$ 相连且已经选了的点，那么有：

dp_{fa_i,s}\to dp_{i,s+2\times 3^{dep_i}}

否则：

dp_{fa_i,s}\to dp_{i,s+3^{dep_i}}

若 $i$ 选，由于存在 Back edge， $i$ 到“根”的路径上一些点的状态可能由 $1$ 变到 $2$ 。我们记新的状态为 $s'$ ，则：

dp_{fa_i,s}+c_i \to dp_{i,s'}

剩下的就是 $i$ 的“子树”对 $i$ 的影响了。由于要先统计“子树”的状态，需要在递归完每个“子树”时将 $dp_i$ 从“子树”更新一次：

$$dp_{i,s}=\min(dp_{i,s},dp_{son_i,s+2\times 3^{dep_i}}) $$

在以上过程中，每个“子树”会先继承“祖先”的贡献，然后再重新反过来更新“父亲”。这样就处理了“子树”对 $i$ 到“根”的路径的贡献。

最后一点就是优化空间。注意到以上方法的空间是 $\mathcal{O}(3^{10}\times n)$ 的，显然会挂。我们将第一维改为点在搜索树中的深度，空间优化至 $\mathcal{O}(10\times 3^{10})$ 。

时间复杂度为 $\mathcal{O}(10\times 3^{10} \times n)$ 。

code

#include <bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
#define For(i,x) for(reg int i=head[(x)];i;i=net[(i)])
using namespace std;
bool beginning;
inline int read();
const int N = 2e4 + 5, E = 6e4 + 5, inf = 0x3f3f3f3f;
int n, m, c[N], dep[N];
int ver[E], net[E], head[N], tot;
inline void add(int x, int y) {
	ver[++tot] = y, net[tot] = head[x], head[x] = tot;
}
bool vis[N];
int pw[20] {1}, dp[15][E];
#define bit(x,i) (((x)/pw[(i)])%3)
#define Min(x,y) ((x)>(y) and ((x)=(y)))
void dfs(int x) {

	vis[x] = true;
	memset(dp[dep[x]], 0x3f, sizeof(dp[dep[x]]));

	if (dep[x] == 0) {

		dp[0][0] = c[x];
		dp[0][1] = 0;
		dp[0][2] = inf;
	} else {

		static bool ok[N];
		memset(ok, 0, sizeof(ok));

		For(i, x) {
			if (vis[ver[i]])
				ok[dep[ver[i]]] = true;
		}

		F(s, 0, pw[dep[x]] - 1) {

			if (dp[dep[x] - 1][s] < inf) {

				bool hav = false;
				int sta = s;

				F(i, 0, dep[x] - 1) {
					hav |= ok[i] and bit(s, i) == 0;
					sta += pw[i] * (ok[i] and bit(s, i) == 1);
				}

				if (hav)
					Min(dp[dep[x]][s + pw[dep[x]] * 2], dp[dep[x] - 1][s]);

				else
					Min(dp[dep[x]][s + pw[dep[x]]], dp[dep[x] - 1][s]);

				Min(dp[dep[x]][sta], dp[dep[x] - 1][s] + c[x]);
			}

		}
	}

	For(i, x) {

		if (vis[ver[i]])
			continue;

		dep[ver[i]] = dep[x] + 1;
		dfs(ver[i]);
		F(s, 0, pw[dep[x] + 1] - 1) {
			dp[dep[x]][s] = min(dp[dep[x] + 1][s], dp[dep[x] + 1][s + pw[dep[x] + 1] * 2]);
		}

	}

}
bool ending;
int main() {
	//  printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
	n = read(), m = read();
	F(i, 1, n)c[i] = read();
	int x, y;
	F(i, 1, m) {
		x = read(), y = read();
		add(x, y), add(y, x);
	}

	F(i, 1, 10)pw[i] = pw[i - 1] * 3;

	int ans = 0;

	F(i, 1, n)if (!vis[i])
		dfs(i), ans += min(dp[0][0], dp[0][2]);

	printf("%d", ans);
	return 0;
}
inline int read() {
	reg int x = 0;
	reg char c = getchar();

	while (!isdigit(c))
		c = getchar();

	while (isdigit(c))
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();

	return x;
}

创造君核反应堆 LV 8 @ 2021-9-21 0:16:27

提个建议，后括号之后也要加空格
Macesuted QWQ LV 10 SU @ 2021-9-21 6:52:10

@ 按照一些规范来说是不应该加的，另外不要那么严格对待格式么（。
创造君核反应堆 LV 8 @ 2021-9-22 22:03:07

@ 强迫症晚期，不要介意（（
shinecms LV 6 @ 2022-7-3 11:06:21

想问一下你们逗号后面不打空格吗
shinecms LV 6 @ 2022-7-3 11:06:24

想问一下你们逗号后面不打空格吗

Maplisky 枫 LV 10 @ 2021-9-17 10:42:02

#003 2021.9.17

[COCI2016-2017 Contest#7 T6] Klavir

题意简述

给定一个字符串，每次等概率随机产生一个新的字符。问产生该字符串的每一前缀的期望次数。

题解

Declare

下文中，记弹 $1\to i$ 的期望弹奏次数为 $dp_i$ ，且 $dp_1=n$ 。
记音符串为 $a_i$ 。

Analysis

首先读懂题意，我们发现，对于当前正在弹奏的一段乐曲，有以下两种情况：

当前段的某一后缀与前缀相同。
当前段的任何后缀都与前缀不同。（当前串是“独立”的串）

第二种情况比较简单，对于第二种情况，那么有：

$$dp_i=dp_{i-1}+\frac{1}{n}+\frac{1}{n}\times(dp_i-dp_1+1)+\frac{n-2}{n}\times(dp_i+1) $$

\Rightarrow dp_i=n\times dp_{i-1}

其中，第一个 $\frac{1}{n}$ 表示第 $i$ 个音符直接弹奏正确的期望， $\frac{1}{n}\times(dp_i-dp_1+1)$ 表示这个音符弹奏错误，但与第一个音符相同的期望， $\frac{n-2}{n}\times(dp_i+1)$ 表示这个音符弹奏错误，同时与第一个音符不同的期望。

样例三对应的就是这种情况。

3
3
1 2 3

3
9
27

接下来讨论第一种情况。

前后缀显然可以用 KMP 预处理处理。

设已经弹奏了 $1\to i$ ，现在要弹奏第 $i+1$ 个音符。枚举当前弹奏音符 $j$ 。弹错时，需要找到最长的已经弹对的前缀，记为 $k_j$ ，于是有：

$$dp_{i+1}=dp_i+\frac{1}{n}+\frac{1}{n}\times\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j}+1)(j\neq a_{i+1}) $$$$\Rightarrow dp_{i+1}=dp_i+n+\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j})(j\neq a_{i+1}) $$

其中 $\frac{1}{n}\times\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j}+1)(j\neq a_{i+1})$ 表示弹错了，但已经弹对前缀 $1\to k$ ，接着从 $k+1$ 弹到 $n+1$ 的期望。两层循环跑一下就完了。时间复杂度 $\mathcal{O}(n\times m^2)$ ，实测可过（~~大概是机子跑得快的原因~~）。

    dp[1] = n;
    F(i, 1, m) {//弹第 i 个音符
        long long s = 0;
        F(j, 1, n){//枚举弹的音符
            if (j != a[i + 1]) {
                k = fail[i];
                while (k && a[k + 1] != j) k = fail[k];
                if (a[k + 1] == j) ++k;
                s += dp[i] - dp[k];
            }
        }
        dp[i + 1] = (s + n + dp[i]) % mod;
    }

虽然可过，但理论上还是蛮卡的。接下来我们考虑优化。

我们记当前为第 $i$ 个音符，下一个音符是 $j$ 时，最终跳到的位置为 $f_{i,j}$ ，那么 $f_{i,j}$ 和 $f_{fail_i,j}$ 只有在 $j=a_{i+1}$ 时是不同的。因此对于 $dp_{i+1}$ 可以直接继承 $dp_{fail_{i+1}}$ 的答案，再额外计算 $j=a_{i+1}$ 的贡献即可。从上面方法中，可以看出 $j=a_{i+1}$ 的贡献就是 $n^{i+1}$ 。

综上可得：

dp_i=dp_{fail_i}+n^i

时间复杂度 $\mathcal{O}(m)$ ，算是十分优秀了。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define _min(x, y) ((x) < (y) ? (x) : (y))
#define _max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) > (y) and ((x) = (y)))
#define Max(x, y) ((x) < (y) and ((x) = (y)))
#define F(i, a, b) for (reg int i = (a); i <= (b); ++i)
#define PF(i, a, b) for (reg int i = (a); i >= (b); --i)
#define For(i, x) for (reg int i = head[(x)]; i; i = net[(i)])
using namespace std;
bool beginning;
inline int read();
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, m, a[N], fail[N];
inline void init() {
    int j = 0;
    F(i, 2, m) {
        while (j and a[j + 1] != a[i]) j = fail[j];
        j += (a[j + 1] == a[i]);
        fail[i] = j;
    }
}
bool ending;
int main() {
    // printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
    n = read(), m = read();
    F(i, 1, m) {
        a[i] = read();
    }
    init();
    int t = n;
    F(i, 1, m) {
        a[i] = a[fail[i]] + t;
        if (a[i] >= mod) a[i] -= mod;
        t = 1ll * t * n % mod;
        printf("%d\n", a[i]);
    }
    return 0;
}
inline int read() {
    reg int x = 0;
    reg bool f = 1;
    reg char c = getchar();
    while (!isdigit(c)) {
        f = c ^ 45;
        c = getchar();
    }
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? x : -x;
}

特别鸣谢

Macesuted 提供优化思路。/bx

Odalys @ 2022-2-27 9:30:03

第一种情况的dp柿子是不是写错了啊
Odalys @ 2022-2-27 9:37:08

@ 哦没事了，我看错了

Macesuted QWQ LV 10 SU @ 2021-9-9 7:25:42

#002 2021.9.9

Ynoi2008 stcm

题目大意

给出一棵 $n$ 个点的树，需要你构建一个操作序列使得树上每一个结点均被标记一次，操作序列由下面三种操作构成：

+x：向当前集合中插入 $x$ 号点。
-：撤销上一次插入操作。
=x：确定当前集合为 $x$ 号点的子树补集并标记 $x$ 。

$x$ 号点子树补集的定义为 $x$ 号点子树构成的点集在整棵树点集中的补集。

题意可能较难理解，也不是非常容易以较简单的方式字面描述，如果你还是不理解可以手推一下样例。

每个测试点有 $T$ 组测试数据。

$n \le 10^5,~T \le 3,$ +x 操作数量 $\le 4.5 \times 10^6$

题解

分析

观察限制的 +x 操作数量大约在 $O(n \log n)$ 级别，容易想到对树进行重链剖分，然后依次处理每一条重链。

我们发现如果当前集合为 $p$ 点的子树补集且 $p$ 为其所在重链的顶端，我们可以用 $O(siz[p])$ 的操作标记 $p$ 所在重链上的所有点：假设 $p$ 重链上的点从上到下为 $x_1,~x_2,~x_3,\dots$ ，我们可以先标记 $x_1$ ，然后将 $x_1$ 和 $x_1$ 的所有轻儿子为根的子树加入集合，然后标记 $x_2$ ，再将 $x_2$ 和 $x_2$ 的所有轻儿子为根的子树加入集合，以此类推，最终可以 $O(siz[p])$ 标记该重链上的所有点。全局花在该操作上的次数为 $O(n \log n)$ 级别，证明类似 dsu on tree。

我们现在已经可以处理一条重链上的信息了，接下来我们要考虑如何完成重链间的切换。为完成重链间的切换，我们显然是枚举 $p$ 所在重链的所有节点的所有轻儿子，然后考虑将当前集合变为该轻儿子的子树补集然后递归处理该轻儿子所在重链信息。考虑如何在较小的操作步数中将所有轻儿子的子树补集都构造一次。

考虑极端情况，即整棵树为一个菊花图的情况，考虑如何构造方案。稍微尝试一些方法后会发现最优策略为你构造一个类似线段树的结构，然后你从线段树根开始遍历这个线段树：

如果当前节点为叶子节点，标记该节点并跳过下面的步骤并回溯。
将当前节点右儿子对应区间内的所有节点加入集合。
递归处理左儿子。
撤销 2 步骤中的插入操作。
将当前节点左二子对应区间内的所有节点加入集合。
递归处理右儿子。
撤销 5 步骤中的插入操作。

容易发现该方法可以用 $O(n \log n)$ 此操作标记所有的点，因为每一个点一共被操作的次数等于其祖先数量。

我们同样可以使用该方法处理我们的轻儿子的问题。我们可以先将重链上的所有节点加入集合，然后将每个轻儿子视为一个点，对所有的轻儿子构建一棵线段树，然后在线段树上从根开始递归处理，到叶子结点时将原本的“标记该结点”换为“递归处理该节点所在的重链”。

但是容易发现这样的方法并不能保证操作次数复杂度一定正确，因为修改每一个轻儿子的花费是 $siz[\text{轻儿子}]$ 而不是 $1$ 。考虑这棵线段树上的总操作数是等于 $\sum_{i \in \text{叶子节点}} siz[i] \times dep[i]$ ，我们想要最小化它的值。这时我们发现哈夫曼树正好就是在最小化这个值，所以我们将“构造线段树”换为“构造哈夫曼树”就可以使该操作复杂度成为 $O(siz[p] \log siz[p])$ ，递归方法不变。与处理重链时的复杂度证明相似，可以发现全局花在这一操作上的总操作次数为 $O(n \log n)$ 。

总操作次数 $O(n \log n)$ 。

代码

/**
 * @author Macesuted (macesuted@outlook.com)
 * @copyright Copyright (c) 2021
 * @brief
 *      My tutorial: https://macesuted.cn/article/h1031/
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    queue<char> que;
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch();
    string s;
    s.resize(que.size());
    for (register int i = 0; i < s.size(); i++) s[i] = que.front(), que.pop();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (register int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
inline T read() {
    register T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
inline void write(const T& t) {
    register T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 100005

vector<vector<int> > graph;

int siz[maxn], son[maxn];

void insert(int p) {
    putch('+'), write(p);
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) insert(*i);
    return;
}
void erase(int p) {
    for (register int i = 1; i <= siz[p]; i++) putch('-');
    return;
}

class HuffmanTree {
   public:
    struct Node {
        int id, siz;
        Node *l, *r;
        Node(int _id = 0) { siz = ::siz[id = _id], l = r = NULL; }
    };

    typedef pair<int, Node*> pin;

    Node* root;

    void destroy(Node* p) {
        if (p == NULL) return;
        if (p->l != NULL) destroy(p->l);
        if (p->r != NULL) destroy(p->r);
        delete p;
    }

    HuffmanTree(void) { root = NULL; }
    ~HuffmanTree(void) { destroy(root); }
    void build(const vector<int>& sons) {
        static priority_queue<pin, vector<pin>, greater<pin> > que;
        while (!que.empty()) que.pop();
        for (vector<int>::const_iterator i = sons.cbegin(); i != sons.cend(); i++) {
            Node* p = new Node(*i);
            que.push((pin){siz[*i], p});
        }
        while (que.size() > 1) {
            Node* l = que.top().second;
            que.pop();
            Node* r = que.top().second;
            que.pop();
            Node* p = new Node();
            p->l = l, p->r = r;
            p->siz = l->siz + r->siz;
            que.push((pin){p->siz, p});
        }
        root = que.top().second, que.pop();
        return;
    }
    void insert(Node* p) {
        if (p == NULL) return;
        if (p->id) return ::insert(p->id);
        if (p->l != NULL) insert(p->l);
        if (p->r != NULL) insert(p->r);
        return;
    }
    void erase(Node* p) {
        if (p == NULL) return;
        if (p->id) return ::erase(p->id);
        if (p->l != NULL) erase(p->l);
        if (p->r != NULL) erase(p->r);
        return;
    }
};

void dfs1(int p) {
    siz[p] = 1, son[p] = 0;
    for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) {
        dfs1(*i);
        siz[p] += siz[*i];
        if (son[p] == 0 || siz[*i] > siz[son[p]]) son[p] = *i;
    }
    return;
}
void dfs3(HuffmanTree&, HuffmanTree::Node*);
void dfs2(int p) {
    vector<int> chain, sons;
    chain.clear(), sons.clear();
    int x = p;
    while (x) chain.push_back(x), x = son[x];
    for (vector<int>::iterator i = chain.begin(); i != chain.end(); i++) {
        putch('='), write(*i), putch('+'), write(*i);
        for (vector<int>::iterator j = graph[*i].begin(); j != graph[*i].end(); j++)
            if (*j != son[*i]) sons.push_back(*j), insert(*j);
    }
    for (vector<int>::reverse_iterator i = sons.rbegin(); i != sons.rend(); i++) erase(*i);
    for (vector<int>::reverse_iterator i = chain.rbegin(); i != chain.rend(); i++) putch('-');
    for (vector<int>::iterator i = chain.begin(); i != chain.end(); i++) putch('+'), write(*i);
    if (!sons.empty()) {
        HuffmanTree tree;
        tree.build(sons);
        dfs3(tree, tree.root);
    }
    for (vector<int>::reverse_iterator i = chain.rbegin(); i != chain.rend(); i++) putch('-');
    return;
}
void dfs3(HuffmanTree& tree, HuffmanTree::Node* p) {
    if (p == NULL) return;
    if (p->id) return dfs2(p->id);
    tree.insert(p->r);
    if (p->l != NULL) dfs3(tree, p->l);
    tree.erase(p->r);
    tree.insert(p->l);
    if (p->l != NULL) dfs3(tree, p->r);
    tree.erase(p->l);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin >> n) {
        graph.resize(n + 1);
        for (register int i = 2, fa; i <= n; i++) cin >> fa, graph[fa].push_back(i);
        dfs1(1), dfs2(1);
        putch('!'), putch('\n');
        graph.clear();
    }
    return 0;
}

创造君核反应堆 LV 8 @ 2021-9-12 9:09:57

用 class+public: 是为了让别人看不懂么……
创造君核反应堆 LV 8 @ 2021-9-12 9:10:45

@创造君: （而不用 struct)
Rratic LV 5 @ 2021-9-13 20:46:18

@创造君: 比如我，就喜欢用class（逃

Maplisky 枫 LV 10 @ 2021-9-3 15:13:19

#001 2021.9.3

[COCI2018-2019 Final T4] TENIS

题解

Analysis

思维题。

拿到题目首先观察样例。

针对第二个事件，我们发现，虽然在前两个场地 $4$ 都是最弱的，但是在第三个场地 $4$ 能打赢 $1$ 和 $3$ ，而在第一个场地 $1$ 又能打赢 $2$ 。因此只需让能被选手 $4$ 打败的人先去打选手 $4$ 打不过的人，选手 $4$ 才有可能获得胜利。

将以上策略抽象成图，将每一个人视为一个结点，向每个他能打败的人（不管在哪个场地）都连一条边，那么询问就是看从这个人的结点出发，能否遍历其他所有结点。如下图：

（此处 $1.1,1.2,1.3$ 为选手 $1$ 在三个场地的排名，在这种方法中可缩为一个点）

这时处理询问的复杂度为 $\mathcal{O}(n)$ ，总时间复杂度为 $\mathcal{O}(n\times Q)$ ，期望得分 $30$ 分。

我们发现问题的瓶颈在于处理询问，而上述处理方法基于连向其他结点的边。为方便观察，先将这些边删去。~~我们来随手搓一组。~~

将同一个选手在三个场地的位置用边连接，如下图：

此时选手 $1$ 、选手 $2$ 、选手 $4$ 可能获胜。

可以发现，能获胜的选手和不能获胜的选手中间有一道明显的分隔线。这条分割线满足：没有一条边横跨分割线。这时在分割线左边的选手能获胜，右边的则不能。

然而随手一组就 Hack 掉了。比如：

在这组中有多条满足要求的分割线，怎么办？显然只有最左边的是正确的。考虑维护最左边的分割线。

为什么这样是正确的？考虑分割线左边选手的情况。显然左边的选手可以直接或间接打败在左边的其他选手。假设某一个选手不能打败左边的其他选手，那么这条分割线一定可以向左移动，把这个选手排除在外。那么这样就不满足最左边的分割线这一前提条件。因此假设不成立。

基于以上事实，分割线左边的选手必定可以直接或间接打败其他选手。同样的，分割线右边的选手不可能直接或间接打败左边的全部选手。（同样可以反证）

这条线如何维护呢？我们记数组 $p$ ， $p_i$ 表示有 $p_i$ 个选手的边没有跨过 $i$ 。记第 $i$ 位选手的在第 $j$ 个场地的排名为 $d_{i,j}(1\le j\le 3)$ ，那么对于这名选手来说，他的边不会跨过 $\max(d_{i,j})\to n~(1\le j\le 3)$ ，体现在 $p$ 数组上即对 $p_i \to p_n$ 区间加 $1$ 。

最后， $p$ 何时满足条件？根据 $p_i$ 的定义可知，若 $p_i=i$ ，则此处有一条分割线。找最左边的一条即可。

总结上文，需要支持的操作有：

区间加。
区间查询。

用线段树维护即可。时间复杂度 $\mathcal{O}(Q \log n)$ 。

tips：线段树叶节点可以赋初值 $-l$ ，其中 $l$ 为结点代表的范围。在每个结点里记最大值。查询时树上二分，若左子树最大值为 $0$ ，查左子树，否则查右子树。

code

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define _max(a,b) ((a)>(b)?(a):(b))
#define Max(x,y,z) ((x)>(y)?_max((x),(z)):_max((y),(z)))
#define _Max(x) Max(d[1][x],d[2][x],d[3][x])
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
using namespace std;
bool beginning;
inline int read();
const int N=1e5+5;
int n,q,d[4][N],Ans;
struct P {
	int l,r,Mx,lz;
} f[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r) {
	f[x].l=l,f[x].r=r;
	if(l==r) {
		f[x].Mx=-l;
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	f[x].Mx=_max(f[ls].Mx,f[rs].Mx);
}
inline void push_down(int x) {
	if(!f[x].lz)return;
	f[ls].lz+=f[x].lz,f[rs].lz+=f[x].lz;
	f[ls].Mx+=f[x].lz,f[rs].Mx+=f[x].lz;
	f[x].lz=0;
}
void modify(int x,int l,int r,int val) {
	if(l<=f[x].l and f[x].r<=r) {
		f[x].lz+=val,f[x].Mx+=val;
		return;
	}
	push_down(x);
	int mid=f[x].l+f[x].r>>1;
	if(l<=mid)modify(ls,l,r,val);
	if(r>mid)modify(rs,l,r,val);
	f[x].Mx=_max(f[ls].Mx,f[rs].Mx);
}
int query(int x,int l,int r) {
	if(l==r)return l;
	int mid=l+r>>1;
	push_down(x);
	if(!f[ls].Mx)return query(ls,l,mid);
	return query(rs,mid+1,r);
}
bool ending;
int main() {
//  printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
	n=read(),q=read();
	build(1,1,n);
	F(i,1,3)F(j,1,n)d[i][read()]=j;//记排名 
	F(i,1,n)modify(1,_Max(i),n,1);//将初始结点插入答案 
	Ans=query(1,1,n);//记录分割线 
	reg int op,x,y,z;
	while(q--) {
		op=read();
		if(op==1) {
			x=read();
			puts(d[1][x]<=Ans?"DA":"NE");
		} else if(op==2) {
			z=read(),x=read(),y=read();
			modify(1,_Max(x),n,-1);
			modify(1,_Max(y),n,-1);
			swap(d[z][x],d[z][y]);
			modify(1,_Max(x),n,1);
			modify(1,_Max(y),n,1);
			Ans=query(1,1,n);
		}
	}
	return 0;
}
inline int read() {
	reg int x=0;
	reg char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}

youyukyc LV 6 @ 2021-9-5 18:18:34

%%%STO
CnuhXuyaen LV 8 @ 2021-9-8 20:49:13

把题解放下面一点吧，一打开讨论就看到了做法

HydroOJ 每日一题

42 条评论

#017 2022.3.15

题意

分析

代码

#016 2022.3.12

题意

分析

代码

#015 2022.3.4

题意

分析

代码

#014 2022.2.24

题意

分析

代码

#013 2022.2.23

题目大意

分析

代码

#012 2022.2.22

题目大意

1. 静态 xor 最短路

2. 考虑动态加边删边做这个东西：

code

#011 2022.2.1

题目大意

分析

代码

#010 2022.1.30

题目大意

分析

代码

#009 2022.1.29

题目大意

分析

代码

#008 2022.1.28

题目大意

分析

代码

#007 2021.11.4

题目大意

Analysis

Q1：是否存在一种情况，使得不能将一条边改为独有的颜色？

Q2：一条边会不会被重复改变颜色？

Q3：何时无法到达？

Code:

#006 2021.10.10

题目大意

分析

代码

#005 2021.9.25

题意

分析

代码

#004 2021.9.18

题意简述

Analysis

code

#003 2021.9.17

题意简述

Declare

Analysis

code

特别鸣谢

#002 2021.9.9

题目大意

分析

代码

#001 2021.9.3

Analysis

code

状态

开发

支持

还没有账户？

登录