2024 扬州大学百度之星、码蹄杯校内选拔赛题解

文章大图来源: pixiv_id=89088195

A. 物理学家的传说

题目描述

定义 $f(x)$ 为正整数 $x$ 每一位数字的乘积。给定两个整数 $l$ 和 $r$，计算：

$$(\prod_{i=l}^r f(i)) \mod (10^9+7)$$

「2024 百度之星选拔赛」物理学家的传说

解题思路 模拟 + 数学

由于 $1 \le l \le r \le 10^9$，故直接暴力计算肯定会超时。

显然，当 $r - l + 1 >= 10$ 时，在 $[l, r]$ 区间内一定会出现至少一个数字其数位中存在 $0$。因此，在 $r - l + 1 \le 10$ 的情况下，连乘后答案一定为 $0$，此时直接输出 $0$ 即可；剩余的情况下，直接暴力模拟计算连乘输出答案。注意需要开 $\text{long long}$。每次模拟计算顶多大概 $80$ 次，时间复杂度 $O(T)$

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int mod = 1e9 + 7;

inline ll f(int x){
    ll res = 1;
    while(x) res = (res * (x % 10)) % mod, x /= 10;
    return res;
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ){
        int l, r; cin >> l >> r;
        if(r - l + 1 >= 10) cout << 0 << "\n";
        else{
            ll ans = 1;
            for(int i = l; i <= r; i ++ ) ans = (ans * f(i)) % mod;
            cout << ans << "\n";
        }
    }

    return 0;
}

B. 未知之花、魅知之旅

题目描述

给定一个 $n \times m$ 的 $01$ 矩阵。 定义合法路径为：$(1, 1)$ 为起点，$(n, m)$ 为终点，每次移动只能向右或向下。且路径中至少有 $p$ 个元素 $0$，同时至少有 $q$ 个元素 $1$。

两条路径不同当且仅当两条路径中至少有一个通过的位置不同。求给定矩阵中一共有多少条合法路径。答案对 $998244353$ 取模。

「2024 百度之星选拔赛」未知之花、魅知之旅

解题思路 状态机DP + 滚动数组

此题可以用动态规划来解决。定义 $dp[i][j][k]$ 为到达位置 $(i, j)$ 且经过了 $k$ 个元素 $1$ 的路径条数。状态这样定义的妙处在于，给定矩阵是一个 $01$ 矩阵，故我们只需要用一个维度来记录 $0$ 或 $1$ 的个数（此处记录的是 $1$ 的个数），假设到达 $(i, j)$ 经过了 $k$ 个 $1$，显然可以知道经过了 $i + j - 1 - k$ 个 $0$。

初始状态 $dp[1][1][g[1][1]] = 1$。由此，我们可以得到状态转移方程：

$$\begin{cases} dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k], & g[i][j] = 0 \\\\ dp[i][j][k] = dp[i - 1][j][k - 1] + dp[i][j - 1][k - 1], & g[i][j] = 1 \ \text{and} \ k > 0 \end{cases}$$

但是，由于 $1 \le n, m \le 300$，按照上面的状态定义我们需要 $300 \times 300 \times 600$ 的空间，会导致 $\text{MLE}$。因此我们需要进行空间优化。

可以发现，第一个维度每个状态之和上一层有关，因此可以用滚动数组把第一个维度的空间直接优化掉，最后只需要 $2\times 300 \times 600$ 的空间开销。滚动数组在进行上面的状态转移时，每次在更新 $dp[i]$ 时用完 $dp[i-1]$ 这一层的状态后都需要将其进行清空，否则会导致在下一层更新 $dp[i + 1]$ 时状态重叠而出错。

最后枚举第三个维度从 $q$ 到 $n + m - 1 - p$ 累加终点状态即为答案。（注意需要同时保证 $q$ 个 $1$ 和 $p$ 个 $0$）。时间复杂度 $O(n \times m \times (n + m))$。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 310, mod = 998244353;

