Znzryb's Blog

2025-ICPC-Asia-Taiwan-Online-台湾网络赛-C. One-Way Abyss（注意题目中的必须移动）

Posted on 2026-02-02 Edited on 2026-04-06

题目大意

Mitty是一位勇敢的冒险者，正在探索一个被称为深渊的神秘地下洞穴系统。深渊由 $n$ 个平行垂直井和 $m$ 个水平隧道组成。每条隧道恰好连接两个相同深度的井。所有 $m$ 个隧道的深度各不相同，令人惊讶的是，每条隧道的中间都藏有一宝藏！

Mitty可以选择任意一个井开始。他从所选井的顶部向下移动，遵守以下规则：

他只能向下移动，不允许向上移动。
每当他遇到水平隧道时，必须立即进入，并将到达连接的井。
一旦他进入水平隧道，就不能回头。

这些隧道中的宝藏有各种价值。Mitty想要尽可能多地收集宝藏。请帮助他计算从一个井开始时他可以收集到的最大总宝藏价值。

最大样例的示例图：

思路讲解

可以把两个值绑在一起，当然三个，四个也是可以的。

注意，由于必须移动，因此不能够去 max。

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> dp(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        tie(dp[u],dp[v])=(pair<ll,ll>){dp[v]+w,dp[u]+w};
    }
    ll ans=*max_element(all(dp));
    cout<<ans<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106084/submission/361088193

源代码

/**
 * Problem: C. One-Way Abyss
 * Contest: 2025 ICPC Asia Taiwan Online Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106084/problem/C
 * Created: 2026-02-02 13:59:00
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> dp(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        tie(dp[u],dp[v])=(pair<ll,ll>){dp[v]+w,dp[u]+w};
    }
    ll ans=*max_element(all(dp));
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106084/submission/361088193

*/

心路历程（WA，TLE，MLE……）

2025-ICPC-Asia-Taiwan-Online-台湾网络赛-D. Palindromic Distance（字符串与回文串之间的最短距离）（不要那么死板，dp 的转移顺序是可以变的）

Posted on 2026-02-02 Edited on 2026-04-06

题目大意

两个字符串 $u$ 和 $v$ 之间的编辑距离是将 $u$ 转换为 $v$ 的最小编辑操作次数。可以对字符串应用三种编辑操作：插入字符，删除字符，用不同字符替换某个字符。

例如，我们可以用四次替换将hello转换为world，因此编辑距离最多为 $4$ 。您可以用两次替换和一次插入将wally转换为walter，因此编辑距离最多为 $3$ 。计算两个字符串之间的编辑距离是一个众所周知的问题，有许多应用。

当前任务是计算一个字符串到最接近的回文串的编辑距离。回文串是从后往前读和从前往后读相同的字符串，例如madam。

hello到最接近回文串的编辑距离仅为 $2$ ：我们可以用两次编辑操作将hello转换为ollo，或hllh，或elle。

编写一个程序，可以找到一个单词到最接近回文串的距离。

思路讲解

auto dfs=[&](auto && self,ll l,ll r) -> ll {
    if (r==l) {
        return 0;
    }
    if (r-l==1) {
        return s[l]!=s[r];
    }
    if (dp[l][r]!=INF) {
        return dp[l][r];
    }
    dp[l][r]=min({self(self,l+1,r-1)+(s[l]!=s[r]),      // 替换
        self(self,l,r-1)+1,     // 删除右侧（等价于左侧插入一个相同的抵消）
        self(self,l+1,r)+1,     // 删除左侧（等价于在右侧插入一个相同的）
    });
    return dp[l][r];
};

AC代码

AC
https://codeforces.com/gym/106084/submission/361098919

源代码

/**
 * Problem: D. Palindromic Distance
 * Contest: 2025 ICPC Asia Taiwan Online Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106084/problem/D
 * Created: 2026-02-02 14:13:18
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
bool check(const string &s) {
    ll sz=s.size();
    for (int i=0;i<sz;++i) {
        if (s[i]!=s[sz-i-1]) {
            return false;
        }
    }
    return true;
}
void Solve() {
    string s;
    cin>>s;
    if (check(s)) {
        cout<<0<<"\n";
        return;
    }
    ll N=s.size();
    s.insert(s.begin(),'#');
    vector dp(N+2,vector<ll>(N+2,INF));
    auto dfs=[&](auto && self,ll l,ll r) -> ll {
#ifdef LOCAL
        assert(r>=l);
#endif
        if (r==l) {
            return 0;
        }
        if (r-l==1) {
            return s[l]!=s[r];
        }
        if (dp[l][r]!=INF) {
            return dp[l][r];
        }
        dp[l][r]=min({self(self,l+1,r-1)+(s[l]!=s[r]),
            self(self,l,r-1)+1,
            self(self,l+1,r)+1,
        });
        return dp[l][r];
    };
    ll ans=dfs(dfs,1,N);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106084/submission/361098919

*/

