历年CSP-J组第二轮题目完整解析
[CSP-J2019] 数字游戏
解题代码
// 题意：统计一个长度为8的01字符串中'1'的个数。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int sol() {
string s;
cin >> s;
int ans = 0;
// 遍历字符串中的每个字符
for (char c : s) {
if (c == '1') {
ans++;
}
}
cout << ans << endl;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J2019] 公交换乘
解题代码
// 题意概括：
// 模拟地铁和公交的计费过程。
// 坐地铁会得到一张有时效（45分钟）和票价限制（公交票价不高于地铁票价）的优惠票。
// 坐公交时，如果有多张可用优惠票，优先使用获得时间最早的那一张。
// 求总花费。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
queue<int> q[1005]; // q[i] 存储价格为 i 的地铁票的乘车时间
ll ans;
int n;
void sol() {
cin >> n;
for (int i = 0; i < n; ++i) {
int op, p, t;
cin >> op >> p >> t;
if (op == 0) { // 地铁
ans += p;
q[p].push(t);
} else { // 公交
int fnd = -1; // 记录找到的可用票对应的价格
int get = 2e9; // 记录找到的可用票中最早的出发时间
// 从 p 到 1000 遍历所有价格足够的票
for (int j = p; j <= 1000; ++j) {
// 清除该价格队列中过期的票
while (!q[j].empty() && t - q[j].front() > 45) {
q[j].pop();
}
// 如果该价格有票，且其时间戳比当前找到的更早，则更新
if (!q[j].empty() && q[j].front() < get) {
get = q[j].front();
fnd = j;
}
}
if (fnd != -1) { // 找到了可用的票
q[fnd].pop(); // 使用这张票
} else { // 未找到
ans += p; // 付费
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J2019] 纪念品
解题代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// 题意：T天，N种物品，初始有M元钱。
// 每天可以无限次买卖任何物品。
// 求T天后最多能有多少钱。
// 这可以看作一个每日的完全背包问题。
// 对于第 i 天，我们拥有 m 元，考虑如何投资能在第 i+1 天获得最多的钱。
// 将第 i 天的价格视为物品的“花费”，第 i+1 天的价格视为物品的“价值”。
// dp[k] 表示用 k 元钱在第 i 天买入，在第 i+1 天卖出后能拥有的最大金币数。
int t, n, m;
int p[105][105];
int dp[10005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t >> n >> m;
for (int i = 0; i < t; ++i) {
for (int j = 0; j < n; ++j) {
cin >> p[i][j];
}
}
// 从第一天循环到倒数第二天
for (int i = 0; i < t - 1; ++i) {
// 初始化dp数组，不买任何东西的话，钱不变
for (int k = 0; k <= m; ++k) {
dp[k] = k;
}
// 对每一种纪念品进行完全背包计算
for (int j = 0; j < n; ++j) {
// k 代表当前拥有的钱(背包容量)
for (int k = p[i][j]; k <= m; ++k) {
dp[k] = max(dp[k], dp[k - p[i][j]] + p[i+1][j]);
}
}
// 用今天所有钱m能换到的最大价值，更新为明天的钱
m = dp[m];
}
cout << m << endl;
return 0;
}
[CSP-J2019] 加工零件
解题代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// 题意：一个n个点m条边的无向图。
// q次询问，每次问a点生产L阶段零件，1号点是否需要提供原材料。
// 分析可知，a点生产L阶段零件，需要所有存在一条长度为L的路径可达的节点提供原材料。
// 这里的“路径”指的可以经过重复点和边的"walk"。
// 存在长度为L的walk，等价于 最短路d<=L 且 d和L奇偶性相同。
// 这是因为我们总可以在一条边上来回走，每次使路径长度增加2。
// 因此问题转化为，求1号点到各点a的最短奇数长路径和最短偶数长路径。
// 用一个BFS即可解决。BFS队列中的状态为(当前节点, 路径长度奇偶性)。
const int N = 100005;
int n, m, q;
vector<int> g[N];
int de[N]; // 1号点到各点的偶数最短路
int doo[N]; // 1号点到各点的奇数最短路
void bfs() {
memset(de, -1, sizeof(de));
memset(doo, -1, sizeof(doo));
queue<pair<int, int>> qu;
de[1] = 0;
qu.push({1, 0}); // {节点, 奇偶性}, 0代表偶数
while (!qu.empty()) {
auto [u, p] = qu.front();
qu.pop();
int cst;
if (p == 0) cst = de[u];
else cst = doo[u];
for (int v : g[u]) {
if (p == 0) { // 从偶数路径点u出发，到达v的路径为奇数
if (doo[v] == -1) {
doo[v] = cst + 1;
qu.push({v, 1});
}
} else { // 从奇数路径点u出发，到达v的路径为偶数
if (de[v] == -1) {
de[v] = cst + 1;
qu.push({v, 0});
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bfs();
while (q--) {
int a;
ll l;
cin >> a >> l;
bool ok = false;
if (l % 2 == 0) { // 需要偶数长度的路径
if (de[a] != -1 && de[a] <= l) {
ok = true;
}
} else { // 需要奇数长度的路径
if (doo[a] != -1 && doo[a] <= l) {
ok = true;
}
}
if (ok) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
[CSP-J2019 江西] 面积
解题代码
// 题意：比较边长为a的正方形和长宽为b,c的矩形的面积大小。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void sol() {
ll a, b, c;
cin >> a >> b >> c;
// 由于a, b, c最大可达10^9，面积会超过int范围，需要使用long long
ll s_a = a * a;
ll s_b = b * c;
if (s_a > s_b) {
cout << "Alice" << endl;
} else {
cout << "Bob" << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J2019 江西] 次大值
解题代码
/*
* 题意：给定n个正整数，计算所有 a_i % a_j (i!=j) 的值，去重后求严格次大值。
*
* 思路：
* 对输入数组去重并排序，得到递增序列 u, 大小为 m。
* 如果 m <= 1, 结果数量不足两个，输出 -1。
*
* 所有 a_i % a_j 的结果中：
* 1. 当 a_i < a_j 时，结果为 a_i。这部分能产生的最大值是 u[m-2] (通过 u[m-2] % u[m-1] 得到)。
* 2. 当 a_i > a_j 时，结果为 a_i % a_j，该值一定小于 a_j，从而小于 u[m-1]。
* 同时，a_i % a_j < a_j <= u[m-2]。
* 综上，所有结果中的最大值就是 u[m-2]。
*
* 寻找次大值，它由两类候选者决定：
* 1. a_i < a_j 情况下的次大值，即 u[m-3] (前提是 m >= 3)。
* 2. a_i > a_j 情况下的最大值。为使 a_i % a_j 最大，a_i 应取最大，即 u[m-1]。
* 所以需要计算 max(u[m-1] % u[i]) 对于所有 i < m-1。
*
* 最终答案就是这两类候选者的最大值。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end()); // 排序去重
int m = a.size();
if (m <= 1) {
cout << -1 << endl;
return 0;
}
int res = 0;
// 候选1: 来自 a_i < a_j 的次大值
if (m >= 3) {
res = a[m - 3];
}
// 候选2: 来自 a_i > a_j 的最大值
int M = a[m - 1];
for (int i = 0; i < m - 1; ++i) {
res = max(res, M % a[i]);
}
cout << res << endl;
return 0;
}
[CSP-J2019 江西] 道路拆除
题目链接：P5683 [CSP-J2019 江西] 道路拆除
解题代码
// 题意：给定一个n点m边的无权无向图，以及两个目标点s1, s2和对应的最大距离t1, t2。
// 问最多可以拆除多少条边，使得首都1到s1和s2的最短路分别不超过t1和t2。
// 这等价于求满足条件所需的最少保留边数，然后用总边数m减去它。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 3005;
const int INF = 1e9;
int n, m;
int s1, t1, s2, t2;
vector<int> adj[N];
int d0[N], da[N], db[N]; // 分别存储从1, s1, s2出发的距离
// 广度优先搜索，计算单源最短路
void bfs(int s, int d[]) {
for (int i = 1; i <= n; ++i) {
d[i] = INF;
}
queue<int> q;
q.push(s);
d[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (d[v] == INF) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
}
void sol() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> s1 >> t1 >> s2 >> t2;
// 预处理出三个源点的最短路
bfs(1, d0);
bfs(s1, da);
bfs(s2, db);
int res = INF;
// 遍历所有点i，假设它是1到s1和1到s2路径的汇合点
for (int i = 1; i <= n; ++i) {
ll p1 = (ll)d0[i] + da[i]; // 路径1->i->s1的长度
ll p2 = (ll)d0[i] + db[i]; // 路径1->i->s2的长度
if (p1 <= t1 && p2 <= t2) {
// 如果两条路径都满足时间限制，更新所需的最少边数
int cnt = d0[i] + da[i] + db[i];
res = min(res, cnt);
}
}
if (res == INF) {
cout << -1 << endl;
} else {
cout << m - res << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J2019 江西] 非回文串
题目链接：P5684 [CSP-J2019 江西] 非回文串
解题代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
* 题意：
* 给定 n 个小写字母，问有多少种排列方案，使得组成的字符串不是回文串。
* 方案不同指的是排列的下标序列不同。
*
* 解法：
* 正难则反。总方案数减去回文串的方案数。
*
* 1. 总方案数：
* n 个字符，下标有 1~n。对下标进行全排列，共有 n! 种不同的方案。
*
* 2. 回文串方案数：
* 首先，判断是否可能构成回文串。
* - 如果 n 是偶数，所有字符的出现次数必须都是偶数。
* - 如果 n 是奇数，有且仅有一个字符的出现次数是奇数。
* 如果不满足上述条件，则无法构成回文串，回文方案数为 0。
*
* 如果满足条件，我们来计算能构成回文串的方案数。
* 这个问题的核心是将问题分解为两部分：
* a. 可以构成多少种不同的回文串？
* b. 对于每一种回文串，有多少种下标排列方案可以得到它？
*
* 对于 a):
* 一个回文串由其前一半决定。设 h = n / 2。
* 前一半的字符串，是由每种字符数量的一半构成的。
* 例如，总共有 cnt['a'] 个 'a'，那么前一半就需要 cnt['a']/2 个 'a'。
* 所以，前一半是一个长度为 h 的多重集排列。
* 不同的前一半字符串数量为 h! / ( (cnt['a']/2)! * (cnt['b']/2)! * ... )。
* 这就是不同回文串的数量。
*
* 对于 b):
* 对于一个确定的目标串 S (比如 "abccba")，我们要从原始的 n 个字符 c_1, ..., c_n 中，
* 选择对应的字符来填充。假设 S 需要 k_a 个 'a', k_b 个 'b' ...
* 我们原始字符中，'a' 有 cnt['a'] 个，'b' 有 cnt['b'] 个 ...
* 将 cnt['a'] 个 'a' 安排到 S 中 k_a 个 'a' 的位置上，有 cnt['a']! 种方案。
* 所以总共有 cnt['a']! * cnt['b']! * ... 种方案。
*
* 因此，回文串方案数 = (不同回文串的数量) * (每种串的构成方案数)。
* P_pal = (h! / (Π (cnt[c]/2)!)) * (Π cnt[c]!)
*
* 3. 最终答案：
* (n! - P_pal) mod (10^9 + 7)。
* 所有计算都在模意义下进行，需要预处理阶乘和阶乘逆元。
*/
const int N = 2005;
const int mod = 1e9 + 7;
ll fac[N];
ll ifac[N];
int cnt[26];
// 快速幂
ll qpo(ll a, ll b) {
ll res = 1;
a %= mod;
while (b) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
// 预处理阶乘和逆元
void pre(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = (fac[i - 1] * i) % mod;
}
ifac[n] = qpo(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
ifac[i] = (ifac[i + 1] * (i + 1)) % mod;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string s;
cin >> s;
for (char c : s) {
cnt[c - 'a']++;
}
pre(n);
int odd = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i] % 2 != 0) {
odd++;
}
}
ll pal = 0;
bool ok = false;
// 检查是否可能构成回文串
if (n % 2 == 0) {
if (odd == 0) ok = true;
} else {
if (odd == 1) ok = true;
}
if (ok) {
int h = n / 2;
ll p_s = fac[h]; // 计算不同回文串数量
for (int i = 0; i < 26; i++) {
p_s = (p_s * ifac[cnt[i] / 2]) % mod;
}
ll ways = 1; // 计算每种串的构成方案数
for (int i = 0; i < 26; i++) {
ways = (ways * fac[cnt[i]]) % mod;
}
pal = (p_s * ways) % mod;
}
ll tot = fac[n];
ll ans = (tot - pal + mod) % mod;
cout << ans << endl;
return 0;
}
[CSP-J2020] 优秀的拆分
解题代码
// 题意概括:
// 将一个正整数 n 拆分成若干个不同的 2 的正整数次幂之和。
// 如果 n 是奇数，其二进制表示必然包含 2^0=1，不满足“正整数次幂”的要求，无解。
// 如果 n 是偶数，其唯一的二进制表示就是答案。
// 从大到小输出拆分出的数。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<int> ans;
void sol() {
cin >> n;
if (n % 2 != 0) { // 奇数必须包含 2^0，不符合题意，无解
cout << -1 << endl;
return;
}
// 从大到小贪心选取 2 的幂
for (int p = 1 << 24; p >= 2; p /= 2) {
if (n >= p) {
ans.push_back(p);
n -= p;
}
}
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
}
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J2020] 直播获奖
解题代码
// 题意简述:
// 逐一给出n个选手的成绩，在每次给出成绩后，计算当前的获奖分数线并输出。
// 获奖率为w%，获奖人数为 max(1, floor(p * w/100))，p为当前已公布成绩的人数。
// 分数线为排名为获奖人数的选手的成绩。
// 解题思路:
// 选手成绩范围为0到600，值域很小。
// 可以用一个大小为601的桶（数组）来记录每个分数出现的次数。
// 每次读入新成绩，对应桶的计数加一。
// 然后计算出当前获奖人数k。
// 从高分到低分（600到0）遍历桶，累加人数，
// 当累计人数第一次大于等于k时，当前分数即为分数线。
// 时间复杂度为O(n * 分数范围)，可以通过此题。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int S = 601;
int n, w;
int cnt[S];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; ++i) {
int s;
cin >> s;
cnt[s]++;
int k = max(1, i * w / 100);
int sum = 0;
for (int j = 600; j >= 0; --j) {
sum += cnt[j];
if (sum >= k) {
cout << j << " ";
break; // 找到分数线
}
}
}
cout << endl;
return 0;
}
[CSP-J2020] 表达式
解题代码
/*
* 题意: 给定一个后缀表达式和变量初值，多次询问翻转某个变量后表达式的值。
*
* 思路:
* 暴力地对每次询问都重新计算表达式的值会超时。
* 核心思想是预处理出每个变量的改变是否会影响最终结果。
* 1. 建树 + 初值计算: 后缀表达式可以很方便地建成一棵表达式树。
* 在建树的同时，利用栈进行计算，求出每个子表达式（节点）的初始值。
* 2. 影响传递分析: 从根节点开始进行一次深度优先搜索(DFS)。
* 根节点的结果就是最终结果，所以根节点的改变一定会影响最终结果（标记为有影响）。
* 对于一个有影响的父节点P，分析其子节点C的影响：
* - 若P是 '!'，则C的改变必然导致P的改变，所以C也有影响。
* - 若P是 '&' 或 '|'，C的影响取决于其兄弟节点S的值。
* 例如，对于 A&B，若B为1，则A的改变会影响结果；若B为0，则结果恒为0，A无影响。
* 或运算同理。
* 这样一次DFS就可以预处理出所有变量节点的影响情况。
* 3. 回答询问: 对于每个询问，查询对应变量节点的影响标记。
* 若有影响，输出与初始表达式结果相反的值；否则输出初始结果。
* 每次询问的时间复杂度为O(1)。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 表达式树节点
struct N {
int op; // 0:变量, 1:!, 2:&, 3:|
int v; // 节点的值
bool f; // 改变此节点是否影响最终结果
int l, r; // 左右子节点索引
int vid; // 如果是变量节点，其下标
};
vector<N> t; // 存储表达式树
map<int, int> vtn; // 变量下标 -> 树中节点索引
// DFS计算每个节点的影响
void dfs(int u) {
if (t[u].l == -1) { // 叶子节点
return;
}
if (t[u].f) { // 只有当父节点有影响时，子节点才可能产生影响
int c1 = t[u].l;
int c2 = t[u].r;
if (t[u].op == 1) { // '!'
t[c1].f = true;
} else if (t[u].op == 2) { // '&'
if (t[c2].v == 1) t[c1].f = true; // a&1, a有影响
if (t[c1].v == 1) t[c2].f = true; // 1&b, b有影响
} else if (t[u].op == 3) { // '|'
if (t[c2].v == 0) t[c1].f = true; // a|0, a有影响
if (t[c1].v == 0) t[c2].f = true; // 0|b, b有影响
}
}
dfs(t[u].l);
if (t[u].r != -1) {
dfs(t[u].r);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
getline(cin, s);
vector<string> tok;
string tmp;
for (char c : s) {
if (c == ' ') {
if (!tmp.empty()) tok.push_back(tmp);
tmp.clear();
} else {
tmp += c;
}
}
if (!tmp.empty()) tok.push_back(tmp);
int n;
cin >> n;
vector<int> iv(n + 1);
for (int i = 1; i <= n; ++i) cin >> iv[i];
stack<int> st;
for (const auto& T : tok) {
if (T[0] == 'x') {
int id = stoi(T.substr(1));
t.push_back({0, iv[id], false, -1, -1, id});
vtn[id] = t.size() - 1;
st.push(t.size() - 1);
} else {
int c1 = st.top(); st.pop();
if (T[0] == '!') {
t.push_back({1, !t[c1].v, false, c1, -1, 0});
} else {
int c2 = st.top(); st.pop();
swap(c1, c2); // 后缀表达式先弹出的是右操作数
if (T[0] == '&') {
t.push_back({2, t[c1].v & t[c2].v, false, c1, c2, 0});
} else { // '|'
t.push_back({3, t[c1].v | t[c2].v, false, c1, c2, 0});
}
}
st.push(t.size() - 1);
}
}
int rt = st.top();
int ir = t[rt].v;
t[rt].f = true; // 根节点总是有影响的
dfs(rt);
int qn;
cin >> qn;
while (qn--) {
int i;
cin >> i;
cout << (t[vtn[i]].f ? !ir : ir) << "\n";
}
return 0;
}
[CSP-J2020] 方格取数
解题代码
/*
* 题意:
* 在一个 n x m 的方格图中，从左上角 (1,1) 走到右下角 (n,m)。
* 每一步可以向右、向上或向下，不能重复经过同一个格子。
* 求经过格子中的整数之和的最大值。
*
* 思路:
* 动态规划。dp[i][j][k] 表示到达 (i,j) 的最大和。
* k=0: 从左边 (i, j-1) 到达。
* k=1: 从上边 (i-1, j) 到达。
* k=2: 从下边 (i+1, j) 到达。
* 按列计算，防止回头路。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1005;
const ll NINF = -1e18; // 代表负无穷
int n, m;
int a[MAX][MAX];
ll dp[MAX][MAX][3];
void slv() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
// 初始化dp数组
for (int i = 0; i <= n + 1; ++i) {
for (int j = 0; j <= m + 1; ++j) {
dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = NINF;
}
}
// 虚拟起点在 (1,0)，分数为0
dp[1][0][0] = 0;
for (int j = 1; j <= m; ++j) {
// k=0: 从左边过来
for (int i = 1; i <= n; ++i) {
ll p = max({dp[i][j - 1][0], dp[i][j - 1][1], dp[i][j - 1][2]});
if (p > NINF) {
dp[i][j][0] = p + a[i][j];
}
}
// k=1: 从上面过来 (向下走)
for (int i = 1; i <= n; ++i) {
ll p = max(dp[i - 1][j][0], dp[i - 1][j][1]);
if (p > NINF) {
dp[i][j][1] = p + a[i][j];
}
}
// k=2: 从下面过来 (向上走)
for (int i = n; i >= 1; --i) {
ll p = max(dp[i + 1][j][0], dp[i + 1][j][2]);
if (p > NINF) {
dp[i][j][2] = p + a[i][j];
}
}
}
// 终点 (n,m) 不可能从下方(n+1,m)到达
ll ans = max(dp[n][m][0], dp[n][m][1]);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slv();
return 0;
}
[CSP-J 2021] 分糖果
解题代码
// 题意概括:
// 在 [L, R] 区间内选择一个整数 k，使得 k % n 的值最大。
// k % n 的值随 k 的增加而周期性地从 0 递增到 n-1。
// 如果 [L, R] 区间跨越了 n 的某个倍数，那么这个区间内一定可以取到余数为 n-1 的 k。
// 否则，该区间内 k % n 的值是单调递增的，最大值在 k=R 时取到。
// 判断是否跨越 n 的倍数，只需比较 L/n 和 R/n 的整数商是否相等。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, l, r;
void sol() {
cin >> n >> l >> r;
// 如果 L 和 R 除以 n 的整数商相同，说明它们在同一个长度为 n 的区间内
// 在这种情况下，余数是单调递增的，因此最大余数在 k=R 时取得
if (l / n == r / n) {
cout << r % n << endl;
} else {
// 如果商不同，说明区间 [L, R] 至少跨越了一个 n 的倍数
// 这意味着区间内必然存在一个数 k，使得 k % n = n - 1，这是最大可能的余数
cout << n - 1 << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J 2021] 插入排序
解题代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 8005;
const int B = 450; // 块大小
int n, q;
ll a[N];
struct Op {
int t, x;
ll v;
};
struct Elem {
ll v;
int p;
bool operator<(const Elem& o) const {
if (v != o.v) return v < o.v;
return p < o.p;
}
};
Elem sa[N];
Op ops[200005];
void sol() {
for (int i = 0; i < q; i += B) {
int end = min(i + B, q);
for (int j = 1; j <= n; ++j) {
sa[j] = {a[j], j};
}
sort(sa + 1, sa + n + 1);
for (int j = i; j < end; ++j) {
if (ops[j].t == 2) {
int qp = ops[j].x;
ll qv = a[qp];
// 确定查询时的真实值
for (int k = i; k < j; ++k) {
if (ops[k].t == 1 && ops[k].x == qp) {
qv = ops[k].v;
}
}
Elem qe = {qv, qp};
// 在块开始时的数组中计算排名
auto it = lower_bound(sa + 1, sa + n + 1, qe);
ll ans = (it - (sa + 1));
map<int, ll> chg;
// 根据块内修改进行修正
for (int k = i; k < j; ++k) {
if (ops[k].t == 1) {
int p = ops[k].x;
ll old_v, new_v;
new_v = ops[k].v;
// 找到修改前的旧值
if (chg.count(p)) {
old_v = chg[p];
} else {
old_v = a[p];
}
if ((Elem{old_v, p}) < qe) {
ans--;
}
if ((Elem{new_v, p}) < qe) {
ans++;
}
chg[p] = new_v;
}
}
cout << ans + 1 << "\n";
}
}
// 应用本块的全部修改
for (int j = i; j < end; ++j) {
if (ops[j].t == 1) {
a[ops[j].x] = ops[j].v;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 0; i < q; ++i) {
cin >> ops[i].t >> ops[i].x;
if (ops[i].t == 1) {
cin >> ops[i].v;
}
}
sol();
return 0;
}
[CSP-J 2021] 网络连接
解题代码
/*
* 题意：
* 模拟 n 个网络连接操作。计算机分为服务机(Server)和客户机(Client)。
* 每个操作提供一个类型和一个地址串。
* 需要先验证地址串 `a.b.c.d:e` 的格式是否规范：
* 1. a,b,c,d 在 [0, 255] 内, e 在 [0, 65535] 内。
* 2. 均不能有前导零 (除非是单个0)。
* 3. 格式严格，不多不少3个'.'和1个':'，且'.'在':'之前。
*
* 如果地址串非法，输出 ERR。
*
* 如果地址合法：
* - Server:
* - 若地址未被占用，则成功建立，输出 OK，记录该地址和编号。
* - 若地址已被占用，则失败，输出 FAIL。
* - Client:
* - 若地址存在已成功的Server，则连接成功，输出该Server的编号。
* - 若地址不存在对应Server，则连接失败，输出 FAIL。
*
* 解法：
* 这是一个纯模拟题。核心是编写一个函数来验证地址串的合法性。
* 我们可以用一个 map<string, int> 来存储已成功建立连接的服务机地址及其编号。
* 循环 n 次，对每个操作：
* 1. 调用地址验证函数。若非法，输出 ERR。
* 2. 若合法，根据是 Server 还是 Client 进行处理：
* - Server: 查 map。若存在，输出 FAIL。否则，输出 OK 并将地址和编号存入 map。
* - Client: 查 map。若存在，输出其编号。否则，输出 FAIL。
*
* 地址验证函数可以手动解析字符串，查找3个'.'和1个':'的位置，分割出5个数字字符串，
* 然后对每个数字字符串检查前导零、纯数字、范围等。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 验证地址串的一个部分
bool vpc(string s, int lim) {
if (s.empty()) return false;
for (char c : s) {
if (!isdigit(c)) return false;
}
if (s.length() > 1 && s[0] == '0') return false;
ll val = 0;
for (char c : s) {
val = val * 10 + (c - '0');
if (val > lim) return false; // 防止溢出和超限
}
return val <= lim;
}
// 验证整个地址串
bool vld(string ad) {
vector<int> dts;
int cln = -1;
for (int i = 0; i < ad.length(); ++i) {
if (ad[i] == '.') {
dts.push_back(i);
} else if (ad[i] == ':') {
if (cln != -1) return false; // 多个冒号
cln = i;
}
}
if (dts.size() != 3 || cln == -1) return false;
// 保证分隔符顺序正确
if (!(dts[0] < dts[1] && dts[1] < dts[2] && dts[2] < cln)) return false;
string s1 = ad.substr(0, dts[0]);
string s2 = ad.substr(dts[0] + 1, dts[1] - dts[0] - 1);
string s3 = ad.substr(dts[1] + 1, dts[2] - dts[1] - 1);
string s4 = ad.substr(dts[2] + 1, cln - dts[2] - 1);
string s5 = ad.substr(cln + 1);
if (!vpc(s1, 255)) return false;
if (!vpc(s2, 255)) return false;
if (!vpc(s3, 255)) return false;
if (!vpc(s4, 255)) return false;
if (!vpc(s5, 65535)) return false;
return true;
}
void sol(int n) {
map<string, int> srv;
for (int i = 1; i <= n; ++i) {
string op, ad;
cin >> op >> ad;
if (!vld(ad)) {
cout << "ERR\n";
continue;
}
if (op[0] == 'S') { // Server
if (srv.count(ad)) {
cout << "FAIL\n";
} else {
srv[ad] = i;
cout << "OK\n";
}
} else { // Client
if (srv.count(ad)) {
cout << srv[ad] << "\n";
} else {
cout << "FAIL\n";
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
sol(n);
return 0;
}
[CSP-J 2021] 小熊的果篮
解题代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 2e5 + 5;
int n;
int v[MAX];
int l[MAX], r[MAX];
bool b[MAX];
void sol() {
vector<int> c;
v[0] = -1; // 哨兵, 方便处理边界
for (int i = 1; i <= n; ++i) {
l[i] = i - 1;
r[i] = i + 1;
if (v[i] != v[i - 1]) {
c.push_back(i);
}
}
r[n] = 0;
while (!c.empty()) {
sort(c.begin(), c.end());
for (int i = 0; i < c.size(); ++i) {
cout << c[i] << (i == c.size() - 1 ? "" : " ");
}
cout << "\n";
for (int p : c) {
b[p] = true;
}
vector<int> x;
for (int p : c) {
int R_p = r[p];
if (R_p != 0 && !b[R_p]) {
int L_p = l[p];
// 找到 R_p 实际上的左邻居
while (L_p != 0 && b[L_p]) {
L_p = l[L_p];
}
if (L_p == 0 || v[L_p] != v[R_p]) {
x.push_back(R_p);
}
}
}
// 更新链表，将被拿走的水果从链表中移除
for (int p : c) {
int L_p = l[p];
int R_p = r[p];
if (L_p != 0) {
r[L_p] = R_p;
}
if (R_p != 0) {
l[R_p] = L_p;
}
}
// 清理标记数组
for (int p : c) {
b[p] = false;
}
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
c = x;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i];
}
sol();
return 0;
}
[CSP-J 2022] 乘方
解题代码
/*
* 题意：
* 计算 a^b，如果结果大于 10^9，则输出 -1，否则输出其值。
*
* 解法：
* 由于 b 的值可能很大(最高可达 10^9)，直接循环 b 次进行乘法会超时。
* 因此，我们需要使用 O(log b) 复杂度的快速幂算法。
*
* 快速幂的核心思想是利用 b 的二进制表示来加速计算。
* 例如 a^9 = a^(1001_2) = a^(8+1) = a^8 * a^1。
* 我们在计算过程中迭代地将底数平方(a -> a^2 -> a^4 -> a^8 ...)，
* 同时根据 b 的二进制位来决定是否将当前的底数乘入结果。
*
* 在本题中，我们不需要取模，而是要计算真实值。关键在于，在每一步乘法之前，
* 都要检查结果是否会超过 10^9 这个上限。
*
* - 在 ans = ans * a 之前，检查 ans > 10^9 / a 是否成立。
* - 在 a = a * a 之前，检查 a > 10^9 / a 是否成立。
*
* 如果任何一步乘法将导致结果超过 10^9，我们就可以提前判断并输出 -1。
* 此外，需要特别处理 a = 1 的情况，此时结果永远是 1。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll lim = 1e9;
void sol() {
ll a, b;
cin >> a >> b;
if (a == 1) {
cout << 1 << endl;
return;
}
ll ans = 1;
while (b > 0) {
if (b & 1) {
// 检查 ans * a 是否会超过上限 lim
if (ans > lim / a) {
cout << -1 << endl;
return;
}
ans *= a;
}
b >>= 1;
// 如果循环还未结束，则需要计算 a*a
if (b > 0) {
// 检查 a * a 是否会超过上限 lim
if (a > lim / a) {
cout << -1 << endl;
return;
}
a *= a;
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J 2022] 解密
解题代码
/*
* 题意：
* 给定 k 组 n, e, d，求正整数 p, q 满足：
* 1. n = p * q
* 2. e * d = (p - 1)(q - 1) + 1
*
* 解法：
* 这是一个数学问题。我们可以通过化简给定的两个方程来求解。
*
* 对第二个方程进行展开：
* e * d = (p - 1)(q - 1) + 1
* e * d = pq - p - q + 1 + 1
* e * d = pq - (p + q) + 2
*
* 将第一个方程 n = pq 代入上式：
* e * d = n - (p + q) + 2
*
* 移项得到 p + q 的表达式：
* p + q = n - e * d + 2
*
* 题目中给了一个提示性的定义 m = n - e * d + 2。
* 所以我们有了一个关于 p 和 q 的方程组：
* 1. p + q = m
* 2. p * q = n
*
* 这是经典的韦达定理应用场景。p 和 q 可以看作是某个一元二次方程 x^2 - (p+q)x + pq = 0 的两个根。
* 代入 m 和 n，方程为：
* x^2 - mx + n = 0
*
* 我们可以用求根公式解这个方程：
* x = (m ± sqrt(m^2 - 4n)) / 2
*
* 令判别式 Δ = m^2 - 4n。
* 要使 p, q 有正整数解，需要满足几个条件：
* 1. Δ 必须大于等于 0，否则方程无实数解。
* 2. Δ 必须是一个完全平方数，否则解是无理数。
* 3. (m ± sqrt(Δ)) 必须是偶数，才能被2整除得到整数解。(实际上，如果Δ是整数的完全平方数，这个条件自动满足，因为 m 和 sqrt(Δ) 的奇偶性必然相同)
*
* 算法步骤：
* 对于每组查询：
* 1. 计算 m = n - e * d + 2。
* 2. 计算判别式 Δ = m*m - 4*n。
* 3. 如果 Δ < 0，无解。
* 4. 计算 Δ 的整数平方根 s = round(sqrt(Δ))。如果 s*s != Δ，说明 Δ 不是完全平方数，无解。
* 5. 否则，解存在，p = (m - s) / 2, q = (m + s) / 2。
* 6. 由于要求 p <= q，这个解的顺序正好。输出 p 和 q 即可。
*
* 注意数据范围，n 和 e*d 可能很大，需要使用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {
ll n, e, d;
cin >> n >> e >> d;
ll ed = e * d;
ll m = n - ed + 2;
// 判别式 delta = m^2 - 4n
ll del = m * m - 4 * n;
if (del < 0) {
cout << "NO\n";
return;
}
// 求整数平方根，使用 long double 保证精度
ll s = round(sqrtl((long double)del));
// 检查 s 是否为正确的整数平方根
if (s * s != del) {
cout << "NO\n";
return;
}
// 求解 p 和 q
// m 和 s 奇偶性相同, m-s 一定是偶数
ll p = (m - s) / 2;
ll q = (m + s) / 2;
// 验证解是否正确，p,q为正整数且乘积为n
if (p > 0 && q > 0 && p * q == n) {
cout << p << " " << q << "\n";
} else {
cout << "NO\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k;
cin >> k;
while (k--) {
sol();
}
return 0;
}
[CSP-J 2022] 逻辑表达式
解题代码
// 题意概括:
// 对一个包含 '0','1','&','|','(',')' 的逻辑表达式求值，并统计短路次数。
// 运算规则: `()` 优先级最高，然后是 `&`，最后是 `|`，同级从左到右。
// 短路规则:
// 1. a & b: 若 a 的值为 0，则 b 不再计算，这计为一次 '&' 短路。
// 2. a | b: 若 a 的值为 1，则 b 不再计算，这计为一次 '|' 短路。
// 3. 如果一个表达式因外层短路而未被计算，其内部的潜在短路也不被统计。
//
// 这是一个经典的表达式求值问题，带有副作用（短路计数）。
// 此类问题最自然的解法是递归下降分析法。
// 我们可以根据 `expr -> term -> factor` 的语法结构进行递归解析。
// 在解析 `a|b` 和 `a&b` 时，先求出左操作数 a 的值，
// 然后根据 a 的值判断是否发生短路，再决定是否继续求右操作数 b。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Res 结构体用于封装一个子表达式的计算结果
// v: 表达式的值 (0 或 1)
// a: & 短路次数
// o: | 短路次数
struct Res {
int v, a, o;
};
string s;
int pos;
// 函数前向声明，因为 expr, term, fact 存在相互递归调用
Res expr();
Res term();
Res fact();
// 解析一个因子 (factor)
// factor 的定义: '0', '1', 或被括号包裹的表达式
// factor ::= '0' | '1' | '(' expr ')'
Res fact() {
char c = s[pos];
if (c == '(') {
pos++; // 跳过 '('
Res res = expr();
pos++; // 跳过 ')'
return res;
}
pos++; // 跳过 '0' 或 '1'
return {c - '0', 0, 0};
}
// 解析一个项 (term)，由 '&' 连接
// term ::= factor { '&' factor }
Res term() {
Res res = fact();
while (pos < s.length() && s[pos] == '&') {
pos++; // 跳过 '&'
if (res.v == 0) { // 发生 '&' 短路
res.a++;
fact(); // 需调用解析函数来正确跳过右侧表达式
} else {
Res rhs = fact();
res.v &= rhs.v;
res.a += rhs.a;
res.o += rhs.o;
}
}
return res;
}
// 解析一个表达式 (expr)，由 '|' 连接
// expr ::= term { '|' term }
Res expr() {
Res res = term();
while (pos < s.length() && s[pos] == '|') {
pos++; // 跳过 '|'
if (res.v == 1) { // 发生 '|' 短路
res.o++;
term(); // 需调用解析函数来正确跳过右侧表达式
} else {
Res rhs = term();
res.v |= rhs.v;
res.a += rhs.a;
res.o += rhs.o;
}
}
return res;
}
void sol() {
cin >> s;
pos = 0;
Res ans = expr();
cout << ans.v << endl;
cout << ans.a << " " << ans.o << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
[CSP-J 2022] 上升点列
解题代码
/*
* 题意:
* 给定n个点和k个可自由添加的点，找一个x,y坐标均单调不减的序列，求其最大长度。
* 序列中相邻点欧几里得距离为1，即只能向右或向上移动一格。
*
* 思路:
* 动态规划。将点排序后，dp[i][j]表示以p_i结尾、用掉j个自由点的最长路径。
* 路径可以从一个自由点序列开始，也可以从另一个给定点p_m转移而来。
* 转移时，连接p_m和p_i的成本是曼哈顿距离减1，路径长度增加曼哈顿距离。
* 最后，对于一个算出的路径，剩余的自由点都可以加在末尾。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pt {
ll x, y;
};
// 按x, y坐标排序
bool cmp(const Pt& a, const Pt& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int n;
ll k;
Pt p[505];
ll dp[505][105];
void slv() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> p[i].x >> p[i].y;
}
sort(p + 1, p + n + 1, cmp);
// 初始化dp数组
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
// 路径可以由j个自由点开始，最后连接到p_i，长度为j+1
dp[i][j] = j + 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int m = 1; m < i; ++m) {
// p[m].x <= p[i].x 已由排序保证
if (p[m].y > p[i].y) {
continue;
}
ll dx = p[i].x - p[m].x;
ll dy = p[i].y - p[m].y;
ll d = dx + dy;
// 连接 p_m 和 p_i 需要 d-1 个自由点
if (d > 0) {
ll cst = d - 1;
if (cst <= k) {
for (int j = cst; j <= k; ++j) {
ll pk = j - cst; // 到达p_m时使用的自由点数
dp[i][j] = max(dp[i][j], dp[m][pk] + d);
}
}
}
}
}
ll ans = 0;
// 包含至少一个给定点的路径
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
// 路径长度dp[i][j]，剩余k-j个自由点可以加在末尾
ans = max(ans, dp[i][j] + k - j);
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slv();
return 0;
}
[CSP-J2022 山东] 植树节
题目链接：P11853 [CSP-J2022 山东] 植树节
解题代码
// 题意：给出 n 个区间 [a, b]，求在所有整数点上，被区间覆盖次数的最大值。
// 这是一个经典的差分问题。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 定义一个足够大的数组来做差分，坐标最大到 10^6
// d[b+1] 需要访问到 10^6 + 1，所以数组大小至少为 10^6 + 2
const int N = 1000005;
int d[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int mxb = 0; // 记录最大的右端点，可以优化遍历范围
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
d[a]++;
d[b + 1]--; // 区间[a,b]的影响，在b+1处消除
mxb = max(mxb, b);
}
int ans = 0;
int cur = 0;
// 遍历求前缀和，得到每个点的实际覆盖次数，同时找出最大值
for (int i = 0; i <= mxb; ++i) {
cur += d[i];
ans = max(ans, cur);
}
cout << ans << endl;
return 0;
}
[CSP-J2022 山东] 宴会
解题代码
/*
* 题意概括:
* n个人位于数轴上不同的点x_i，每个人需要t_i的时间打扮。
* 他们要选择一个宴会地点x_0，使得所有人到达所需时间的最大值最小。
* 第i个人到达x_0的总时间为 |x_i - x_0| + t_i。
* 求最优的x_0。
*
* 解法:
* 设宴会开始时间为T，则对任意一个人i，必须满足 |x_i - x_0| + t_i <= T。
* 变形得 x_i + t_i - T <= x_0 <= x_i - t_i + T。
* 为了让x_0有解，所有人的可行区间必须有交集。
* 即 max(x_i + t_i - T) <= min(x_j - t_j + T)。
* 令 ms = max(x_i + t_i), md = min(x_j - t_j)。
* 得 ms - T <= md + T，即 T >= (ms - md) / 2。
* 最小的T在等号成立时取到，此时x_0的区间缩为一个点。
* x_0 = ms - T = ms - (ms - md) / 2 = (ms + md) / 2。
* 所以，我们只需遍历所有人，求出ms和md，即可算出唯一的x_0。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {
int n;
cin >> n;
vector<int> x(n), p(n);
for (int i = 0; i < n; ++i) cin >> x[i];
for (int i = 0; i < n; ++i) cin >> p[i];
// ms存储max(x_i + t_i), md存储min(x_i - t_i)
ll ms = (ll)x[0] + p[0];
ll md = (ll)x[0] - p[0];
for (int i = 1; i < n; ++i) {
ll s = (ll)x[i] + p[i];
ll d = (ll)x[i] - p[i];
if (s > ms) ms = s;
if (d < md) md = d;
}
// 计算并输出 x0 = (ms + md) / 2
ll sm = ms + md;
if (sm % 2 == 0) {
cout << sm / 2 << "\n";
} else {
// 如果和为奇数，结果是.5，按要求格式化输出
cout << fixed << setprecision(1) << (double)sm / 2.0 << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tcs;
cin >> tcs;
while (tcs--) {
sol();
}
return 0;
}
[CSP-J2022 山东] 部署
解题代码
/*
* 题意概括:
* 给定一棵以1为根的n个节点的树，每个节点有初始兵力。
* 存在两种操作：
* 1. 对指定节点x及其整个子树的兵力增加y。
* 2. 对指定节点x及其所有直接邻居（父节点和子节点）的兵力增加y。
* 经过m次操作后，回答q次询问，每次询问一个节点的最终兵力。
*
* 解法:
* 采用离线处理的思想，先记录所有修改，最后计算结果并回答询问。
*
* 对于操作1 (子树加):
* 使用数组 b1 记录。对于操作(1 x y)，执行 b1[x] += y。
* 完成所有记录后，通过一次从根节点开始的DFS，将父节点的b1值累加到子节点上。
* 这样，每个节点u的b1值就等于路径(root -> u)上所有节点的初始b1值之和，即为操作1对u的总贡献。
*
* 对于操作2 (邻居加):
* 使用数组 b2 记录。对于操作(2 x y)，执行 b2[x] += y。
*
* 最终计算:
* 1. DFS建树，确定父子关系。
* 2. 读入m个操作，填充b1和b2数组。
* 3. DFS传递b1的贡献。
* 4. 将初始兵力a与b1的贡献相加。
* 5. 遍历所有节点i，若b2[i]非零，将其值加到i, fa[i]及i的所有子节点的兵力上。
* 6. 回答q次询问。
*
* 兵力总和可能很大，需使用long long。
* 整体复杂度为 O(N+M+Q)。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000005;
int n;
int m;
int q;
ll a[N]; // 存储兵力
vector<int> e1[N]; // 初始邻接表
vector<int> e2[N]; // 子节点邻接表
int fa[N]; // 父节点数组
ll b1[N]; // 操作1的贡献
ll b2[N]; // 操作2的贡献
// 建树，确定父子关系
void bld(int u, int p) {
fa[u] = p;
for (int v : e1[u]) {
if (v == p) continue;
e2[u].push_back(v);
bld(v, u);
}
}
// DFS传递操作1的贡献
void prop(int u) {
for (int v : e2[u]) {
b1[v] += b1[u]; // 子节点继承父节点的累积贡献
prop(v);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
e1[u].push_back(v);
e1[v].push_back(u);
}
bld(1, 0); // 以1为根建树
cin >> m;
while (m--) {
int p, x;
ll y;
cin >> p >> x >> y;
if (p == 1) {
b1[x] += y;
} else {
b2[x] += y;
}
}
prop(1); // 传递操作1的子树贡献
// 合并操作1的贡献
for (int i = 1; i <= n; ++i) {
a[i] += b1[i];
}
// 合并操作2的贡献
for (int i = 1; i <= n; ++i) {
if (b2[i] == 0) continue;
a[i] += b2[i]; // 对中心点i
if (fa[i] != 0) {
a[fa[i]] += b2[i]; // 对父节点
}
for (int v : e2[i]) {
a[v] += b2[i]; // 对所有子节点
}
}
cin >> q;
while (q--) {
int x;
cin >> x;
cout << a[x] << "\n";
}
return 0;
}
[CSP-J2022 山东] 吟诗
解题代码
// 题意: 统计长度为N(元素1-10)的序列中, 存在三段连续子数组和分别为X,Y,Z的方案数.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int p = 998244353;
int n, m, x, y, z, e;
int f[41][1 << 17];
ll ans = 1;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> x >> y >> z;
// 核心思想: 正难则反. 总方案数(10^N)减去不满足条件的方案数.
// 我们用状压DP来统计不满足条件的方案数.
// f[i][s]: 长度为i的序列, 其所有后缀和的集合由位掩码s表示的方案数.
// s的第k位为1, 表示存在一个后缀, 其和为 k+1.
// 我们只需要关心和最大为 x+y+z 的后缀, 所以用 m 进行按位与操作来限制状态.
m = (1 << (x + y + z)) - 1;
// "妙手"出现的条件是: 存在i<j<k<l, 使sum(i..j-1)=X, sum(j..k-1)=Y, sum(k..l-1)=Z.
// 这等价于在l-1位置, 同时存在和为 Z, Y+Z, X+Y+Z 的后缀.
// e就是这个目标状态的掩码.
e = (1 << (z - 1)) | (1 << (y + z - 1)) | (1 << (x + y + z - 1));
f[0][0] = 1; // 初始条件: 长度为0的序列, 后缀和集合为空, 方案数为1.
// i: 枚举序列长度
for (int i = 1; i <= n; i++, ans = ans * 10ll % p) { // ans顺便计算总方案数
// j: 枚举上一轮的状态 (长度为i-1时的后缀和集合)
for (int j = 0; j <= m; j++) {
if (!f[i - 1][j]) continue; // 从可达状态转移
// k: 枚举新添加的数字 (1到10)
for (int k = 1; k <= 10; k++) {
// 计算新状态s:
// 1. (j << k): 原有后缀和S都变为S+k, 对应掩码左移k位.
// 2. | (1 << (k-1)): 新增一个值为k的后缀, 对应掩码第k-1位置1.
int s = ((j << k) | (1 << (k - 1))) & m;
// (s | e) != s 等价于 (s & e) != e, 检查s是否包含了e的所有位.
// 如果s中尚未凑齐目标状态e, 说明这个长为i的序列还不算"妙手", 计入f[i][s].
if ((s | e) != s) {
f[i][s] = (f[i][s] + f[i - 1][j]) % p;
}
}
}
}
// 遍历所有最终状态, f[n][i]里存储的都是长度为n但未达成"妙手"的方案数.
// 从总方案ans里减去这些不满足条件的方案.
for (int i = 0; i <= m; i++) {
ans = (ans + p - f[n][i]) % p;
}
cout << ans << '\n';
return 0;
}
[CSP-J 2023] 小苹果
解题代码
// 题意: n个苹果, 每天取走位置为1,4,7...的, 剩下的重排. 求总天数与编号n被取走的天数.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
// --- 计算总天数 ---
ll cur = n;
int d1 = 0;
while (cur > 0) {
d1++;
// 每一天, 数量为cur的苹果会被拿走 ceil(cur / 3.0) 个
// 在整数计算中, (cur + 2) / 3 等价于 ceil(cur / 3.0)
cur -= (cur + 2) / 3;
}
// --- 计算编号为n的苹果被取走的天数 ---
ll pos = n;
int d2 = 0;
while (true) {
d2++;
// 如果当前位置是3k+1, 则在这一天被取走
if (pos % 3 == 1) {
break;
}
// 如果没被取走, 计算它在下一天新队列中的位置
// 它前方被取走的苹果数量为 (pos + 1) / 3
pos -= (pos + 1) / 3;
}
cout << d1 << " " << d2 << '\n';
return 0;
}
[CSP-J 2023] 公路
解题代码
/*
* 题意:
* 开车从1号站到n号站，每段路长v[i]，i号站油价a[i]，每升油跑d公里。
* 求最小花费。
*
* 思路:
* 贪心。在当前站点i，找到下一个油价更低的站点j。
* 若有，则在i只买恰好能跑到j的油；若无，则在i买足跑到终点的油。
* 用单调栈O(n)预处理出每个站点右边第一个更便宜的站点。
* 然后模拟跳跃过程，计算总花费。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 100005;
int n;
ll d;
ll v[MAX];
ll a[MAX];
ll pre[MAX]; // v的前缀和
int nxt[MAX]; // 下一个更小油价站点的下标
void slv() {
cin >> n >> d;
// v_i 是站点 i 到 i+1 的距离
for (int i = 1; i < n; ++i) cin >> v[i];
for (int i = 1; i <= n; ++i) cin >> a[i];
// 计算距离前缀和
pre[0] = 0;
for (int i = 1; i < n; ++i) {
pre[i] = pre[i - 1] + v[i];
}
// 从 i 到 j (j>i) 的距离是 pre[j-1] - pre[i-1]
// 单调栈预处理下一个更便宜的油站
stack<int> s;
for (int i = n; i >= 1; --i) {
while (!s.empty() && a[s.top()] >= a[i]) {
s.pop();
}
if (s.empty()) {
nxt[i] = n + 1; // 哨兵，表示后面没有更便宜的了
} else {
nxt[i] = s.top();
}
s.push(i);
}
ll ans = 0;
ll rge = 0; // 当前油量能跑的公里数
int cur = 1;
while (cur < n) {
int tar = nxt[cur];
if (tar > n) { // 后面没有更便宜的油站
tar = n;
}
// 计算从 cur 到 tar 的距离
ll dis = pre[tar - 1] - pre[cur - 1];
// 如果当前油量不够跑到tar
if (rge < dis) {
ll buy = dis - rge;
// 计算需要买多少升油，向上取整
ll ltr = (buy + d - 1) / d;
ans += ltr * a[cur];
rge += ltr * d;
}
rge -= dis;
cur = tar;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slv();
return 0;
}
[CSP-J 2023] 一元二次方程
题目链接：P9750 [CSP-J 2023] 一元二次方程
解题代码
// 题意: 求解一元二次方程并按格式化输出.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// 计算最大公约数
ll gcd(ll x, ll y) {
return y == 0 ? x : gcd(y, x % y);
}
// 按要求格式化输出有理数 p/q
void put(ll p, ll q) {
if (p == 0) {
cout << 0;
return;
}
ll g = gcd(abs(p), abs(q));
p /= g;
q /= g;
if (q < 0) {
p = -p;
q = -q;
}
if (q == 1) {
cout << p;
} else {
cout << p << "/" << q;
}
}
// 单次求解过程
void slv() {
ll a, b, c;
cin >> a >> b >> c;
ll del = 1ll * b * b - 4ll * a * c;
if (del < 0) {
cout << "NO";
return;
}
ll sd = round(sqrt(del));
if (sd * sd == del) { // 有理根
ll p = -b;
// 根据a的符号决定取+sqrt(del)还是-sqrt(del)得到较大根
if (a > 0) p += sd;
else p -= sd;
ll q = 2 * a;
put(p, q);
} else { // 无理根
// 将 sqrt(del) 化简为 k*sqrt(r)
ll k = 1;
ll r = del;
for (ll i = 2; i * i <= r; ++i) {
while (r % (i * i) == 0) {
k *= i;
r /= (i * i);
}
}
// 输出有理部分 q1 = -b / 2a
if (b != 0) {
put(-b, 2 * a);
cout << "+";
}
// 输出无理部分 q2*sqrt(r)
// q2 = k / |2a|
ll p2 = k;
ll q2 = abs(2 * a);
ll g = gcd(p2, q2);
p2 /= g;
q2 /= g;
if (p2 == 1 && q2 == 1) { // q2 = 1
cout << "sqrt(" << r << ")";
} else if (q2 == 1) { // q2 为整数
cout << p2 << "*sqrt(" << r << ")";
} else if (p2 == 1) { // q2 = 1 / 整数
cout << "sqrt(" << r << ")/" << q2;
} else { // q2 为一般分数
cout << p2 << "*sqrt(" << r << ")/" << q2;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, m;
cin >> t >> m;
while (t--) {
slv();
cout << "\n";
}
return 0;
}
[CSP-J 2023] 旅游巴士
解题代码
/*
* 题意:
* 在一个n点m边的有向图中，从1到n找一条路径。
* 每条边通过时间为1，且有一个开放时间a，必须在不早于a的时刻出发。
* 不能停留。要求进入1号点和离开n号点的时间都是k的倍数。求最早离开时间。
*
* 思路:
* 路径长度L必须是k的倍数。设出发时间为T_start，则T_start >= max(a_i - (i-1))。
* 目标是最小化 T_end = ceil(max(a_i-(i-1))/k)*k + L。
* 这是一个带有复杂代价函数的最短路问题。
*
* 使用Dijkstra，状态为 (u, r)，表示到达u点，路径长度模k为r。
* d[u][r] 记录最优路径的{长度L, 约束值M}。
* 优先队列按T_end排序，寻找最优解。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10004;
const int K = 101;
const ll INF = 1e18;
int n, m, k;
vector<pair<int, int>> adj[N];
pair<ll, ll> D[N][K]; // 存储最优路径的 {L, M}
struct St {
ll cst, l, m; // cost (T_end), length, M_val
int u, r; // node, remainder
bool operator>(const St& o) const {
if (cst != o.cst) return cst > o.cst;
return l > o.l;
}
};
// 计算T_end
ll cal(ll l, ll m, int kk) {
if (l >= INF) return INF;
ll st = 0;
if (m > 0) {
st = (m + kk - 1) / kk * kk;
}
return st + l;
}
void slv() {
cin >> n >> m >> k;
// 用map处理平行边，只保留a最小的
map<pair<int, int>, int> E;
for (int i = 0; i < m; ++i) {
int u, v, a;
cin >> u >> v >> a;
if (E.find({u, v}) == E.end()) {
E[{u, v}] = a;
} else {
E[{u, v}] = min(E[{u, v}], a);
}
}
for (auto const& [p, a] : E) {
adj[p.first].push_back({p.second, a});
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < k; ++j) {
D[i][j] = {INF, INF};
}
}
priority_queue<St, vector<St>, greater<St>> q;
D[1][0] = {0, -INF};
q.push({0, 0, -INF, 1, 0});
while (!q.empty()) {
St cur = q.top();
q.pop();
ll cst = cur.cst;
ll l = cur.l;
ll M = cur.m;
int u = cur.u;
int r = cur.r;
if (cst > cal(D[u][r].first, D[u][r].second, k) ||
(cst == cal(D[u][r].first, D[u][r].second, k) && l > D[u][r].first)) {
continue;
}
for (auto& edg : adj[u]) {
int v = edg.first;
int a = edg.second;
ll nl = l + 1;
ll nm = max(M, (ll)a - l);
int nr = nl % k;
ll nc = cal(nl, nm, k);
if (nc < cal(D[v][nr].first, D[v][nr].second, k) ||
(nc == cal(D[v][nr].first, D[v][nr].second, k) && nl < D[v][nr].first)) {
D[v][nr] = {nl, nm};
q.push({nc, nl, nm, v, nr});
}
}
}
ll ans = cal(D[n][0].first, D[n][0].second, k);
if (ans >= INF) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slv();
return 0;
}
[CSP-J 2024] 扑克牌
解题代码
/*
* 题意:
* 一副完整的扑克牌有 52 张 (4 种花色 x 13 种点数)。
* 现有 n 张牌，可能包含重复的牌。
* 问至少需要再借多少张牌，才能凑齐一副完整的扑克牌。
*
* 思路:
* 统计给定的 n 张牌中，有多少种不同的牌。
* 用一个集合 (set) 来存储已有的牌，集合能自动去重。
* 遍历 n 张牌，将代表牌的字符串插入集合。
* 最终，52 减去集合的大小，即为所需借的牌数。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void slv() {
int n;
cin >> n;
set<string> s;
for (int i = 0; i < n; ++i) {
string c;
cin >> c;
s.insert(c);
}
cout << 52 - s.size() << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slv();
return 0;
}
[CSP-J 2024] 地图探险
解题代码
// 题意概括:
// 在一个 n x m 的网格地图上模拟一个机器人的移动。地图上有空地和障碍物。
// 机器人有位置(x,y)和朝向d（0-3分别代表E,S,W,N）。它将执行k次操作。
// 每次操作，机器人尝试向当前朝向前进一格：
// - 如果目标格子在地图内且是空地，则移动到该格，方向不变。
// - 否则，位置不变，方向右转90度 (d = (d+1)%4)。
// 任务是计算k次操作后，机器人总共访问过多少个不同的格子（包括起点）。
//
// 核心思路：
// 这是一个直接的模拟问题。由于操作次数 k (<= 10^6) 和地图大小 (<= 1000x1000)
// 都在可接受的范围内，我们可以精确地模拟机器人的每一步操作。
// 使用一个二维布ール数组 `vis` 来记录访问过的格子。
// 循环 k 次，在每一步中，根据当前状态 (x,y,d) 计算出下一步的目标位置 (nx,ny)。
// 判断 (nx,ny) 是否可达（在边界内且非障碍）。
// 如果可达，更新机器人位置，并检查 `vis[nx][ny]`，如果未访问过则计数器加一并标记。
// 如果不可达，则更新机器人朝向。
// 模拟结束后，计数器的值即为答案。
// 考虑到 k 可能大于总状态数(n*m*4)，理论上存在循环。但由于 k 的值相对较小，
// 不需要实现复杂的循环检测，直接模拟即可通过。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll k;
int x, y, d;
vector<string> g;
vector<vector<bool>> vis;
// 方向向量: 0:E, 1:S, 2:W, 3:N
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
void sol() {
cin >> n >> m >> k;
cin >> x >> y >> d;
x--;
y--;
g.assign(n, string(m, ' '));
for (int i = 0; i < n; ++i) {
cin >> g[i];
}
vis.assign(n, vector<bool>(m, false));
vis[x][y] = true;
int cnt = 1;
for (ll i = 0; i < k; ++i) {
int nx = x + dx[d];
int ny = y + dy[d];
bool ok = true;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
ok = false;
} else if (g[nx][ny] == 'x') {
ok = false;
}
if (ok) {
x = nx;
y = ny;
if (!vis[x][y]) {
vis[x][y] = true;
cnt++;
}
} else {
d = (d + 1) % 4;
}
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
sol();
}
return 0;
}
[CSP-J 2024] 小木棍
解题代码
// 题目：P11229 [CSP-J 2024] 小木棍
// 题意：用 n 根小木棍，拼成一个最小的正整数。
// 思路：
// 答案的位数越少，数就越小。
// 所以从小到大枚举答案的位数 len。
// 对于第一个能拼出数字的 len，用贪心构造出字典序最小的那个数，即为答案。
// 构造时，从高到低每一位都尝试最小的数字，并检查剩余木棍是否在剩余位数的表示范围内。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int cst[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 数字0-9的代价
void sol() {
int n;
cin >> n;
bool fnd = false;
// 枚举答案的位数
for (int len = 1; len <= n / 2 + 2 && len < 100000; ++len) {
// 剪枝：len位数字的代价范围是[2*len, 7*len]
if (n > len * 7 || n < len * 2) {
continue;
}
int rem = n;
string ans = "";
bool psl = true;
// 从高到低确定每一位
for (int pos = 1; pos <= len; ++pos) {
int rln = len - pos; // 剩余位数
bool dgt = false;
// 尝试当前位填入的最小数字
for (int d = (pos == 1 ? 1 : 0); d <= 9; ++d) {
int c = cst[d];
if (rem >= c) {
// 检查剩余木棍数是否能被剩余位数表示
if (rem - c >= rln * 2 && rem - c <= rln * 7) {
ans += to_string(d);
rem -= c;
dgt = true;
break;
}
}
}
if (!dgt) {
psl = false;
break;
}
}
if (psl) {
cout << ans << endl;
fnd = true;
break;
}
}
if (!fnd) {
cout << -1 << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
sol();
}
return 0;
}
[CSP-J 2024] 接龙
解题代码
/*
* 题意概括:
* n个人，每人有一个词库。进行r轮接龙游戏。
* 规则：
* 1. 每轮由一人 p 从其词库 Sp 中选一个长度为 [2, k] 的连续子序列 A。
* 2. 第一轮 A 的开头必须是 1。
* 3. 后续轮次 A 的开头必须是上一轮 A 的结尾。
* 4. 相邻两轮不能是同一个人。
* q 个任务，每个任务问 r 轮后，接龙序列的最后一个元素能否是 c。
*
* 解法:
* 预处理动态规划。
* 定义 own[i][j] 表示第 i 轮后，以数字 j 结尾的接龙是由谁完成的。
* own[i][j] 的值有三种情况：
* - 0: 表示无法达成。
* - p (p > 0): 表示只能由第 p 个人完成。
* - -1: 表示可以由多于一个人完成。
*
* 状态转移：
* 从第 1 轮到第 100 轮（题目 r 的上限）进行迭代。
* 对第 r 轮：
* 1. 首先确定哪些数字可以作为本轮接龙序列的开头 (hed)。
* - r=1 时，只有数字 1 可以作为开头。
* - r>1 时，数字 s[i] 能作为开头，当且仅当它在 r-1 轮是一个合法的结尾，
* 并且完成者不是当前持有 s[i] 的人。如果 r-1 轮的结尾有多个完成者，则任何人都可以接。
* 2. 使用前缀和 (hsm) 优化查找过程。
* 3. 遍历所有词库中的每个位置 i，判断它能否成为一个合法的结尾 (tal)。
* - 这要求在 [i-k+1, i-1] 范围内，且在当前主人词库内，存在一个合法的开头。
* 4. 根据所有合法的结尾，更新 own[r] 数组。
* 所有查询均可 O(1) 回答。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 100005;
const int MXR = 105;
const int MXL = 200005;
const int MXS = 200005;
const ll MUL = -1; // 代表多人可完成
int s[MXL], per[MXL];
bool hed[MXR][MXL], tal[MXR][MXL];
ll own[MXR][MXS];
int n, k, q;
int len[MXN], ed[MXN];
int hsm[MXL + 1];
void slv() {
cin >> n >> k >> q;
ed[0] = 0;
int tot = 0;
for (int i = 1; i <= n; ++i) {
cin >> len[i];
for (int j = 0; j < len[i]; ++j) {
cin >> s[tot];
per[tot] = i;
tot++;
}
ed[i] = tot;
}
for (int r = 1; r <= 100; r++) {
// 计算本轮哪些位置可以作为龙头
if (r == 1) {
for (int i = 0; i < tot; i++) {
hed[r][i] = (s[i] == 1);
}
} else {
for (int i = 0; i < tot; i++) {
ll pown = own[r - 1][s[i]];
if (pown == 0) {
hed[r][i] = false;
} else if (pown == MUL) {
hed[r][i] = true; // 多人可达，任何人都可以接
} else {
hed[r][i] = (pown != per[i]); // 不能自己接自己的
}
}
}
// 前缀和优化，快速判断一个区间内有无合法龙头
hsm[0] = 0;
for (int i = 0; i < tot; i++) {
hsm[i + 1] = hsm[i] + hed[r][i];
}
// 计算本轮哪些位置可以作为龙尾
for (int i = 0; i < tot; i++) {
int p = per[i];
int lft = max(ed[p - 1], i - k + 1); // 合法开头的搜索窗口左边界
int rgt = i; // 搜索窗口右边界（开）
if (lft < rgt && hsm[rgt] - hsm[lft] > 0) {
tal[r][i] = true;
} else {
tal[r][i] = false;
}
}
// 更新本轮的 owner 状态
fill(own[r], own[r] + MXS, 0);
for (int i = 0; i < tot; i++) {
if (tal[r][i]) {
if (own[r][s[i]] == 0) {
own[r][s[i]] = per[i];
} else if (own[r][s[i]] != per[i]) {
own[r][s[i]] = MUL;
}
}
}
}
while (q--) {
int r, c;
cin >> r >> c;
if (r > 100 || c >= MXS) {
cout << 0 << "\n";
} else {
cout << (own[r][c] != 0) << "\n";
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
slv();
}
return 0;
}
0 条评论
目前还没有评论...