int n, m, p, q, g[N][N];
ll dp[2][N][N << 1];

int main(){
    ios;

    cin >> n >> m >> p >> q;
    for(int i = 1; i <= n; i ++ ) 
        for(int j = 1; j <= m; j ++ ) cin >> g[i][j];

    dp[1][1][g[1][1]] = 1;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ )
            for(int k = 0; k <= i + j - 1; k ++ ){
                if(!g[i][j]){
                    dp[i&1][j][k]=(dp[i&1][j][k]+dp[(i-1)&1][j][k])%mod;
                    dp[i&1][j][k]=(dp[i&1][j][k]+dp[i&1][j-1][k])%mod;
                }
                if(g[i][j] && k){
                    dp[i&1][j][k]=(dp[i&1][j][k]+dp[(i-1)&1][j][k-1])%mod;
                    dp[i&1][j][k]=(dp[i&1][j][k]+dp[i&1][j-1][k-1])%mod;
                }
            }
        memset(dp[(i-1)&1], 0, sizeof dp[(i-1)&1]); // 清空上一层
    }

    ll ans = 0;
    for(int i = q; i <= n + m - 1 - p; i ++ ) ans = (ans+dp[n&1][m][i])%mod;
    cout << ans << "\n";    

    return 0;
}

C. 伏瓦鲁魔法图书馆

题目描述

给定一个长度为 $n$ 的数组 $a$，共 $m$ 次询问。每次询问一个区间 $[l, r]$，任选一个大于 $1$ 的正整数 $p$，求该区间内最多有多少个数能被 $p$ 整除。「2024 百度之星选拔赛」伏瓦鲁魔法图书馆

解题思路 莫队 + 质因数分解

显然，当选择 $p$ 为质因数时，答案一定更优。所以我们要求区间 $[l, r]$ 内，最多有多少个数有质因子 $p$。

由于不涉及修改操作，故考虑用离线莫队维护答案。记 $mx$ 为每个询问区间的答案。对于每个质数 $p$，我们需要维护当前区间内有多少元素可以被这个 $p$ 整除，记为 $cnt[p]$；同时，我们还需要维护有多少种质数 满足 当前区间内可以被这个质数整除元素个数为 $c$，记为 $num[c]$。

在莫队进行删除操作时，如果当前枚举质因数 $p$ 出现了 $mx$ 等于 $cnt[p]$，而已经没有可以 满足 当前区间可以被某个质数整除元素个数为 $c$ 的质因数了，此时需要进行 $mx$ 需要减一（删除每次只走一步）。

其他部分就是莫队的模板。（莫队 OI Wiki）。埃式筛复杂度 $O(m \log (\log m))$，每个数字质因子都只有几个，可视作常数，故此题莫队复杂度 $O(n \sqrt n)$，。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 5e4 + 10, M = 1e6 + 10;

vector<int> fac[M];
bool vis[M];

void work(int n){ // 质因数分解(埃式筛)
    for(int i = 2; i <= n; i ++ ){
        if(vis[i]) continue;
        for(int j = i; j <= n; j += i){
            vis[j] = true;
            fac[j].emplace_back(i);
        }
    }
}

int n, m, len, a[N];
int mx, ans[N];  // 记录答案
int cnt[M]; // cnt[p]: 当前区间内有相同质因子p的元素个数
int num[M]; // num[c]: 当前区间内有相同质因子的元素个数为c的质因数种类数
struct node{
    int l, r, id;
    bool operator < (const node &b) const {
        if(l / len != b.l / len) return l < b.l;
        return (l / len) & 1 ? r < b.r : r > b.r;
    }
}q[N];

inline void add(int x){
    for(auto &p : fac[x]){
        num[cnt[p]] -- ; 
        cnt[p] ++ ; 
        num[cnt[p]] ++ ; 
        mx = max(mx, cnt[p]);
    }
}

