Znzryb's Blog

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;
}

/*

*/

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

CF-1077-D. Shortest Statement Ever（没招的时候可以尝试尝试 dp）（高位起到决定性作用）

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

题目大意

给定两个非负整数 $x$ ， $y$ 。找到两个非负整数 $p$ 和 $q$ ，使得 $p\;\&\;q=0$ ，且 $|x-p|+|y-q|$ 最小化。这里， $\&$ 表示按位与操作。

You are given two non-negative integers $x$ , $y$ . Find two non-negative integers $p$ and $q$ such that $p\;\&\;q=0$ , and $|x-p|+|y-q|$ is minimized. Here, $\&$ denotes the bitwise AND operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The only line of each test case contains two non-negative integers $x$ and $y$ ( $0 \le x,y < 2^{30}$ ).

Output

For each test case, output two non-negative integers $p$ and $q$ you found. If there are multiple pairs of $p$ and $q$ satisfying the conditions, you may output any of them.

It can be proven that under the constraints of the problem, any valid solution satisfies $\max(p,q)<2^{31}$ .

7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822

0 0
2 1
3 8
6 9
4 3
128 321
1073741824 1073741822

Note

In the first test case, one valid pair would be $p=0$ and $q=0$ , as $0\,\&\,0=0$ and $|x-p|+|y-q|=|0-0|+|0-0|=0$ is the minimum over all pairs of $p$ and $q$ .

In the third test case, one valid pair would be $p=3$ and $q=8$ , as $3\,\&\,8=0$ and $|x-p|+|y-q|=|3-3|+|8-6|=2$ is the minimum over all pairs of $p$ and $q$ . Note that $(p,q)=(3,4)$ is also a valid pair.

思路讲解

我们需要利用这个高位较优的这个特性，

我们设计了一个 dp， $dp_{i,0}$ 表示该位采用 $0,0$ 的配置， $dp_{i,1}$ 表示该位采用 $1,0$ 的配置， $dp_{i,2}$ 表示该位采用 $0,1$ 的配置。

不难写出这样的转移式子：

vector dp(40,vector<Diff_p_q>(3));
dp[36][0]=Diff_p_q(0,0);
dp[36][1]=Diff_p_q(1ll<<36,0);
dp[36][2]=Diff_p_q(0,1ll<<36);
for (int i=35;i>=0;--i) {
    dp[i]=dp[i+1];
    // dp[i][0]   自己重新开始     继承      继承       继承
    dp[i][0]=min({Diff_p_q(0,0),dp[i][0],dp[i+1][1],dp[i+1][2]});
    //             自己重新开始
    dp[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp[i+1][0].p+(1ll<<i),dp[i+1][0].q),
        Diff_p_q(dp[i+1][1].p+(1ll<<i),dp[i+1][1].q),
        Diff_p_q(dp[i+1][2].p+(1ll<<i),dp[i+1][2].q)});
    dp[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp[i+1][0].p,dp[i+1][0].q+(1ll<<i)),
        Diff_p_q(dp[i+1][1].p,dp[i+1][1].q+(1ll<<i)),
        Diff_p_q(dp[i+1][2].p,dp[i+1][2].q+(1ll<<i))});
}

然后你忐忑地提交了，结果 WA on 2。

你使用了对拍，或者其实你不需要使用对拍，你也知道，是因为上面的做法有一些激进，高位上比较好，那自然是比较好的，但是好分大的好和小的好。那么上面的做法，大的好，自然是可以得到的，但是小的好，就不是那么简单的可以得到的了。

