第七届传智杯全国IT技能大赛程序设计赛道省赛（第二场）—— 题解
补题链接：
https://ac.nowcoder.com/acm/contest/103864
以下的代码均只给出了核心逻辑部分，并不是完整的代码。
同时代码中的 assert() 语句均为 std 编写过程中，充当validator的语句，提交时可以不写。
为了不产生歧义，这里给出以下代码的头文件部分：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long
const int mod = 1e9 + 7;
const int pp = 998244353;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
a %= p;
while(b) {
if(b & 1) ans = (ans * a) % p;
b >>= 1;
a = (a * a) % p;
}
return ans % p;
}
A. 小苯点兵点将
题意：
给定 ，问
内是否存在至少一个
的倍数。
知识点：
模拟，数学
题解：
可以直接遍历判断，也可以求出 中
倍数的个数，和
中
倍数的个数，作差判断结果是否大于
。
void solve() {
int L, R, k = 3;
cin >> L >> R;
assert(L >= 1);
assert(L <= R);
assert(R <= 2000);
assert(k <= 2000);
if(R / k - (L - 1) / k > 0) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
时间复杂度：单组
B. 小苯的迷宫行走
题意：
给定一个面积为 奇数 的矩阵，要从左上角出发走到右下角，每一步可以走到上下左右四个相邻的位置上，每个点都只能经过最多一次，要求最大化所有走过的点的 的按位或值，求这个最大的按位或是多少。
知识点：
位运算，构造，贪心
题解：
实际上，当 和
中任意一个为奇数时，我们总能找到一条路径使得他能把所有点都走过恰好一遍，路径大概长成一个 “
” 型，或者是横躺着的 “
” 型。而题目限定了面积是奇数，则
都是奇数，因此我们一定可以通过走 “
” 把 所有点 经过一次。
而位运算 的性质则是越
越大，既然我们有办法将所有格子都走一遍的同时走到终点，因此我们直接将所有输入的数字都
起来即可。
代码：
void solve() {
int n, m;
cin >> n >> m;
assert(n <= 4000);
assert(m <= 4000);
assert((n * m) & 1);
int ans = 0;
for(int i = 0, x; i < n * m; i++) {
cin >> x;
assert(x <= 1e9);
assert(x >= 0);
ans |= x;
}
cout << ans << endl;
}
时间复杂度：
C.小苯的好数
题意：
定义 是所有严格小于
的因子之和，例如
，定义好数是：
是个偶数。
知识点：
数学，前缀和
题解：
首先不难发现偶数一定是好数，因为如果 是偶数则
一定是偶数。那么此时我们考虑可能的奇数，这里我们可以将奇数的因子以一对一对的形式写出，例如
。
我们会发现，奇数一定是 奇数 奇数 得到的，而由于这些因子都是成对出现，因此如果将
的所有因子相加，其结果应该是 “偶数个奇数” 相加，则结果应该是偶数。但实际上我们会发现特例就在于，如果
是一个奇完全平方数，即存在正整数
使得
，那么此时上述提到的一对对 奇数
奇数 的总和就会少一个奇数，会使得结果从偶数变成奇数，因此完全平方数是特例。
但我们本题天然的会少一个最大的奇数因子，即 本身，因此其结论也是反过来的，也就是说对于奇数
，当且仅当其是完全平方数，其才是好数。
得到了上述的结论，则我们存每个数字是不是好数，用前缀和优化查询即可。
代码：
void solve() {
int n, q;
cin >> n >> q;
vector<int> s(n + 1);
auto check = [&](int x) -> bool {
if(x % 2 == 0) return 1;
int sq = sqrt(x);
return sq * sq == x;
};
for(int i = 1, x; i <= n; i++) {
cin >> x;
s[i] = s[i - 1] + check(x);
}
while(q -- ) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
}
时间复杂度：。
D. 小苯的 
题意：
给定长度为 的
串，保证只由
和
两种字符构成，至多选择
个位置改变字符从
到
；
到
，问最多可以产生多少个不相交的 "
" 子串。
知识点：
题解：
不难想到，可以定义 表示考虑到前
个位置的时候，操作了
次最多子串个数。则我们直接枚举
转移即可，这里思考下就会发现，我们可以给
数组加一个限制为：最后一个 "
" 子串一定是
这个子串修改得到的，这样一来
的转移将十分简单，我们求出把最后三个字符改成 "
" 的花费
，接着从
的状态转移过来即可，具体的见代码。
代码：
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
if(n < 3) {
cout << 0 << endl;
return ;
}
s = " " + s;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1e9));
dp[0][0] = dp[1][0] = dp[2][0] = 0;
for(int i = 3; i <= n; i++) {
int cost = (s[i - 2] != 'o') + (s[i - 1] != 'v') + (s[i] != 'o');
dp[i] = dp[i - 1];
for(int j = cost; j <= k; j++) {
dp[i][j] = max(dp[i][j], dp[i - 3][j - cost] + 1);
}
}
cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
}
当然，不要忘记特判 的情况。
时间复杂度：
（当然，本题可以使用 二分的做法优化到
，难度不低，这里不详细展开了。）
E. 小苯的水瓶
题意：
给定 个水瓶，每个水瓶一开始装了一些水，现在可以：
任选一些水瓶对
，把
中的水倒入
中，使用这个操作最多倒出
单位水；
另有一个水壶可以给任意瓶子倒水，使用这个操作最多倒出
单位的水。
求装水量最少的瓶子最多能装多少水。
知识点：
二分，贪心
题解：
首先不难发现答案有单调性，因此考虑二分答案。
那么对于一个答案 ，如何
其是否合法，我们只需要贪心即可，
方便起见我们对数组排序，首先把超过
的那些水瓶中的水倒入不够
的那些水瓶中，这一步可以双指针实现，也可以简单枚举实现。
接着我们只需要看所有瓶子中不够 的需求量是否在
以内即可，直接枚举一遍就行，如果在
以内则合法。
需要注意的是，本题如果无脑倒水的话在实现上可能会爆 ，因此还是建议读者在上述的 ”判断不够
的瓶子中缺的水量是否够
时“ 加上判断，如果超过
可以直接
。（下方的代码中并没有这一点，因此开了
防止爆
了。）
代码：
void solve() {
int n, m, k;
cin >> n >> m >> k;
assert(n <= 2e5);
assert(m <= 2e14);
assert(k <= 2e14);
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) {
assert(a[i] >= 0 && a[i] <= 1e9);
cin >> a[i];
}
sort(a.begin() + 1, a.end());
auto check = [&](int mid) -> bool {
auto b = a;
int s = 0;
for(int i = n; i > 0; i--) {
s += max(0LL, b[i] - mid);
b[i] = min(mid, b[i]);
}
s = min(s, m);
for(int i = 1; i <= n; i++) {
int sub = max(0LL, mid - b[i]);
if(sub <= 0) continue;
if(s >= sub) {
s -= sub;
b[i] = mid;
} else {
b[i] += s;
s = 0;
break;
}
}
lll K = k; // 注意K有可能会爆longlong
for(int i = 1; i <= n; i++) {
K -= max(0LL, mid - b[i]);
}
return K >= 0;
};
int l = 0, r = 1e16;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
复杂度：，其中
为二分的上限。
F.小苯的旅行计划
题意：给定一棵带边权树，另有 个点对
，表示要花费
，即花费：
走到
最短路路径上的边权和。现在最多可以使得一条边免费，求总花费的最小值。
知识点：
树上差分，枚举，
题解：
实际上做法十分明显，我们考虑枚举那个免费的边，想一想其对答案的影响是什么，实际上就是，如果它免费，则答案会减少所有经过它的 点对数
它的边权。
它的边权我们已知，那么我们的问题转为了如何求经过一条边的点对数量，这里我们使用 对每个输入的点对做一个树上边差分即可，做好后枚举免费的边，取最优答案即可。
难点在于代码实现上的细节，有同学可能只会做树上点差分，实际上边差分是一样的只需要把边权下放给 中更深点的点权即可。
代码：
void solve() {
int n, m;
cin >> n >> m;
assert(n <= 1e5);
assert(m <= 2e5);
vector<vector<P>> g(n + 1);
struct Edge {
int u, v, w;
};
vector<Edge> edge;
for(int i = 0, u, v, w; i < n - 1; i++) {
cin >> u >> v >> w;
assert(u >= 1 && u <= n);
assert(v >= 1 && v <= n);
assert(u != v);
assert(1 <= w <= 1e9);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
edge.push_back({u, v, w});
}
vector<vector<int>> f(20, vector<int>(n + 1));
vector<int> dep(n + 1), sum(n + 1); // sum记录深度和树上前缀的边权和，为了算出任何边都不免费的答案
auto dfs1 = [&](auto && self, int u, int fa) -> void {
dep[u] = dep[fa] + 1;
f[0][u] = fa;
for(int j = 1; j < 20; j++) {
f[j][u] = f[j - 1][f[j - 1][u]];
}
for(auto & [v, w] : g[u]) {
if(v == fa) continue;
sum[v] = sum[u] + w; // 树上边权前缀和
self(self, v, u);
}
};
dfs1(dfs1, 1, 0);
auto LCA = [&](int u, int v) -> int {
if(dep[u] < dep[v]) swap(u, v);
for(int j = 19; j >= 0; j--) {
if(dep[f[j][u]] >= dep[v]) {
u = f[j][u];
}
}
if(u == v) return u;
for(int j = 19; j >= 0; j--) {
if(f[j][u] != f[j][v]) {
u = f[j][u];
v = f[j][v];
}
}
return f[0][u];
};
int cost = 0; // 一条边都不免费的答案
vector<int> s(n + 1);
for(int i = 0, a, b; i < m; i++) {
cin >> a >> b;
assert(a >= 1 && a <= n);
assert(b >= 1 && b <= n);
int lca = LCA(a, b);
s[a] ++ ;
s[b] ++ ;
s[lca] -= 2; // 树上边差分，把边权下放给点
cost += (sum[a] + sum[b] - 2 * sum[lca]); // 算出原本的边权前缀和
}
auto dfs2 = [&](auto && self, int u, int fa) -> void {
for(auto & [v, w] : g[u]) {
if(v == fa) continue;
self(self, v, u);
s[u] += s[v]; // 树上前缀和还原差分的结果
}
};
dfs2(dfs2, 1, 0);
int mx = 0; // 记录免费一条边后减少的价值最大值
for(auto & [u, v, w] : edge) {
if(dep[u] < dep[v]) swap(u, v); // 更深那一个点的点权才是这条边的真实边权
mx = max(mx, s[u] * w);
// s[u] 是 u 被所有朋友经过的总次数，w 是这条边的权，乘起来就是这条边免费后能省下来的钱
}
cout << cost - mx << endl; // 答案就是原本的花费减去省的最多的
}
时间复杂度：。
G.小苯的奇怪最短路
题意：
给定带权无向图，求 到
的最短路，但最短路定义为经过的边里边权 最小 的边加上边权 最大 的边。
知识点：
思维，并查集， 最小生成树，枚举，贪心
题解：
让我们考虑枚举答案中的最大边 ，那么问题变成了最小边如何求。
让我们考虑最小生成树的求法，在合并连通块的过程中，如果 连通则我们直接跳过，否则连上边，并给总权加上
的权。
在本题中实际上也类似，我们给每个连通块都维护一个当前连通块中的最小边 ，接着正常执行
求最小生成树，如果当前
和
已经连通，则我们就对
所在的连通块的最小边
加上当前边
取
即可，在过程中要一直维护每个连通块中最小边的权
。
代码：
void solve() {
int n, m;
cin >> n >> m;
assert(n <= 3e5);
assert(m <= 5e5);
vector<int> fa(n + 1), mn(n + 1, 1e18);
iota(fa.begin(), fa.end(), 0LL);
auto find = [&](int x) -> int {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
};
auto merge = [&] (int u, int v, int w) -> bool {
u = find(u);
v = find(v);
fa[v] = u;
mn[u] = min(mn[u], mn[v]);
mn[u] = min(mn[u], w);
return 1;
};
struct E {
int u, v, w;
bool operator<(const E & e) const {
return w < e.w;
}
};
vector<E> edge;
for(int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
edge.push_back({u, v, w});
}
sort(edge.begin(), edge.end());
int ans = 1e18;
for(auto & [u, v, w] : edge) {
merge(u, v, w);
if(find(1) == find(n)) {
ans = min(ans, mn[find(1)] + w);
}
}
if(ans > 1e17) ans = -1;
cout << ans << endl;
}
时间复杂度：。（瓶颈在对边排序）
H. 小苯的矩阵变换
题意：
给定 个
矩阵，计算排列
的个数，满足这些矩阵按照
的顺序放置后，对任意位置都满足：第
号矩阵是由第
号矩阵通过
了某一行或者某一列得到的。并且最后一个矩阵一定是全
的。
知识点：
模拟建图，状压 计数。
题解：
首先我们考虑可以两两枚举矩阵建图，如果 可以通过
操作得到
，则我们建一条
之间的双向边，同时我们找到所有全
矩阵的编号，记作
数组。
接着问题变为了，对于 个点的一张无向图，求有多少条哈密顿路径的终点是
中的某个。事实上我们反着考虑，用
中所有点当做起点的效果是一样的。
因此我们定义数组：状压 表示目前已经走过的点状态为
，且最后一个点是
的总方案数，枚举状态和结尾点转移即可，最终答案即为
的所有第二维之和。
初始化我们只需要把所有 中的点都当一次起点即可，即：
。
代码
void solve() {
int n, m, k;
cin >> n >> m >> k;
assert(n <= 100);
assert(m <= 100);
assert(k <= 15);
k ++ ;
vector<vector<string>> g(k, vector<string>(n + 1));
vector<int> S;
for(int c = 0; c < k; c++) {
bool white = 1;
for(int i = 1; i <= n; i++) {
string s;
cin >> s;
s = " " + s;
g[c][i] = s;
for(int j = 1; j <= m; j++) {
white &= (g[c][i][j] == '0');
}
}
if(white) {
S.emplace_back(c);
}
}
if(S.empty()) {
cout << 0 << endl;
return ;
}
// vector<vector<int>> adj(k, vector<int>(k));
vector<vector<int>> adj(k);
auto addEdge = [&](int u, int v) -> bool {
vector<vector<int>> mp(n + 1, vector<int>(m + 1));
int sx = 0, sy = 0;
int ex = 0, ey = 0;
int cnt = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int x = ((g[u][i][j] - '0') ^ (g[v][i][j] - '0'));
mp[i][j] = x;
if(sx == 0 && x) {
sx = i;
sy = j;
}
if(x) {
cnt ++ ;
ex = i;
ey = j;
}
}
}
if(sx == ex && cnt == m) {
for(int j = sy; j <= ey; j++) {
if(mp[sx][j] == 0) return 0;
}
// adj[u][v] = adj[v][u] = 1;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
return 1;
} else if(sy == ey && cnt == n) {
for(int i = sx; i <= ex; i++) {
if(mp[i][sy] == 0) return 0;
}
adj[u].emplace_back(v);
adj[v].emplace_back(u);
// adj[u][v] = adj[v][u] = 1;
return 1;
}
return 0;
};
for(int u = 0; u < k; u++) {
for(int v = u + 1; v < k; v++) {
if(addEdge(u, v)) {
// cerr << u << "-" << v << endl;
}
}
}
vector<vector<int>> dp(1 << k, vector<int>(k));
for(auto & s : S) {
dp[1 << s][s] = 1;
}
for(int i = 1; i < 1 << k; i++) {
for(int j = 0; j < k; j++) {
if(dp[i][j] == 0) continue;
if((i >> j & 1) == 0) continue;
for(auto & nxt : adj[j]) {
if((i >> nxt & 1) == 0) {
dp[i | (1 << nxt)][nxt] += dp[i][j];
}
}
}
}
int ans = 0;
for(int e = 0; e < k; e++) {
ans += dp[(1 << k) - 1][e];
}
cout << ans << endl;
}
时间复杂度：。（只是上限，实际上跑不到最坏情况）
: https://ac.nowcoder.com/acm/contest/103864
投递腾讯等公司8个岗位 >
查看24道真题和解析