inline void del(int x){
    for(auto &p : fac[x]){
        num[cnt[p]] -- ;
        // 没有可以使得当前区间被某个质数整除元素个数为 $c$ 的质因数
        if(mx == cnt[p] && !num[cnt[p]]) mx -- ;
        cnt[p] -- ;
        num[cnt[p]] ++ ;
    }
}

int main(){
    ios;

    work(M - 7);

    int T = 1; cin >> T;
    while(T -- ){
        cin >> n >> m;
        mx = 0, len = (int)sqrt(n);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        for(int i = 1, l, r; i <= m; i ++ ){
            cin >> l >> r;
            q[i] = node{l, r, i};
        }
        sort(q + 1, q + m + 1);

        int l = 1, r = 0;
        for(int i = 1; i <= m; i ++ ){
            while(l > q[i].l) add(a[ -- l]);
            while(r < q[i].r) add(a[ ++ r]);
            while(l < q[i].l) del(a[l ++ ]);
            while(r > q[i].r) del(a[r -- ]);
            ans[q[i].id] = mx;
        }

        for(int i = 1; i <= m; i ++ ) cout << ans[i] << "\n";
        while(l <= r) del(a[l ++ ]); // 清空
    }

    return 0;
}

D. 明日之盛、昨日之俗

题目描述

给定一个 $n$ 个点 $m$ 条边的 $\text{DAG}$，边权都为 $1$，可能有重边。任意选择一条路径，所有路径选择等概率，路径的起点和终点可以相同。求选择的路径长度的期望。答案对 $998244353$ 取模。「2024 百度之星选拔赛」明日之盛、昨日之

解题思路 拓扑排序 + DP + 期望 + 逆元

此题比较经典。由于任意路径选择等概率，因此一条路径的期望可以由如下公式表示：

$$E = \frac{sum}{tot}$$

其中 $sum$ 为所有路径的长度之和，$tot$ 为所有不同路径的条数。

由于是 $\text{DAG}$，考虑用拓扑排序DP解决此题。我们可以用 $dp[v]$ 表示以 $v$ 点为结尾的所有路径的长度之和，$cnt[v]$ 为以 $v$ 点为结尾的所有不同路径条数。显然，只有直接连接到 $v$ 点的有向边 $(u, v)$ 会对 $dp[v]$ 产生影响，因此可以直接在拓扑排序过程中进行DP状态转移。

由于路径的起点和终点可以相同，因此对于所有点，初始情况下 $dp[v] = 0, cnt[v] = 1$。拓扑排序过程中的状态转移如下（当前点为 $u$，可达点为 $v$）：

$$\begin{split} dp[v] &= dp[v] + dp[u] + cnt[u] \\\\ cnt[v] &= cnt[v] + cnt[u] \end{split}$$

$cnt[v]$ 部分的转移比较好理解。比较容易忽视的是 $dp[v]$ 状态转移部分，需要加上 $cnt[u]$。由于到达 $u$ 有 $cnt[u]$ 种不同的路径，边权为 $1$，因此有向边 $(u, v)$ 对 $dp[v]$ 的贡献是 $cnt[u]$，而非 $1$。

最后答案只需要分别累加所有的 $dp[v]$ 和 $cnt[v]$，然后用快速幂求路径条数的逆元即可得到答案。时间复杂度 $O(n + m)$。

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e5 + 10, mod = 998244353;

ll dp[N], cnt[N];
int n, m, ind[N];
vector<int> e[N];

ll qmi(ll a, ll b, int mod){
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

void topo(){
    queue<int> q;
    for(int i = 1; i <= n; i ++ ){
        cnt[i] = 1;
        if(!ind[i]) q.emplace(i);
    }

    while(q.size()){
        int u = q.front();
        q.pop();

        for(auto &v : e[u]){
            dp[v] = (dp[v] + dp[u] + cnt[u]) % mod;
            cnt[v] = (cnt[v] + cnt[u]) % mod;
            if(!( -- ind[v])) q.emplace(v);
        }
    }
}

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        ind[v] ++ ;
    }

    topo();

    ll sum = 0, tot = 0;
    for(int i = 1; i <= n; i ++ ){
        sum = (sum + dp[i]) % mod;
        tot = (tot + cnt[i]) % mod;
    }
    cout << (sum * qmi(tot, mod - 2, mod) % mod) << "\n";

    return 0;
}