心路历程（WA，TLE，MLE……）

CF-1063-B. Siga ta Kymata（如果说一道题目限制操作次数，比如说 5 次，那么大概率，有一种策略，可以在 5 次内对大多数情况操作成功）

Posted on 2026-02-02 Edited on 2026-04-06

题目大意

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

CF-1077-E. Jerry and Tom（没有思路的时候，可以从特殊情况入手）（可以从分析单步最优入手，从局部最优到整体最优）（不符合单步最优的，我们直接删除）（太复杂了，就要想想是不是可以删一些东西，即边）（深度其实也只和儿子的数量有关系）

Posted on 2026-01-30 Edited on 2026-04-06

题目大意

Jerry和Tom正在一个有 $n$ 个顶点的有向图 $G$ 上玩一个游戏，顶点编号从 $1$ 到 $n$ 。对于每个顶点 $1 \le u < n$ ，从 $u$ 到 $u+1$ 有一条有向边。此外，还有 $m$ 条额外的有向边。第 $i$ 条额外边从 $u_i$ 到 $v_i$ 。

图 $G$ 具有以下特殊性质：不存在两条有向边 $(u_i\to v_i)$ 和 $(u_j\to v_j)$ 使得 $u_i < u_j < v_i < v_j$ 。

在游戏开始时，Jerry和Tom分别站在顶点 $x$ 和 $y$ 上，其中 $x \ne y$ 。游戏按照轮次进行。在每个轮次中，玩家根据以下规则行动，Jerry先行，然后是Tom：

Jerry 必须选择从他当前顶点出发的一条出边****并沿着它移动到终点。如果他当前顶点没有出边，则他保持原地。
Tom 可以选择从他当前顶点出发的一条出边并沿着它移动到终点，或者选择不移动并保持原地。

如果在任何轮次结束时，Jerry和Tom在同一个顶点上（包括在顶点 $n$ 处），游戏立即结束且Tom获胜。否则，如果Jerry最初在顶点 $n$ ，或在任何轮次结束时到达顶点 $n$ ，Jerry获胜。

注意，如果在一轮之后，Jerry和Tom都在顶点 $n$ ，则Tom获胜。

在整个游戏过程中，两个玩家都知道对方的位置。

可以证明游戏会在有限轮次内结束。

对于一对整数 $1 \le x,y \le n$ ， $x \ne y$ ，定义 $f(x,y)$ 如下：

Jerry和Tom将进行一个游戏，其中Jerry从顶点 $x$ 开始，Tom从顶点 $y$ 开始。Tom想赢，但他也想最小化他实际移动的次数（即，他改变顶点的轮次数；原地不算移动）。假设双方都以最佳方式行动，如果Tom不能赢则令 $f(x,y)=0$ ；否则，令 $f(x,y)$ 为Tom强迫赢所需的最小移动次数。如果Tom在最佳游戏中获胜，Jerry仍会尽力最大化Tom必须移动的次数。

计算

\sum\limits_{1 \le x,y \le n, x \ne y}f(x,y).

思路讲解

我们梳理一下题意，并进行一下样例解释

题目不允许这样子的两条边存在。

在样例 2 中，贡献为 1 的两种情况。

如果说没有额外的边，那么答案就是 $0$ 。因为 Tom 在 Jerry 前面，反正肯定赢不了。Tom 在 Jerry 后面，守株待兔即可。可以发现，无论什么情况，根据定义，都是 $0$ 。

我们现在这个问题还是回来，什么时候肯定不会有这个追及，有这个贡献？其实就是如果把额外边当作区间加法的话，Tom 在没有被任何区间覆盖的地方，肯定是不会有答案贡献的。

不过我们发现，这样子一种一种情况看，实在是太慢了。既然是博弈题目，那么Tom 和 Jerry 的最优策略是什么呢？就是每步都走最远的边。

因此，我们不妨把 Tom 走的路径，以及 Jerry 走的路径绘画在一张图上（按照上面说的最优策略），这张图，其实是一颗树。

或者，换句话说，我们只保留每个点的最长出边（这样子就可以形成一颗树），较短的出边，我们直接删除（因为不符合）。

接着就是来处理这个贡献与计算问题了。

我们想要计算的就是，当我们已经知道一个点 $u$ ，在其他所有树上，比他的深度浅或者同样深度的所有点，记作 $V$ 集合，贡献为：

\sum_{v\in V}\text{dep}(u)-\text{dep}(\text{lca}(u,v))

这个问题，有许多解决方法，不过，我们这里选择使用启发式合并。