_______________[ Testcase #1 INPUT ]_______________
1
78 88

_______________[ Testcase #1 OUTPUT]_______________
78 128
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:40
brute_diff:39
x_br:39
y_br:88

那么对拍也给了我们这个反馈，确实是这样的。

但是我们怎么样得到小的好呢？其实也简单，我们使用同样方法，整一个 dp，但是我们 dp 里存的的那个结构体的构造函数，我们传入一个指示参数，使得只要一出现大于的情况，就给他附上 $diff\gets\text{INF}$ ，使其不够优秀而被淘汰，强制得到这个我们所谓的小的好。

struct Diff_p_q {
    ll diff,p,q;
    bool operator<(const Diff_p_q &o) const {
        return diff<o.diff;
    }
    Diff_p_q()=default;
    explicit Diff_p_q(ll p,ll q,bool no_big=false) {
        if (!no_big) {
            diff=abs(p-X)+abs(q-Y);
            this->p=p;
            this->q=q;
        }else {
            if (p > X || q > Y) {
                diff=INF;
            }else {
                diff=abs(p-X)+abs(q-Y);
            }
            this->p=p;
            this->q=q;
        }

    }
};

一样的 dp 过程。

Diff_p_q Ans=min({dp[0][0],dp[0][1],dp[0][2]});
{
    vector dp2(40,vector<Diff_p_q>(3));
    dp2[36][0]=Diff_p_q(0,0,true);
    dp2[36][1]=Diff_p_q(1ll<<36,0,true);
    dp2[36][2]=Diff_p_q(0,1ll<<36,true);
    for (int i=35;i>=0;--i) {
        dp2[i]=dp2[i+1];
        // dp[i][0]   自己重新开始     继承      继承       继承
        dp2[i][0]=min({Diff_p_q(0,0,true),dp2[i][0],dp2[i+1][1],dp2[i+1][2]});
        //             自己重新开始
        dp2[i][1]=min({Diff_p_q(1ll<<i,0,true),Diff_p_q(dp2[i+1][0].p+(1ll<<i),dp2[i+1][0].q,true),
            Diff_p_q(dp2[i+1][1].p+(1ll<<i),dp2[i+1][1].q,true),
            Diff_p_q(dp2[i+1][2].p+(1ll<<i),dp2[i+1][2].q,true)});
        dp2[i][2]=min({Diff_p_q(0,1ll<<i,true),Diff_p_q(dp2[i+1][0].p,dp2[i+1][0].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][1].p,dp2[i+1][1].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][2].p,dp2[i+1][2].q+(1ll<<i),true)});
    }
    Ans=min({Ans,dp2[0][0],dp2[0][1],dp2[0][2]});
}
cout<<Ans.p<<" "<<Ans.q<<"\n";

okay，上面我们已经把我们的思路讲的比较清楚了。

我感觉这个代码对是因为，在确定好高位以后，绝对值距离最小的数一定贴在区间边界：要么贴上边界（低位全 0），要么贴下边界（低位全 1）；中间形态永远不可能比边界更近。

不过我们的第一种 dp 由于没有引入这个 loose 和 tight，实际上计算出来的，并不是严格的 $≥$ ，会有 $<$ 的情况出现，所以我心里也不太踏实。欢迎 hack 我的代码。

AC代码

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

源代码

/**
 * Problem: D. Shortest Statement Ever
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/D
 * Created: 2026-01-30 01:18:00
 * 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;

/*
 *
 */