E. 魔女们的舞踏会

题目描述

给定一个无向图，每次可以执行一次如下操作：

• 任意选择一条边。将除这条边以外的其他边的边权都减去 $1$。

求最少多少次操作可以使得编号为 $k$ 的边 $(S, T)$ $确保在此无向图的最小生成树中。

「2024 百度之星选拔赛」魔女们的舞踏会

解题思路 最大流（最小割）

由 $Kruskal$ 算法可以知道，如果边 $(S, T)$ 是必须边，那么在加入所有权值小于等于边 $(S, T)$ 的边之前，$S$ 和 $T$ 一定是不连通的，直到加入了 $(S, T)$ 才会使得 $S$ 和 $T$ 连通（否则就会形成环，说明 $(S, T)$ 不是必须边）。

对于题中所给的操作，我们可以逆向思考这个操作对图的影响。选择一条边不动，其他边都减 $1$，根据相对性，我们可以看作是选择了一条边加 $1$，其他边都不动。

我们只需要考虑边权小于等于边 $(S, T)$ 的边 $(u, v)$，用这些边建一张新图。因此，问题转换为，最少需要多少次任选新图中的一条边使其加 $1$ 的操作，才能使得新图中 $S$ 和 $T$ 不连通，从而使得 $(S, T)$ 为使得 $S$ 和 $T$ 连通的必须边。

故我们可以考虑用最大流来解决此问题。源点设为 $S$，汇点设为 $T$。建立的新图中边的容量设为 $w_{S, T} - w + 1$，意为选择这条边最少需要操作多少次才会使得边权超过 $w_{S, T}$。我们需要求的就是求一个割边集使得图不连通（进而 $S$ 和 $T$ 肯定不连通），且这个边集的容量之和最小。 由最大流最小割定理，跑一边最大流即为答案。$dinic$ 算法时间复杂度 $O(n^2 \times m)$，但由于建模后图的特性，往往不会这么慢。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 510, M = 4010, inf = 0x3f3f3f3f;

int n, m, k, src, des;
struct node{ int u, v, w; }edge[M];
int h[N], e[M], ne[M], w[M], idx;

inline void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
    e[idx] = a, ne[idx] = h[b], w[idx] = 0, h[b] = idx ++ ;
}

int d[N], now[M];

bool bfs(){
    memset(d, -1, sizeof d);
    queue<int> q;
    q.emplace(src);
    d[src] = 0, now[src] = h[src];

    while(q.size()){
        int u = q.front();
        q.pop();

        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i], c = w[i];
            if(!c || ~d[v]) continue;
            
            q.emplace(v);
            d[v] = d[u] + 1, now[v] = h[v];

            if(v == des) return true;
        }
    }

    return false;
}

int dfs(int u, int flow){
    if(u == des) return flow;
    int used = 0;
    for(int i = now[u]; ~i && used < flow; i = ne[i]){
        now[u] = i;
        int v = e[i], c = w[i];
        if(c && d[v] == d[u] + 1){
            int f = dfs(v, min(c, flow - used));
            w[i] -= f, w[i ^ 1] += f;
            used += f;
        }
    }
    return used;
}

int dinic(){
    int res = 0;
    while(bfs()) res += dfs(src, inf);
    return res;
}

