2024年10月4日

2024/09 做题笔记

不行了，语言开始变机械化了 TAT

还有几道题没写完

文章目录

1 [POI2015] PUS / Pustynia
2 [SDOI2014] 旅行
3 [POI2015] ODW / Odwiedziny
4 [ICPC2020 Shanghai R] Sum of Log
5 [APIO2016] 划艇
6 untitled
7 untitled

[POI2015] PUS / Pustynia

给定一个长度为 $n$ 的正整数序列 $a$ ，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数 $t_i$ ，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。

请任意构造出一组满足条件的方案，或者判断无解。

如果抛开区间连边的条件不谈，那么这道题应该就是一个简单的拓扑排序。最最暴力的做法是 $O(n^3)$ 的，即每条边都暴力连接。然后有一个看起来比较常用的技巧，对于每一个约束建立一个超级源点 $s$ ，于是就有 $t_{\tt1..=k} \to s \to {\rm others}$ ，可以把边数和时间复杂度降低到 $O(n^2)$ 级别的。但是这样还不足以通过这道题。

思考对区间连边进行优化：可以采用像本文提到的优化方法优化建图。

然后时间复杂度降低到了大概线对级别。可以通过这道题。

#define revoid(f...) ({ f; return; })
using namespace std;

const int MAXN = 5e5 + 5, MAXV = 1e9;
int dat[MAXN], n, qu;

int ndcnt, deg[MAXN * 3], raw[MAXN];
char vis[MAXN * 3];
vector<int> pat;

vector<pair<int, int>> g[MAXN * 3];
int maxp = 0;
int nd[MAXN];

inline void add_edge(int u, int v, int w)
{
    deg[v]++;
    g[u].push_back({ v, w });
}

void build(int l, int r, int p = 1)
{
    maxp = max(maxp, p);
    if (l == r) revoid(nd[l] = p);
    int mid = (l + r) >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    add_edge(p, p << 1, 0);
    add_edge(p, p << 1 | 1, 0);
}

inline void add_r(int u, int l, int r, int ml = 1, int mr = n, int p = 1)
{
    if (l > r) return;
    if (l > mr || r < ml) return;
    if (l <= ml && mr <= r) return add_edge(u, p, 1);
    int mid = (ml + mr) >> 1;
    add_r(u, l, r, ml, mid, p << 1);
    add_r(u, l, r, mid + 1, mr, p << 1 | 1);
}