ll X,Y;
struct Diff_p_q {
    ll diff,p,q;
    bool operator<(const Diff_p_q &o) const {
        return diff<o.diff;
    }
    Diff_p_q()=default;
    explicit Diff_p_q(ll p,ll q,bool no_big=false) {
        if (!no_big) {
            diff=abs(p-X)+abs(q-Y);
            this->p=p;
            this->q=q;
        }else {
            if (p > X || q > Y) {
                diff=INF;
            }else {
                diff=abs(p-X)+abs(q-Y);
            }
            this->p=p;
            this->q=q;
        }

    }
};
void Solve() {
    cin >> X >> Y;
    vector dp(40,vector<Diff_p_q>(3));
    dp[36][0]=Diff_p_q(0,0);
    dp[36][1]=Diff_p_q(1ll<<36,0);
    dp[36][2]=Diff_p_q(0,1ll<<36);
    for (int i=35;i>=0;--i) {
        dp[i]=dp[i+1];
        // dp[i][0]   自己重新开始     继承      继承       继承
        dp[i][0]=min({Diff_p_q(0,0),dp[i][0],dp[i+1][1],dp[i+1][2]});
        //             自己重新开始
        dp[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp[i+1][0].p+(1ll<<i),dp[i+1][0].q),
            Diff_p_q(dp[i+1][1].p+(1ll<<i),dp[i+1][1].q),
            Diff_p_q(dp[i+1][2].p+(1ll<<i),dp[i+1][2].q)});
        dp[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp[i+1][0].p,dp[i+1][0].q+(1ll<<i)),
            Diff_p_q(dp[i+1][1].p,dp[i+1][1].q+(1ll<<i)),
            Diff_p_q(dp[i+1][2].p,dp[i+1][2].q+(1ll<<i))});
    }
    Diff_p_q Ans=min({dp[0][0],dp[0][1],dp[0][2]});
    {
        vector dp2(40,vector<Diff_p_q>(3));
        dp2[36][0]=Diff_p_q(0,0,true);
        dp2[36][1]=Diff_p_q(1ll<<36,0,true);
        dp2[36][2]=Diff_p_q(0,1ll<<36,true);
        for (int i=35;i>=0;--i) {
            dp2[i]=dp2[i+1];
            // dp[i][0]   自己重新开始     继承      继承       继承
            dp2[i][0]=min({Diff_p_q(0,0,true),dp2[i][0],dp2[i+1][1],dp2[i+1][2]});
            //             自己重新开始
            dp2[i][1]=min({Diff_p_q(1ll<<i,0,true),Diff_p_q(dp2[i+1][0].p+(1ll<<i),dp2[i+1][0].q,true),
                Diff_p_q(dp2[i+1][1].p+(1ll<<i),dp2[i+1][1].q,true),
                Diff_p_q(dp2[i+1][2].p+(1ll<<i),dp2[i+1][2].q,true)});
            dp2[i][2]=min({Diff_p_q(0,1ll<<i,true),Diff_p_q(dp2[i+1][0].p,dp2[i+1][0].q+(1ll<<i),true),
                Diff_p_q(dp2[i+1][1].p,dp2[i+1][1].q+(1ll<<i),true),
                Diff_p_q(dp2[i+1][2].p,dp2[i+1][2].q+(1ll<<i),true)});
        }
        Ans=min({Ans,dp2[0][0],dp2[0][1],dp2[0][2]});
    }
    cout<<Ans.p<<" "<<Ans.q<<"\n";

#ifdef LOCAL
    if (X>100 || Y>100) {
        return;
    }
    ll brute_diff=INF,x_br,y_br;
    for (int i=0;i<=1000;++i) {
        for (int j=0;j<=1000;++j) {
            if ((i&j)==0) {
                ll lans=abs(i-X)+abs(j-Y);
                if (lans<=brute_diff) {
                    x_br=i;
                    y_br=j;
                    brute_diff=lans;
                }
            }
        }
    }
    if (brute_diff==Ans.diff) {
        return;
    }
    cout<<"WA\n";
    debug(Ans.diff);
    debug(brute_diff);
    debug(x_br);
    debug(y_br);
#endif

}

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/360662700

_______________[ Stress test, testcase 187 OUTPUT]_______________
63 64
[+] SUCCESS: CORRECT ANSWER
_______________[ Stress test, testcase 188 INPUT ]_______________
1
41 9

_______________[ Stress test, testcase 188 OUTPUT]_______________
41 16
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:7
brute_diff:3
x_br:41
y_br:6



_______________[ Testcase #1 INPUT ]_______________
1
78 88

_______________[ Testcase #1 OUTPUT]_______________
78 128
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:40
brute_diff:39
x_br:39
y_br:88




{
        ll dp;
        vector dp2(40,vector<Diff_p_q>(3));
        dp2[0][0]=Diff_p_q(0,0);
        dp2[0][1]=Diff_p_q(1,0);
        dp2[0][2]=Diff_p_q(0,1);
        for (int i=0;i<=35;++i) {
            dp2[i]=dp2[i-1];
            // dp[i][0]   自己重新开始     继承      继承       继承
            dp2[i][0]=min({Diff_p_q(0,0),dp2[i][0],dp2[i-1][1],dp2[i-1][2]});
            //             自己重新开始
            dp2[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp2[i-1][0].p+(1ll<<i),dp2[i-1][0].q),
                Diff_p_q(dp2[i-1][1].p+(1ll<<i),dp2[i-1][1].q),
                Diff_p_q(dp2[i-1][2].p+(1ll<<i),dp2[i-1][2].q)});
            dp2[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp2[i-1][0].p,dp2[i-1][0].q+(1ll<<i)),
                Diff_p_q(dp2[i-1][1].p,dp2[i-1][1].q+(1ll<<i)),
                Diff_p_q(dp2[i-1][2].p,dp2[i-1][2].q+(1ll<<i))});
        }
        Ans=min({Ans,dp2[35][0],dp2[35][1],dp2[35][2]});
    }

*/