int main(){
    ios;

    cin >> n >> m >> k;
    for(int i = 1, u, v, w; i <= m; i ++ ){
        cin >> u >> v >> w;
        edge[i] = node{u, v, w};
    }

    src = edge[k].u, des = edge[k].v;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++ ){
        if(i == k) continue;
        auto [u, v, w] = edge[i];
        if(w <= edge[k].w){
            add(u, v, edge[k].w - w + 1);
            add(v, u, edge[k].w - w + 1);
        }
    }

    cout << dinic() << "\n";

    return 0;
}

F. 猫猫巫女灵梦

题目描述

一共有 $n$ 个节点，编号 $1 \sim n$，每个节点有个 $h_i$，$h_i$ 为 $1 \sim n$ 的互不相同的整数。 $n$ 个节点构成一棵树，猫猫初始在高度为 $n$ 的节点上。可以进行若干次在节点上放障碍物的操作，如果当前放置障碍物的节点为猫猫处于位置的节点，猫猫会移动到可达的节点中 $h_i$ 最大的节点上。移动到相邻的节点记为一次移动，求在某种放置方案下，猫猫最多可能移动的次数。「2024 百度之星选拔赛」猫猫巫女灵梦

解题思路 倍增求LCA + DP + 并查集

可以发现，假设当前猫在 $u$ 点，放下障碍物后，猫会移动到可达的最高点，由于 $u$ 点被堵住，此时猫再也无法返回到 $u$ 的其他子树。由此可知，每次猫只能移动到一个子树中，其行动轨迹是固定的，每次只需要找到可以移动最长距离的子树转移过去即可。

考虑用 DP 解决此问题。设 $dp[u]$ 表示以 $u$ 为根节点的子树，且猫在 $u$ 点可以移动的最长距离。令 $u$ 为根节点的子树中的最高点为 $pos_u$，故有如下状态转移：

$$dp[u] = \max \{dp[pos_v] + dist(u, v)\}$$

其中 $dist(u, v)$ 为树上点 $u$ 和 $v$ 之间的距离。

由于猫是从最高点开始出发的，容易发现猫的行动轨迹一定是一个高度单调递减的点列。因此，在状态转移过程中，我们需要从高度最低的点开始枚举，得到较低点的状态才能得到更高点的状态。故状态转移时还需满足条件 $h_{pos_v} < h_u$。

为了方便状态转移，我们考虑以 $(h[u], h[v])$ 的方式建边。对于树上两点距离，采用倍增求 LCA 即可；对于维护子树中的最高可达点，采用并查集维护即可。注意开 $\text{long long}$。时间复杂度 $O(n \log n)$。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 2e5 + 10;

vector<int> e[N];
int n, h[N], d[N], f[N][22];
ll dp[N];  // dp[u]以u为根节点子树，猫在u点，可以走的最长距离
int fa[N]; // fa[u]维护u为根节点子树中最高的点

inline int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }

