2026年浙江工业大学之江学院程序设计竞赛题解
A. ZZJCAMC
题目大意
输出ZZJCACM。
解题思路
按题意模拟即可。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cout << "ZZJCACM\n";
}
B. 数字改造大师
题目大意
对一个二进制数进行x次数位上的操作，最大化最后的结果。
解题思路
直接消耗次数从高位由0变1变即可，全1的时候通过奇偶判断末尾是0还是1。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int n, x;
std::cin >> n >> x;
for (int i = std::__lg(n); i >= 0 && x; i--) {
if ((n & (1 << i)) == 0) {
n |= (1 << i);
x--;
}
}
std::cout << (x & 1 ^ n) << "\n";
}
}
C. 会不会数数(hard version)
题目大意
把所有正整数拼接在一起得到一个无限长字符串，求字符串第x位是多少。
解题思路
如果按照数字长度进行分类，可以发现只要通过 位数数量 就能快速得到x是几位数，接着计算一下偏移量即可。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int x;
std::cin >> x;
x--;
i64 len = 1, cnt = 9, start = 1;
while (x > len * cnt) {
x -= len * cnt;
len++;
cnt *= 10;
start *= 10;
}
std::cout << std::to_string(start + x / len)[x % len] << "\n";
}
}
D. 会不会数数(easy version)
题目大意
把所有正整数拼接在一起得到一个无限长字符串，求字符串第x位是多少。
解题思路
easy version数据范围较小，可以通过字符串拼接的方式直接得到整个串，然后直接按索引输出即可。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::string s;
for (int i = 1; i <= 1000; i++) {
s += std::to_string(i);
}
int tt;
std::cin >> tt;
while (tt--) {
int x;
std::cin >> x;
std::cout << s[x - 1] << "\n";
}
}
E. 校园改造计划
题目大意
给定一个01矩阵，对于每块连通的1每天可以修改一个位置为0，问至少要多少天才能出现至少两个1的连通快。
解题思路
仔细思考一下我们可以发现最后的答案不会超过2，因此我们只需要简单分类讨论，检查0和1是否存在即可。可以用bfs解决，也可以从图论的角度考虑，将本题转化为对于一个全1连通块判断是否存在割点。
代码实现
// bfs做法
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
int sum = 0, x = -1, y = -1;
std::vector<std::vector<int>> g(n + 1, std::vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> g[i][j];
if (g[i][j]) {
sum++;
x = i;
y = j;
}
}
}
if (sum == 0) {
std::cout << 0 << "\n";
return 0;
}
int cnt = 0;
std::queue<std::array<int, 2>> q;
std::vector<std::vector<int>> vis(n + 1, std::vector<int>(m + 1));
std::vector<std::array<int, 2>> dire = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
q.push({x, y});
while (!q.empty()) {
auto [xx, yy] = q.front();
q.pop();
if (vis[xx][yy]) {
continue;
}
vis[xx][yy] = 1;
cnt++;
for (auto [dx, dy] : dire) {
int nx = xx + dx, ny = yy + dy;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny]) {
q.push({nx, ny});
}
}
}
if (sum != cnt) {
std::cout << 0 << "\n";
return 0;
}
if (sum <= 2) {
std::cout << sum << "\n";
return 0;
}
auto check = [&](int x, int y) -> int {
int res = 0;
for (auto [dx, dy] : dire) {
int nx = x + dx, ny = y + dy;
if (nx < 1 || nx > n || ny < 1 || ny > m || !g[nx][ny]) {
res++;
}
}
return res;
};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] && check(i, j) == 3) {
std::cout << 1 << "\n";
return 0;
}
}
}
std::cout << 2 << "\n";
}
// tarjan做法
#include <bits/stdc++.h>
using i64 = long long;
class DSU {
public:
int cnt;
std::vector<int> fa, rank, siz;
DSU(int n) : cnt(n), fa(n + 1), rank(n + 1), siz(n + 1, 1) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int x, int y) {
int X = find(x), Y = find(y);
if (X != Y) {
if (rank[X] >= rank[Y]) {
fa[Y] = X;
siz[X] += siz[Y];
if (rank[X] == rank[Y]) {
rank[X]++;
}
} else {
fa[X] = Y;
siz[Y] += siz[X];
}
cnt--;
}
}
int size() {
return cnt;
}
int count(int x) {
return siz[find(x)];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
int node = 0, cnt = 0;
std::map<std::array<int, 2>, int> mp;
std::vector<std::vector<int>> g1(n, std::vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::cin >> g1[i][j];
if (g1[i][j] == 1) {
mp[{i, j}] = ++node;
cnt++;
}
}
}
if (node == 0) {
std::cout << 0 << "\n";
return 0;
}
if (cnt == 1) {
std::cout << 1 << "\n";
return 0;
}
DSU dsu(node);
std::vector<std::array<int, 2>> dire = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::vector<std::vector<int>> g2(node + 1);
for (auto [pos, id] : mp) {
auto [x, y] = pos;
for (auto [dx, dy] : dire) {
int nx = x + dx, ny = y + dy;
if (mp.count({nx, ny})) {
int u = id, v = mp[{nx, ny}];
g2[u].push_back(v);
dsu.merge(u, v);
}
}
}
if (dsu.size() > 1) {
std::cout << 0 << "\n";
return 0;
}
int dfncnt = 0;
std::vector<int> cut(node + 1), dfn(node + 1), low(node + 1);
auto tarjan = [&](auto&& self, int u, int root) -> void {
dfn[u] = low[u] = ++dfncnt;
int child = 0;
for (int v : g2[u]) {
if (!dfn[v]) {
self(self, v, root);
low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u] && u != root) {
cut[u] = 1;
}
if (u == root) {
child++;
}
} else {
low[u] = std::min(low[u], dfn[v]);
}
}
if (child >= 2 && u == root) {
cut[u] = 1;
}
};
for (int i = 1; i <= node; i++) {
if (!dfn[i]) {
tarjan(tarjan, i, i);
}
}
for (int i = 1; i <= node; i++) {
if (cut[i]) {
std::cout << 1 << "\n";
return 0;
}
}
std::cout << 2 << "\n";
}
F. 放纵日
题目大意
给定年月日转换为数字的规则，求指定数字的下一个质数日期。
解题思路
先用筛法预处理出质数，然后注意格式转换记录质数日期，二分即可。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
const int N = 3e7 + 10;
std::bitset<N> f;
void Eratosthenes(int n) {
for (int i = 2; i <= n; i++) {
f[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (f[i]) {
for (int j = i * i; j <= n; j += i) {
f[j] = false;
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
Eratosthenes(N);
auto format = [&](int y, int m, int d) -> std::string {
std::string s;
std::string sy = std::to_string(y);
std::string sm = std::to_string(m);
std::string sd = std::to_string(d);
s += std::string(4 - sy.size(), '0') + sy;
s += std::string(2 - sm.size(), '0') + sm;
s += std::string(2 - sd.size(), '0') + sd;
return s;
};
std::map<int, std::string> mp;
std::vector<int> days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int year = 1; year <= 2026; year++) {
for (int month = 1; month <= 12; month++) {
for (int day = 1; day <= days[month] + ((!(year % 400) || (!(year % 4) && year % 100)) && month == 2); day++) {
// std::string s = std::format("{:04d}{:02d}{:02d}", year, month, day);
std::string s = format(year, month, day);
int x = std::stoi(s);
if (f[x]) {
mp[x] = s;
}
}
}
}
int tt;
std::cin >> tt;
while (tt--) {
int y, m, d;
std::cin >> y >> m >> d;
// std::string s = std::format("{:04d}{:02d}{:02d}", year, month, day);
std::string s = format(y, m, d);
int x = std::stoi(s);
std::cout << mp.upper_bound(x)->second << "\n";
}
}
G. 猴子偷桃
题目大意
给定一个排列并删除一个数，找出被删除的数字。
解题思路
标记所有出现过的数字，没被标记的就是被删除的。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
std::cin >> n;
std::vector<int> f(n + 1);
for (int i = 1; i < n; i++) {
int x;
std::cin >> x;
f[x] = 1;
}
for (int i = 1; i <= n; i++) {
if (!f[i]) {
std::cout << i << "\n";
}
}
}
H. 炒股糕手
题目大意
给定股票信息，求盈利最高且字典序最小的股票每日收益。
解题思路
根据这些信息通过简单的运算可以知道哪只股票盈利最高且字典序最小，而对于股票收益的计算实质上是静态区间加减法，可以用前缀和差分来维护。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e5 + 10;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
std::cin >> n;
std::map<std::string, i64> mp;
std::vector<std::tuple<std::string, i64, i64, i64>> data;
for (int i = 0; i < n; i++) {
std::string s;
i64 l, r, x;
std::cin >> s >> l >> r >> x;
mp[s] += (r - l + 1) * x;
data.push_back({s, l, r, x});
}
std::string S;
i64 max = LLONG_MIN;
for (auto [s, x] : mp) {
if (x > max || (x == max && s < S)) {
max = x;
S = s;
}
}
std::cout << S << "\n";
i64 L = N, R = 0;
std::vector<i64> diff(N);
for (auto [s, l, r, x] : data) {
if (s == S) {
diff[l] += x;
diff[r + 1] -= x;
L = std::min(L, l);
R = std::max(R, r);
}
}
i64 ans = 0;
for (int i = L; i <= R; i++) {
ans += diff[i];
std::cout << ans << " \n"[i == R];
}
}
I. 智慧
题目大意
给定一个字符串，找出其中ZZJC子序列的数量。
解题思路
按照题意模拟即可，需要注意Z J C它们之间有顺序要求。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::string s;
std::cin >> s;
int z1 = 0, z2 = 0, j = 0, c = 0;
for (auto ch : s) {
if (ch == 'Z') {
if (z1 == z2) {
z1++;
} else {
z2++;
}
} else if (ch == 'J' && j < z2) {
j++;
} else if (ch == 'C' && c < j) {
c++;
}
}
std::cout << c << "\n";
}
J. 上课路线
题目大意
给定多个数组，求最长的公共部分长度。
解题思路
先对数组进行哈希，然后二分长度即可。
代码实现
#include <bits/stdc++.h>
using u64 = unsigned long long;
const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
class StringHash {
public:
int P1, P2;
std::vector<u64> h1, h2, p1, p2;
StringHash() {
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// P1 = std::uniform_int_distribution<int>(128, 10000)(rng);
// P2 = std::uniform_int_distribution<int>(128, 10000)(rng);
P1 = 131;
P2 = 13331;
}
template <typename Sequence>
void build(const Sequence& seq) {
int n = seq.size();
h1.resize(n + 1, 0);
h2.resize(n + 1, 0);
p1.resize(n + 1, 1);
p2.resize(n + 1, 1);
for (int i = 1; i <= n; i++) {
h1[i] = (h1[i - 1] * P1 + seq[i - 1]) % MOD1;
h2[i] = (h2[i - 1] * P2 + seq[i - 1]) % MOD2;
p1[i] = (p1[i - 1] * P1) % MOD1;
p2[i] = (p2[i - 1] * P2) % MOD2;
}
}
std::pair<u64, u64> get(int l, int r) {
u64 hash1 = (h1[r] - h1[l - 1] * p1[r - l + 1] % MOD1 + MOD1) % MOD1;
u64 hash2 = (h2[r] - h2[l - 1] * p2[r - l + 1] % MOD2 + MOD2) % MOD2;
return {hash1, hash2};
}
};
struct pair_hash {
int operator()(const std::pair<u64, u64>& x) const {
return x.first ^ (x.second << 1);
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
std::cin >> n;
std::vector<std::vector<int>> paths(n);
for (int i = 0; i < n; i++) {
int m;
std::cin >> m;
paths[i].resize(m);
for (int j = 0; j < m; j++) {
std::cin >> paths[i][j];
}
}
std::vector<StringHash> sh(n);
for (int i = 0; i < n; i++) {
sh[i].build(paths[i]);
}
auto check = [&](int len) -> bool {
std::unordered_map<std::pair<u64, u64>, int, pair_hash> ump;
for (int i = 0; i < n; i++) {
std::unordered_set<std::pair<u64, u64>, pair_hash> ust;
for (int j = 1; j + len - 1 <= paths[i].size(); j++) {
auto hash = sh[i].get(j, j + len - 1);
if (ust.count(hash)) {
continue;
}
ump[hash]++;
ust.insert(hash);
}
}
for (auto [hash, cnt] : ump) {
if (cnt >= n) {
return true;
}
}
return false;
};
int l = 0, r = 1e5 + 10, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
std::cout << ans << "\n";
}
K. 会数数的人
题目大意
给定n个字符，可以从中反复选择k个进行任意排列组合，求字典序第x小的串。
解题思路
数据范围较小，dfs爆搜即可。
代码实现
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, k, x;
std::cin >> n >> k >> x;
std::vector<std::string> s(n), ans;
for (int i = 0; i < n; i++) {
std::cin >> s[i];
}
auto dfs = [&](auto&& self, int cnt, std::string t) -> void {
if (cnt == k) {
ans.push_back(t);
return;
}
for (int i = 0; i < n; i++) {
self(self, cnt + 1, t + s[i]);
}
};
dfs(dfs, 0, "");
std::sort(ans.begin(), ans.end());
std::cout << ans[x - 1] << "\n";
}
京公网安备 11010502036488号