启发式合并的关键就是，合并过程复杂度，必须要依赖于轻儿子的这个子树的参数（如节点数量，深度等），不能够依赖于遍历重儿子。

不过，这个要求并不难，使用前缀和，搞一搞，就好了。

// 计算答案，把轻儿子节点合并进主集合中。
for (auto [dep_son,cnt]:node_dep_cnt_mtx[to]) {
    // cnt 是深度为 dep_son，较大的节点的数量（Jerry），get_presum_val 拿到的
    // 是所有比 dep_son 小的点的 dep(v)-dep(lca(u,v)) 的这个和
    ans+=cnt*get_presum_val(dep_son);
    // 深度相同的节点可以反复贡献（可以理解为上面也可以贡献，下面也可以贡献）
    ans+=cnt*node_dep_cnt_mtx[u][dep_son]*(dep_son-dep);
    // 这个是深度比 dep_son 大的节点的数量
    ll num_gt_dep=sum_node-get_presum_num(dep_son);
    // 深度比 dep 深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
    // 合并进来的时候还没有这样一个节点，贡献的就是 dep_son-dep(lca)
    ans+=num_gt_dep*cnt*(dep_son-dep);
    // 这里是顺手进行一个更新
    node_dep_cnt_mtx[u][dep_son]+=cnt;
}

注意这个有可能出现重儿子比轻儿子的这个链长短的这个情况（当然可以变为分长儿子/短儿子）。这个时候直接取这个前缀和，因为我们用 map 实现，就会取到 $0$ 。这个时候可以用一个匿名 get 函数特判一下这个情况。

这种情况的一个 hack 数据：

AC代码

AC
https://codeforces.com/contest/2188/submission/361002651

源代码