void bfs(int src){
    queue<int> q;
    q.emplace(src);
    d[src] = 1;

    while(q.size()){
        int u = q.front();
        q.pop();

        for(auto &v : e[u]){
            if(!d[v]){
                d[v] = d[u] + 1, f[v][0] = u;
                q.emplace(v);
                for(int k = 1; k <= 20; k ++ ) 
                    f[v][k] = f[f[v][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int k = 20; ~k; k -- ) 
        if(d[f[a][k]] >= d[b]) a = f[a][k];
    if(a == b) return a;
    for(int k = 20; ~k; k -- )
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0]; 
}
// lca求树上两点距离
inline int getd(int x, int y){ return d[x] + d[y] - 2 * d[lca(x, y)]; }

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> h[i];
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        u = h[u], v = h[v];
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    bfs(1);

    for(int i = 1; i <= n; i ++ ) fa[i] = i;
    for(int u = 1; u <= n; u ++ )
        for(auto v : e[u]){
            v = find(v);
            if(v < u) fa[v] = u, dp[u] = max(dp[u], dp[v] + getd(u, v));
        }

    cout << dp[n] << "\n";

    return 0;
}

G. 神圣庄严的大赌场

题目描述

投掷三个骰子，骰子 $1$ 和 $4$ 点的面是红色的，$2, 3, 5, 6$ 点的面是黑色的。判断三个骰子是否可以满足朝上面红色点数之和为 $A$ 同时黑色点数之和为 $B$ 。 「2024 百度之星选拔赛」神圣庄严的大赌场

解题思路 枚举

直接暴力三重循环枚举所有清空，判断是否存在满足即可。时间复杂度常数级。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

bool check(int x, int y){
    for(int i = 1; i <= 6; i ++ )
        for(int j = 1; j <= 6; j ++ )
            for(int k = 1; k <= 6; k ++ ){
                int r = 0, b = 0;
                if(i == 1 || i == 4) r += i;
                else b += i;
                if(j == 1 || j == 4) r += j;
                else b += j;
                if(k == 1 || k == 4) r += k;
                else b += k;

                if(r == x && b == y) return true;
            }
    return false;
}

int main(){
    ios;

    int a, b; cin >> a >> b;
    cout << (check(a, b) ? "Yes" : "No") << "\n";

    return 0;
}

H. 2024 幻想乡越野赛

题目描述

有 $n$ 个人，每个人一个 $v$ 和 一个 $b$，$v$ 表示速度。每个人可以单独行动也可以附着在其他人身上一起行动。当 $j$ 附着在 $i$ 上时：

• 若队员 $i$ 满足 $b_i \ge b_j$，则队员 $i$ 不会收到影响，速度仍然为 $v_i$；

• 若队员 $i$ 满足 $b_i < b_j$，则队员 $i$ 速度变为 $v_i - (b_j - b_i)$。

如果附着后会导致速度变为负数，则附着不成立。最多两个人一起行动。定义整个队伍的速度为为未附着在其他人身上的人中，最小的速度。求可以达到的最大速度。

「2024 百度之星选拔赛」2024 幻想乡越野赛

解题思路 二分 + 贪心

我们可以先对表达式进行一个变形，将 $v_i - (b_j - b_i)$ 变为 $v_i + b_i - b_j$。若最终可达的速度为 $ans$，所有速度小于 $ans$ 的人都必须附着在其他人身上。

显然问题具有单调性，考虑二分答案。每次 $check$ 时，将成员按照 $v_i < ans$ 和 $v_i \ge ans$ 分开。对于所有 $v_j < ans$ 的成员 $j$，必须在 $v_j \ge ans$ 的人中找到一个成员 $i$ 可以满足 $v_i + b_i - b_j \ge ans$。因此，我们可以从从大到小排序，贪心匹配每个 $v_j < ans$ 的成员附着到的成员 $i$，让每个 $v_j < ans$ 的成员 $j$ 匹配到可匹配的 $v_i + b_i$ 最大的 $v_i \ge ans$ 的成员 $i$ 上即可。如果在匹配过程中出现 $v_i + b_i - b_j < ans$，则表明当前 $ans$ 不合法，$ans$ 需要减小；否则 $ans$ 合法。时间复杂度 $O(n (\log n)^2 )$

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
const int N = 1e5 + 10;

pii p[N];
int n;

inline bool check(int mid){
    vector<int> le, ge;
    for(int i = 1; i <= n; i ++ ){
        auto [v, b] = p[i];
        if(v >= mid) ge.emplace_back(v + b);
        else le.emplace_back(b);
    }

    int szl = le.size(), szg = ge.size();
    if(szl > szg) return false; // 特判
    sort(begin(ge), end(ge), greater<int>());
    sort(begin(le), end(le), greater<int>());

    for(int i = 0; i < szl; i ++ )
        if(ge[i] - le[i] < mid) return false;
    
    return true;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n;
        for(int i = 1, x, y; i <= n; i ++ ) cin >> x >> y, p[i] = MP(x, y);

        int l = 1, r = 1e9;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        cout << l << "\n";
    }

    return 0;
}