2026“钉耙编程”中国大学生算法设计春季联赛（5）

1005 老骥伏枥

Problem Description

2026 丙午马年，一位少年骑手报名参加马拉松骑行挑战赛。赛道上的打卡点以正整数编号 $(1,2,3,\ldots)$，若两个打卡点的编号 $i,j$ 满足 $\operatorname{popcount}(i \oplus j)=1$，则它们之间有一条长度为 $1$ 的赛道。

少年从 $1$ 号打卡点出发，目标是到达 $n$ 号打卡点。请你帮他算出最短路的长度。

其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数，$\oplus$ 表示按位异或。

Input

输入 $T$（$1 \le T \le 5 \cdot 10^4$），表示数据组数。

接下来 $T$ 行，每行一个正整数 $n$（$1 \le n \le 10^9$）。

Output

对于每组数据，输出一行一个整数，表示最短路的长度。

解题思路

判断x和1的二进制有多少位不相同就是答案

题解代码

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

const int inf = 0x3f3f3f3f;

void sol() {
    int n; cin >> n;
	int x = 1;
	int cnt = 0;
	for (int i =0; i <= 31; i++)
		if (((x >> i) & 1) != ((n >> i) & 1))
			cnt++;
	cout << cnt << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	    sol();
    return 0;
}

1003 马蹄疾

Problem Description

2026 丙午马年，全国马术锦标赛盛大开幕。一匹骏马要跑过 $n$ 个标记点，在第 $i$ 个标记点处，骑手会选择一种步法编码 $a_i$（满足 $0 \le a_i < 2^t$）。

马匹跑过前 $i$ 个驿标后的奔势定义为前 $i$ 个步法编码的异或值：

$$p_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$$

一次奔跑的马力值是所有奔势的总和：

$$S = \sum_{i=1}^{n} p_i$$

比赛裁判伯乐拿到了若干份参赛申请，每份申请声称自己的马匹在给定的 $n$ 和 $t$ 下能跑出马力值 $S$。伯乐需要逐一审核——这样的奔跑是否存在？请你帮帮伯乐。

Input

本题有多组测试数据。输入 $T$（$1 \le T \le 5 \cdot 10^4$），表示数据组数。

对于每组数据：

一行三个整数 $n,t,S$（$1 \le n \le 10^5$，$1 \le t \le 30$，$0 \le S \le 10^{15}$）。

Output

对于每组数据，输出一行 Yes 或 No。

解题思路

S最小可以是0，最大可以是n个二进制全部为1的数的和，判断一下就行。

题解代码

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

const int inf = 0x3f3f3f3f;
typedef long long ls;


void sol() {
    ls n, t, s; cin >> n >> t >> s;
	if (s >= 0 && s <= ((1LL << t) - 1) * n)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	    sol();
    return 0;
}

1002 驿站

Problem Description

2026 丙午马年，某快递公司运营着一张覆盖全国的物流网络，快递员马马不停蹄地在各驿站之间接力配送。

该网络共设有 $n$ 座驿站，编号为 $1,2,\ldots,n$，驿站之间由 $m$ 条单向运输线路相连。每座驿站的编号代表其安全等级——编号越大，途经该驿站包裹丢失的风险越高。

一条从驿站 $1$（总部）到驿站 $i$ 的运输路线 $P=(v_1,v_2,\ldots,v_k)$（其中 $v_1=1$，$v_k=i$）的风险值定义为途经所有驿站编号的最大值，即：

$$\operatorname{risk}(P)=\max_{1 \le j \le k} v_j$$

调度员需要为每座驿站规划最安全的配送路线。对于每个驿站 $i \in \{1,2,\ldots,n\}$，求从总部出发到达驿站 $i$ 的所有路线中风险值的最小值。若驿站 $i$ 无法从总部到达，输出 $-1$。

Input

本题有多组测试数据。输入 $T$（$1 \le T \le 10^3$），表示数据组数。

对于每组数据（相邻两组数据间用一空行隔开）：

第一行输入两个正整数 $n,m$（$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$）。

接下来 $m$ 行，每行输入两个正整数 $u,v$（$1 \le u,v \le n$），表示一条从驿站 $u$ 到驿站 $v$ 的单向驿道。图中可能存在重边和自环。

保证所有数据的 $n$ 的和不超过 $10^6$，$m$ 的和不超过 $2 \times 10^6$。

Output

对于每组数据：

输出一行 $n$ 个整数，第 $i$ 个整数表示从总部到驿站 $i$ 的最小风险值。若不可达，输出 $-1$。

题面解读

给定一个图，找1号点到每个点的路径，要求这条路径中的最大值最小，输出这个值。

解题思路

单源最短路问题的变种，用dijkstra的优先队列优化。

最短路是距离最短，这题是路径中最大值最小，那就让优先队列保存路径中的最大值，每次找到可以使得它最大值减小的路径就转移。

题解代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

void sol(){
	vector<int> h[N];
	vector<bool> vis(N, false);
	vector<int> dis(N, INF);
	int n, m; cin >> n >> m;
	while (m--){
		int u, v; cin >> u >> v;
		h[u].push_back(v);
	}
	auto dijkstra = [&](){
		priority_queue<PII, vector<PII>, greater<PII>> q;
		dis[1] = 1;
		q.push({1, 1});
		while (!q.empty()){
			int u = q.top().second;
			q.pop();
			if (vis[u])
				continue;
			vis[u] = true;
			for (auto v : h[u])
				if (max(v, dis[u]) < dis[v]){
					dis[v] = max(v, dis[u]);
					q.push({dis[v], v});
				}
		}
	};
	dijkstra();
	for (int i = 1; i <= n; i++)
		if (dis[i] != INF)
			cout << dis[i] << ' ';
		else
			cout << -1 << ' ';
	cout << endl;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
		sol();
}