/**
 * Problem: E. Jerry and Tom
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/E
 * Created: 2026-01-30 16:36:38
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */
#include <bits/stdc++.h>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *我们现在就是卡在这个追及问题。
 *
 *现在我们卡在这个就是非对称贡献问题。
 *就是，我们卡在这个
 *
 */

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> diff_ls(N + 2);
    vector<ll> parent(N + 2);
    for (int i = 1; i <= N - 1; ++i) {
        parent[i] = i + 1;
    }
    for (int i = 1; i <= M; ++i) {
        ll u, v;
        cin >> u >> v;
        parent[u] = max(parent[u], v);
    }
    vector<vector<ll> > g(N + 2);
    for (int i = 1; i <= N - 1; ++i) {
        g[i].push_back(parent[i]);
        g[parent[i]].push_back(i);
    }
    vector<ll> size_ls(N + 2, 1), heavy_son(N + 2), mx_dep_ls(N+2);


    auto dfs1 = [&](auto &&self, ll u, ll p) -> ll {
        for (auto to: g[u]) {
            if (to == p) {
                continue;
            }
            size_ls[u] += self(self, to, u);
            if (size_ls[to] >= size_ls[heavy_son[u]]) {
                heavy_son[u] = to;
            }
        }
        return size_ls[u];
    };
    dfs1(dfs1, N, -1);
    // 我们想要计算的就是，当我们已经知道 一个点 v，在其他
    // 所有树上，比他的深度浅或者同样深度的所有点，贡献 dep(u)-dep(lca(u,v))
    // 不过只有其他

    // dsu on tree
    vector<map<ll,ll> > node_dep_cnt_mtx(N + 2);
    ll ans=0;
    auto dfs2 = [&](auto &&self, ll u, ll p,ll dep) -> void {
        for (auto to: g[u]) {
            if (to == p) continue;
            if (to != heavy_son[u]) continue;
            self(self, to, u, dep+1);
            // 复用重儿子的空间，避免 mle。
            swap(node_dep_cnt_mtx[u], node_dep_cnt_mtx[to]);
            break;
        }
        ll sum_node=size_ls[heavy_son[u]];
        for (auto to: g[u]) {
            if (to == p) continue;
            if (to == heavy_son[u]) continue;
            // 我们先写的 naive 一点
            self(self,to,u,dep+1);
            // 其实只要我们合并的方法只和轻儿子的子树相关性质有关系
            // 比如说深度，
            ll mx_dep=node_dep_cnt_mtx[to].rbegin()->first;
            // 虽然说比他的深度浅或者同样深度的所有点，贡献 dep(u)-dep(lca(u,v))
            // 但比他深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
            // 合并进来的时候还没有这样一个节点，贡献的就是 dep(v)-dep(lca(u,v))

            // 算前缀和
            map<ll,ll> pre_sum_val_mp,pre_sum_num_mp;
            ll lsum=0,lsum_node=0;
            for (auto [dep_son,cnt]:node_dep_cnt_mtx[u]) {
                // 像这里，我虽然遍历了重儿子的这个 node，但是实际上
                // 这里遍历的复杂度取决于轻儿子的这个最大深度
                if (dep_son>mx_dep) {
                    break;
                }
                lsum+=cnt*(dep_son-dep);
                lsum_node+=cnt;
                pre_sum_val_mp[dep_son]=lsum;
                pre_sum_num_mp[dep_son]=lsum_node;
            }
            auto get_presum_val=[&](ll dep_son) -> ll {
                if (pre_sum_val_mp.contains(dep_son)) {
                    return pre_sum_val_mp[dep_son];
                }else {
                    return pre_sum_val_mp.rbegin()->second;
                }
            };
            auto get_presum_num=[&](ll dep_son) -> ll {
                if (pre_sum_num_mp.contains(dep_son)) {
                    return pre_sum_num_mp[dep_son];
                }else {
                    return pre_sum_num_mp.rbegin()->second;
                }
            };
            // 计算答案，把轻儿子节点合并进主集合中。
            for (auto [dep_son,cnt]:node_dep_cnt_mtx[to]) {
                // cnt 是深度为 dep_son，较大的节点的数量（Jerry），get_presum_val 拿到的
                // 是所有比 dep_son 小的点的 dep(v)-dep(lca(u,v)) 的这个和
                ans+=cnt*get_presum_val(dep_son);
                // 深度相同的节点可以反复贡献（可以理解为上面也可以贡献，下面也可以贡献）
                ans+=cnt*node_dep_cnt_mtx[u][dep_son]*(dep_son-dep);
                // 这个是深度比 dep_son 大的节点的数量
                ll num_gt_dep=sum_node-get_presum_num(dep_son);
                // 深度比 dep 深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
                // 合并进来的时候还没有这样一个节点，贡献的就是 dep_son-dep(lca)
                ans+=num_gt_dep*cnt*(dep_son-dep);
                // 这里是顺手进行一个更新
                node_dep_cnt_mtx[u][dep_son]+=cnt;
            }
            sum_node+=size_ls[to];
        }
        node_dep_cnt_mtx[u][dep]++;
    };
    dfs2(dfs2,N,-1,1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2188/submission/361002651

1
3 1
1 3

1
5 1
1 4

1
7 2
3 7
4 6

20
*/

心路历程（WA，TLE，MLE……）

CF-1077-C. Restricted Sorting（当发现一个条件取决于两个数字的时候，可以想想，是不是可以只取决于一个数字？）

Posted on 2026-01-30 Edited on 2026-04-06

题目大意

给定长度为 $n$ 的数组 $a$ 。对于整数 $k$ ，我们称其为piggy，当且仅当通过执行以下操作任意次数（可能为零），可以将 $a$ 以非递减顺序排序：

首先，选择两个索引 $i$ 和 $j$ （ $1 \le i < j \le n$ ），使得 $|a_i - a_j| \ge k$ ;
然后，交换 $a_i$ 和 $a_j$ 。

您需要确定最大的piggy整数 $k$ 。如果不存在这样的整数，则输出 $-1$ 。

思路讲解

不难注意到，我们可以选用最大的数字或者最小的数字去做中转站，

乍一看，好像选择最小的数字，还是选择最大的数字，取决于两个数字 $to$ 和 $now$ ？实际上不是的，我们完全可以换着来，比如说：

这样子就实现了 $to$ 用 $mn$ ， $now$ 用这个 $mx$ ，反之亦然，完全可以只根据一个数去选择。

okay，那就行了。我们发现，这个 $to$ 和 $now$ 一定都是和有序序列中的同位置值不一样的点，因此，我们的答案其实就是：（其中 $S$ 为所有和有序序列中的同位置值不一样的点的下标集合）

ans\gets\min_{i\in S}(\max(mx-a_i,a_i-mn))

当然，也可以使用代码中的这个贪心实现。

AC代码

AC
https://codeforces.com/contest/2188/submission/360594620

源代码

/**
 * Problem: C. Restricted Sorting
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/C
 * Created: 2026-01-30 00:31:10
 * Author: Gospel_rock
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    if (is_sorted(all(A))) {
        cout<<-1<<"\n";
        return;
    }
    vector<ll> a_sort(all(A));
    sort(all(A));
    ll mn=*min_element(all(A)),mx=*max_element(all(A));
    auto check=[&](ll k) {
        for (int i=0;i<N;++i) {
            if (A[i]==a_sort[i]) {
                continue;
            }
            if (abs(A[i]-mn)<k && abs(mx-A[i])<k) {
                return false;
            }
        }
        return true;
    };
    ll l=0,r=mx;
    while (l<r) {
        ll mid=(l+r+1)>>1;
        if (check(mid)) {
            l=mid;
        }else {
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/