inline bool topo()
{
    queue<int> q;
    for (int i = 1; i <= maxp; i++) {
        if (!deg[i]) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = 1;
        for (auto e : g[u]) {
            int v = e.first, w = e.second;
            if (dat[u] - w < max(raw[v], 1)) return false;
            dat[v] = min(dat[v], dat[u] - w);
            if (!--deg[v]) q.push(v);
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int s;
    cin >> n >> s >> qu;
    build(1, n);
    for (int i = 1; i <= s; i++) {
        int pos, val;
        cin >> pos >> val;
        raw[nd[pos]] = dat[nd[pos]] = val;
    }
    for (int qi = 1; qi <= qu; qi++) {
        int l, r, k, tp;
        int from = ++maxp;
        cin >> l >> r >> k;
        int last = l;
        for (int i = 1; i <= k; i++) {
            cin >> tp;
            add_edge(nd[tp], from, 0);
            add_r(from, last, tp - 1);
            last = tp + 1;
        }
        add_r(from, last, r);
    }
    for (int i = 1; i <= maxp; i++) if (!dat[i]) dat[i] = MAXV;
    if (!topo()) {
        cout << "NIE\n";
        return 0;
    }
    for (int i = 1; i <= maxp; i++) {
        if (deg[i]) {
            cout << "NIE\n";
            return 0;
        }
    }
    cout << "TAK\n";
    for (int i = 1; i <= n; i++) cout << dat[nd[i]] << ' ';
}

[SDOI2014] 旅行

Luogu | LOJ

一个国家由 $N$ 个城市组成树状结构，每个城市有宗教和评级。居民旅行时只在宗教相同的城市间移动，需处理四种操作：

CC x c：城市 $x$ 的宗教改为 $c$ ；
CW x w：城市 $x$ 的评级改为 $w$ ；
QS x y：查询从城市 $x$ 到城市 $y$ 的路径上，信仰与 $x$ 相同的城市的评级总和；
QM x y：查询从城市 $x$ 到城市 $y$ 的路径上，信仰与 $x$ 相同的城市的评级最大值。

输入包括初始城市的宗教和评级信息及操作记录，要求根据这些数据还原并输出所有查询的结果。

数据规模： $N, Q \leq 10^5$ 。宗教数量 $\le 10^5$ 。

树剖，然后可以开 $N$ 个线段树但是空间会爆炸！所以这个时候可以换一个思路，写动态开点线段树去优化空间。

单点修改非常简单。具体来说，当城市的评级从 $x$ 改为 $y$ 的时候，在原有的表示宗教 $x$ 的树上删除这个城市（设置为 $0$ ）然后在 $y$ 树上新建这个节点。

查询就更简单了。

#define panic(msg) \
{\
    throw (struct: exception { \
        const char* what() const noexcept override { return "program panicked with message: " msg; } \
    }){};\
}
typedef int ll;
using namespace std;

int n, q;
const int MAXN = 100000 + 5;
vector<int> g[MAXN];

int top[MAXN], fa[MAXN], sz[MAXN], hvson[MAXN], dep[MAXN], dfn[MAXN];
int tru[MAXN], wei[MAXN];
int cnt;

struct DynamicSeg {
    struct Node {
        int lson, rson; ll val, mx;
    } tr[28 * MAXN];

    int rt[MAXN], nid;
    queue<int> buf;

    void update(int id, int x, int val, int l = 1, int r = n, int p = -1)
    {
        if (rt[id] == 0) p = rt[id] = ++nid;
        else if (p == -1) p = rt[id];
        if (l > x || r < x) return;
        if (l == r && l == x) {
            tr[p].val = tr[p].mx = val;
            return;
        }
        int lson = tr[p].lson != 0 ? tr[p].lson : tr[p].lson = ++nid;
        int rson = tr[p].rson != 0 ? tr[p].rson : tr[p].rson = ++nid;
        int mid = (l + r) >> 1;
        update(id, x, val, l, mid, tr[p].lson);
        update(id, x, val, mid + 1, r, tr[p].rson);
        tr[p].val = tr[lson].val + tr[rson].val;
        tr[p].mx = max(tr[lson].mx, tr[rson].mx);
    }

    ll query(int id, int ql, int qr, int l = 1, int r = n, int p = -1)
    {
        if (p == -1) p = rt[id];
        if (p == 0) return 0;
        if (l > qr || r < ql) return 0;
        if (ql <= l && r <= qr) return tr[p].val;
        int mid = (l + r) >> 1;
        return
            query(id, ql, qr, l, mid, tr[p].lson) +
            query(id, ql, qr, mid + 1, r, tr[p].rson);
    }

    ll query_max(int id, int ql, int qr, int l = 1, int r = n, int p = -1)
    {
        if (p == -1) p = rt[id];
        if (p == 0) return 0;
        if (l > qr || r < ql) return 0;
        if (ql <= l && r <= qr) return tr[p].mx; 
        int mid = (l + r) >> 1;
        return max(
            query_max(id, ql, qr, l, mid, tr[p].lson),
            query_max(id, ql, qr, mid + 1, r, tr[p].rson)
        );
    }
} tr;

void dfs1(int u, int _fa = -1)
{
    sz[u] = 1;
    fa[u] = _fa;
    for (const int v : g[u]) {
        if (v == _fa) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[hvson[u]]) hvson[u] = v;
    }
}

void dfs2(int u, int ctop)
{
    top[u] = ctop;
    dfn[u] = ++cnt;
    if (!hvson[u]) return;
    dfs2(hvson[u], ctop);
    for (const int v : g[u])
        if (v != fa[u] && v != hvson[u])
            dfs2(v, v);
}

inline ll query_range_sum(int r, int u, int v)
{
    ll ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans += tr.query(r, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans += tr.query(r, dfn[u], dfn[v]);
    return ans;
}

inline ll query_range_max(int r, int u, int v)
{
    ll ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = max(ans, tr.query_max(r, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans = max(ans, tr.query_max(r, dfn[u], dfn[v]));
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    int u, v;
    for (int i = 1; i <= n; i++) {
        cin >> wei[i] >> tru[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    for (int i = 1; i <= n; i++) {
        tr.update(tru[i], dfn[i], wei[i]);
    }
    char opt1, opt2;
    ll a, b;
    while (q--) {
        cin >> opt1 >> opt2 >> a >> b;
        if (opt1 == 'C') {
            if (opt2 == 'C') {
                tr.update(tru[a], dfn[a], 0);
                tr.update(tru[a] = b, dfn[a], wei[a]);
            } else {
                tr.update(tru[a], dfn[a], wei[a] = b);
            }
        } else {
            if (opt2 == 'S') {
                cout << query_range_sum(tru[a], a, b) << '\n';
            } else {
                cout << query_range_max(tru[a], a, b) << '\n';
            }
        }
    }
}

[POI2015] ODW / Odwiedziny

Luogu

给定一棵 $n$ 个点的树，树上每条边的长度都为 $1$ ，第 $i$ 个点的权值为 $a_i$ 。

Byteasar 想要走遍这整棵树，他会按照某个 $1$ 到 $n$ 的全排列 $b$ 走 $n-1$ 次，第 $i$ 次他会从 $b_i$ 点走到 $b_{i + 1}$ 点，并且这一次的步伐大小为 $c_i$ 。

对于一次行走，假设起点为 $x$ ，终点为 $y$ ，步伐为 $k$ ，那么Byteasar会从 $x$ 开始，每步往前走 $k$ 条边，数据保证了每次行走的距离是 $k$ 的倍数。

请帮助 Byteasar 统计出每一次行走时经过的所有点的权值和。

解法简单粗暴，无需动脑。虽然细节很多，但是还是不用动脑，就是可能需要浪费 8h 去调这个神秘东西（x

思路大概就是先进行一个树链剖分（把点权映射到区间），然后分块，预处理出这个块内起点为 $x$ 且单步行走距离为 $k$ 所经过的点权和。如果 $k$ 大于块长的话不需要处理，因为这个时候会直接跳过这个块。分块查询的话，如果没有走完一整个块就直接暴力。查询时间复杂度是 $O(\sqrt{n}\log n)$ 的。

然后想，怎么预处理起点为 $x$ 、步长为 $k$ 的点权和。暴力做是 $O(n^2)$ 的，具体来说就是枚举每个 $k$ （ $\sqrt{n}$ 级别）、 $x$ （ $\sqrt{n}$ 级别），然后 $O(n)$ 的跳。这个时间复杂度肯定不对，所以可以对于每一个 $k$ 从后往前枚举，用后面的值递推出前面的值。即 $dis(x, k) = a_x + dis(x, x + k)$ 。

然后这个题的各种映射关系会把你搞得十分混乱，所以这个要特别注意！！！！细节调死我了！！！QAQ

const int MAXN = 5e4 + 3, MAXB = 250;
int n, wid[MAXN];
int fa[MAXN], dep[MAXN], hvson[MAXN], sz[MAXN], dfn[MAXN], dfni, top[MAXN], id[MAXN];
struct Block {
    int dat[MAXB][MAXB];
    int sz;
} bk[MAXB];
int bkl[MAXB], bkr[MAXB], bkid[MAXN], bksz, bkcnt;
vector<int> tr[MAXN];

int route[MAXN], opt[MAXN];

void dfs1(int u, int _fa = 0)
{
    fa[u] = _fa;
    sz[u] = 1;
    dep[u] = dep[_fa] + 1;
    int maxw = 0;
    for (auto v : tr[u]) if (v != _fa) {
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (maxw < sz[v]) maxw = sz[hvson[u] = v];
    }
}

void dfs2(int u, int ltop = 1)
{
    dfn[u] = --dfni; id[dfni] = u;
    top[u] = ltop;
    if (hvson[u] == 0) return;
    dfs2(hvson[u], ltop);
    for (auto v : tr[u]) if (v != hvson[u] && v != fa[u]) {
        dfs2(v, v);
    }
}

inline pair<int, int> query_bk(int l, int r, int k, int skip)
{
    int lb = bkid[l], rb = bkid[r];
    int ans = 0;
    if (lb == rb) {
        for (int i = l; i <= r; i++) {
            if (skip == 0) {
                ans += opt[i];
                skip = k;
            }
            skip--;
        }
        return { ans, skip };
    }
    for (int i = l; i <= bkr[lb]; i++) {
        if (skip == 0) {
            ans += opt[i];
            skip = k;
        }
        skip--;
    }
    for (int i = lb + 1; i <= rb - 1; i++) {
        if (skip > bk[i].sz) {
            skip -= bk[i].sz;
            continue;
        }
        ans += bk[i].dat[skip + 1][min(k, bk[i].sz)];
        skip = (k - (bk[i].sz - skip) % k) % k;
    }
    for (int i = bkl[rb]; i <= r; i++) {
        if (skip == 0) {
            ans += opt[i];
            skip = k;
        }
        skip--;
    }
    return { ans, skip };
}

inline int query_tree(int u, int v, int k)
{
    int uskip = 0, vskip = 0;
    int ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) {
            auto res = query_bk(dfn[u], dfn[top[u]], k, uskip);
            ans += res.first;
            uskip = res.second;
            u = fa[top[u]];
        } else {
            auto res = query_bk(dfn[v], dfn[top[v]], k, vskip);
            ans += res.first;
            vskip = res.second;
            v = fa[top[v]];
        }
    }
    if (dep[u] < dep[v]) ans += query_bk(dfn[v], dfn[u], k, vskip).first;
    else ans += query_bk(dfn[u], dfn[v], k, uskip).first;

    return ans;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> wid[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tr[u].push_back(v); tr[v].push_back(u);
    }
    dfni = n + 1;
    dfs1(1, 0);
    dfs2(1, 1);

    bksz = sqrt(n) + 1;
    for (int i = 1; i <= n; i++) opt[i] = wid[id[i]];
    for (int i = 1; ; i += bksz) {
        i = min(i, n); ++bkcnt;
        bkl[bkcnt] = i; bkr[bkcnt] = min(n, i + bksz - 1);
        const int bsz = bkr[bkcnt] - bkl[bkcnt] + 1;
        for (int len = bsz; len >= 1; len--) {
            for (int start = bsz; start >= 1; start--) {
                bk[bkcnt].dat[start][len] =
                    (start + len <= bsz ? bk[bkcnt].dat[start + len][len] : 0) +
                    opt[bkl[bkcnt] + start - 1];
            }
        }
        for (int j = i; j <= bkr[bkcnt]; j++) bkid[j] = bkcnt;
        bk[bkcnt].sz = bsz;
        if (i == n || bkr[bkcnt] == n) break;
    }
    for (int i = 1; i <= n; i++) cin >> route[i];
    for (int i = 1; i < n; i++) {
        int w;
        cin >> w;
        cout << query_tree(route[i], route[i + 1], w) << '\n';
    }
}

[ICPC2020 Shanghai R] Sum of Log

Luogu

计算

$\sum\limits_{i=0}^{X}{\sum\limits_{j=[i=0]}^{Y}{[i \& j=0]\lfloor \log_2(i+j)+1\rfloor}}$

& = 按位与
$X, Y$ 值域 1e9，多测 1e5。

这个数据范围看起来像是数位 DP。条件是 $i$ 和 $j$ 按位与为零，即 $i$ 和 $j$ 没有共同的位同时为 1。那么有 $i+j = i\operatorname{bitor}j$ ， $\lfloor \log_2(i+j)+1\rfloor$ 为 $\max(i,j)$ 的最高位数。然后你可以枚举式子右边的值，看起来会比较好做。

思考一下会有哪些状态。肯定有当前枚举到了第 $k$ 位、 $i$ 是否接触 $X$ 的上界、 $j$ 是否接触 $Y$ 的上界；然后还需要考虑当前数字是否为 0。即 $f(k, 0/1, 0/1, 0/1)$ 为满足（刚才说的）状态限制的方案数。

记得减去 $(0, 0)$ 的情况！

int f[32][2][2][2], limx[32], limy[32];

int dfs(int pos, int nlimx, int nlimy, int pre)
{
    if (!pos) return 1;
    if (f[pos][nlimx][nlimy][pre] != -1) return f[pos][nlimx][nlimy][pre];
    long long res = 0;
    int lix = nlimx ? limx[pos] : 1;
    int liy = nlimy ? limy[pos] : 1;
    for (int i = 0; i <= lix; i++) {
        for (int j = 0; j <= liy; j++) {
            // 不需要计算这位的贡献
            if (i & j) continue;
            int s = pre && (i || j) ? pos : 1;
            (res += 1ll * s * dfs(pos - 1, nlimx && i == lix, nlimy && j == liy, pre && !i && !j) % MODN) %= MODN;
        }
    }
    return f[pos][nlimx][nlimy][pre] = res;
}

inline void solve()
{
    int x, y;
    cin >> x >> y;
    for (int i = 1; i <= 31; i++) (limx[i] = x & 1), x >>= 1;
    for (int i = 1; i <= 31; i++) (limy[i] = y & 1), y >>= 1;
    memset(f, -1, sizeof f);
    cout << ((dfs(31, 1, 1, 1) - 1) % MODN + MODN) % MODN << '\n';
}

[APIO2016] 划艇

Luogu

手玩一下数据可以发现，如果我们钦定第 $i$ 个学校选择 $j$ 个游艇，暴力计算公式有：

$f(i,j)=\prod_{k=i-1}^{i}(\max(0, \min(j-1,b_k)-a_k+1)+1)$

如果暴力枚举 $i$ 和 $j$ ，发现这东西连最基本的部分分都拿不到。然后一开始想的是从 $1\to n$ 开始，枚举区间，但是后面假了。死因：没有注意到逆序对的性质而想当然地直接去用区间长度乘上区间最高点的暴力答案。（calc(i, j) = f(i, j)）；即 P3643 [APIO2016]划艇 by Alex_Wei 提到的错误思路 ~~虽然似乎并不是一个思路但是很类似就是了~~

// 很神秘的假做法。
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        auto beg = rg.insert(a[i]).first;
        auto end = rg.insert(b[i] + 1).first;
        do {
            int last = *beg;
            beg++;
            int delta = calc(i, *beg - 1);
            ans = add(ans, mul(*beg - last, delta));
        } while (beg != end);
    }
    cout << ans << '\n';
}

之后看题解看到一个结论：从区间 $[0, L]$ 选 $n$ 个数，要求非零数严格递增，方案数为 ${L+n\choose n}$ 。

~~后面发现想到这里已经开始和正解靠近了~~

于是从头开始想。发现，方案数，这个东西是可以转移的。令 $f(i, 0) = 1$ ，有

$f(i,j)=\sum_{k=1}^{i-1} \sum_{l=0}^{j-1} [\text{school {\it k} contains {\it l} }] f(k,l)$

考虑按照上面的思路去对区间进行转移。

令 $f(i, 0) = 1$ 。于是有：

$f(i,j)=\sum_{k=1}^{i-1} \sum_{l=0}^{j-1} [\text{school {\it k} contains range {\it l} }] {{\rm len}_l + m – 1 \choose m} f(k, l)$

其中 $m$ 为当前项及其之前包含区间 $l$ 的学校的个数。直接这么做是 $O(n^4)$ 的，但是可以发现 $f(i, j)$ 可以进行前缀和优化。然后组合数可以递推：

${{\rm len}_l + m \choose m + 1} = {{\rm len}_l + m – 1 \choose m} \times \frac{{\rm len}_l + m}{m + 1}$

然后想怎么实现。

发现 len 可能会比较大，但是这个递推一下就会好很多。所以可以先去枚举区间。

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    inv[0] = 1;
    for (int i = 1; i < MAXN; i++) inv[i] = fastpow(i, MODN - 2);

    cin >> n;
    vector<int> ls;
    ls.reserve(2 * n + 1);
    ls.push_back(-1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ls.push_back(a[i]);
        // [)
        ls.push_back(++b[i]);
    }
    sort(ls.begin(), ls.end()); ls.erase(unique(ls.begin(), ls.end()), ls.end());
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(ls.begin(), ls.end(), a[i]) - ls.begin();
        b[i] = lower_bound(ls.begin(), ls.end(), b[i]) - ls.begin();
    }

    f[0] = c[0] = 1;
    int cnt = ls.size();
    cnt--;

    for (int j = 2; j <= cnt; j++) {
        int len = ls[j] - ls[j - 1];
        for (int i = 1; i <= n; i++) {
            c[i] = mul(c[i - 1], len + i - 1, inv[i]);
        }
        for (int i = n; i >= 1; i--) {
            if (a[i] < j && j <= b[i]) {
                for (int k = i - 1, m = 1; k >= 0; k--) {
                    f[i] = add(f[i], mul(f[k], c[m]));
                    if (a[k] < j && j <= b[k]) m++;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = add(ans, f[i]);
    }
    cout << ans << '\n';
}

untitled

给你一个 $n\times n$ 的矩阵，每个格子有一个权值，让你求对于所有格子，以这个格子为左上角的最大正方形且其内部不超过 $k$ 中不同权值。

很神秘，暴力前缀和然后二分都能过（就是写了个循环展开）。

核心代码：

*--upper_bound(erfe.begin(), erfe.end() - max(i, j) + 1, k, [i, j](int k, int pos) {
    return k < ask(i, j, i + pos - 1, j + pos - 1);
});

untitled

一个有 $n$ 个点和 $m$ 条单向道路的 DAG。要求找到一个点，使得从图中删除该点后，剩余图中的最长路径尽可能短，并返回该最短路径的长度以及对应的观测点编号（若有多个，选编号最小的）。边权为 1。

求最长路，考虑拓扑排序。对于一条边 $u\to v$ 而言，如果一条路径经过这一条边，那么删除拓扑序在 $(ord_u, ord_v)$ （注意是开区间）之间的点不影响这条路径的长度。拓扑序的性质决定了在有向无环图中，如果边 $u \to v$ 存在，则 $u$ 的拓扑序必然小于 $v$ 的拓扑序，即 $ord_u \lt ord_v$ 。因此，如果一条路径必须经过边 $u \to v$ ，那么经过这条边的路径上的其他节点的拓扑序要么在 $ord_u$ 之前，要么在 $ord_v$ 之后。

这就意味着，我们可以钦定这条边被保留，随意删除 $(ord_u, ord_v)$ 之间的点也不会出现长度改变的情况。接下来我们需要知道的是通过这条边的最长路。这个时候维护一个超级源点（图可能不是弱连通的）到每个节点的最长路径、每个节点到超级汇点的最长路径，那么这个路径就是 $s \to u \to v \to t$ ，即 $dis_{s\to u} + dis_{v\to t} + 1$ 。

如果我们想要知道删除哪个点是最满足条件的，可以使用一个线段树维护拓扑序上面的区间最长路最值，具体来说，对于每条边都算出经过他的最长路，这意味着如果保留 $u \to v$ ，则 $(ord_u, ord_v)$ 之间的任意一个点删去都不影响最长路，于是对 $(ord_u, ord_v)$ 赋上这个最长路。最后只需要查询删去哪个点的时候最长路最短就好了。

s = 0, t = n + 1;
for (int i = 1; i <= n; i++) {
    G[s].push_back(i), G[i].push_back(t);
}
for (int i = 1; i <= n; i++) {
    rg[t].push_back(i), rg[i].push_back(s);
}
calc(G, dist_s, ord);
calc(rg, dist_t);
sg.build(1, n + 1);
for (int u = 0; u <= n + 1; u++) {
    for (auto v : G[u]) {
        sg.chmax(ord[u] + 1, ord[v] - 1, dist_s[u] + 1 + dist_t[v]);
    }
}
int resl = 1e9, resi = 0;
for (int i = 1; i <= n; i++) {
    int t = sg.find_min(ord[i]);
    if (t < resl) {
        resl = t;
        resi = i;
    }
}

2024/09 做题笔记

[POI2015] PUS / Pustynia

[SDOI2014] 旅行

[POI2015] ODW / Odwiedziny

[ICPC2020 Shanghai R] Sum of Log

[APIO2016] 划艇

untitled

untitled

发表回复 取消回复

发表回复取消回复