当前位置：首页 > news >正文

CST编程题题解

news 2026/3/27 5:35:22

一、CST 1-1-2 Interview（圆桌面试顺序）

解题思路

第一个应聘者直接入列，后续应聘者从前一人位置逆时针数m人，在第m人右侧插入；
利用列表模拟环形结构，通过取模计算环形位置，避免越界；
最终从最后入座者开始，顺时针遍历（列表中位置逐次减1并取模）得到面试顺序。

C++ 完整代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<int> ids(n);for (int i = 0; i < n; ++i) {cin >> ids[i];}if (n == 0) {cout << endl;return 0;}vector<int> circle;circle.push_back(ids[0]);int pre_pos = 0; // 前一个人的位置for (int i = 1; i < n; ++i) {int cur_size = circle.size();// 计算第m人的位置，前一人是第1人int target_pos = (pre_pos + m - 1) % cur_size;// 右侧插入即target_pos+1int insert_pos = target_pos + 1;circle.insert(circle.begin() + insert_pos, ids[i]);pre_pos = insert_pos;}// 从最后一人开始顺时针输出vector<int> res;int last_pos = pre_pos;for (int i = 0; i < n; ++i) {res.push_back(circle[last_pos]);last_pos = (last_pos - 1 + n) % n; // 加n避免负数}// 输出结果for (int i = 0; i < res.size(); ++i) {if (i > 0) cout << " ";cout << res[i];}cout << endl;return 0;
}

输入输出示例

输入：

3 2
10 20 30

输出：

30 20 10

二、CST 1-2-1 Gift（礼物方案数）

解题思路

核心为折半搜索（Meet-in-the-Middle），适配n≤40的组合计数：

将n个礼物分为左右两半（各≤20），分别枚举两半的所有组合花费；
对右半花费数组排序，遍历左半每个花费，用二分查找统计右半中满足左花费+右花费≤P的数量；
累加所有符合条件的数量，即为总方案数，时间复杂度O(2^(n/2) * log2^(n/2))。

C++ 完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll; // 防止溢出，P≤1e9，n=40时和最大4e10// 枚举某一半的所有可能花费
void dfs(int idx, ll sum, const vector<pair<ll, ll>>& cost, vector<ll>& res) {if (idx == cost.size()) {res.push_back(sum);return;}// 选第一个礼物dfs(idx + 1, sum + cost[idx].first, cost, res);// 选第二个礼物dfs(idx + 1, sum + cost[idx].second, cost, res);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;ll P;cin >> n >> P;vector<pair<ll, ll>> cost(n);for (int i = 0; i < n; ++i) {cin >> cost[i].first >> cost[i].second;}// 折半分割int mid = n / 2;vector<pair<ll, ll>> left(cost.begin(), cost.begin() + mid);vector<pair<ll, ll>> right(cost.begin() + mid, cost.end());vector<ll> left_sum, right_sum;dfs(0, 0, left, left_sum);dfs(0, 0, right, right_sum);// 右半排序sort(right_sum.begin(), right_sum.end());ll ans = 0;for (ll s : left_sum) {if (s > P) continue;ll rest = P - s;// 二分找<=rest的元素个数ans += upper_bound(right_sum.begin(), right_sum.end(), rest) - right_sum.begin();}cout << ans << endl;return 0;
}

输入输出示例

输入：

输出：

三、CST 1-2-2 Graphics（线段交点计数）

解题思路

无交线段配对规则：x轴点升序、y轴点降序一一配对（唯一无交方案）；
几何判交转化：射线OP与线段(x_i,0)-(0,y_i)相交 ⇨ x_p * y_i < x_i * y_p（交叉积避免浮点误差）；
二分计数：将配对后的(x_i,y_i)按x_i/y_i升序排序，对每个查询(x_p,y_p)，二分统计满足条件的线段数，时间复杂度O(n logn + m logn)。

C++ 完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll; // 防止交叉积溢出int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<ll> x(n), y(n);for (int i = 0; i < n; ++i) cin >> x[i];for (int i = 0; i < n; ++i) cin >> y[i];// 记录原始索引，用于配对vector<pair<ll, int>> x_idx, y_idx;for (int i = 0; i < n; ++i) x_idx.emplace_back(x[i], i);for (int i = 0; i < n; ++i) y_idx.emplace_back(y[i], i);// x升序，y降序排序sort(x_idx.begin(), x_idx.end());sort(y_idx.begin(), y_idx.end(), greater<pair<ll, int>>());// 配对后的x和yvector<pair<ll, ll>> pairs;for (int i = 0; i < n; ++i) {ll xi = x[x_idx[i].second];ll yi = y[y_idx[i].second];pairs.emplace_back(xi, yi);}// 按xi/yi升序排序（用交叉积比较，避免浮点）sort(pairs.begin(), pairs.end(), [](const pair<ll, ll>& a, const pair<ll, ll>& b) {return a.first * b.second < b.first * a.second;});// 处理查询int m;cin >> m;while (m--) {ll xp, yp;cin >> xp >> yp;// 找第一个满足 xi*yp > xp*yi 的位置，即为符合条件的数量int cnt = lower_bound(pairs.begin(), pairs.end(), make_pair(0LL, 0LL), [&](const pair<ll, ll>& p, const pair<ll, ll>&) {return p.first * yp > xp * p.second;}) - pairs.begin();cout << cnt << endl;}return 0;
}

输入输出示例

输入：

输出：

1
1

四、CST 1-2-3 二维偏序（三元组最大和）

解题思路

核心为二维偏序+带权LIS+树状数组优化DP：

排序：三元组按a升序、a相同按b升序排序，消去一维偏序；
离散化：将b值映射为连续正整数（适配树状数组，处理负数/大数）；
树状数组DP：定义dp[i] = c[i] + max{dp[j] | b[j] ≤ b[i]}，用树状数组维护区间最大值，实现O(logn)查询/更新；
最终答案为所有dp[i]的最大值。

C++ 完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;
const int MAXN = 1e5 + 5;// 树状数组：维护区间最大值
struct FenwickTree {vector<ll> tree;int n;FenwickTree(int size) : n(size) {tree.assign(n + 2, 0); // 初始为0}// 更新idx位置的最大值为valvoid update(int idx, ll val) {for (; idx <= n; idx += idx & -idx) {if (tree[idx] < val) tree[idx] = val;else break; // 无更大值，无需继续更新}}// 查询[1, idx]的最大值ll query(int idx) {ll res = 0;for (; idx > 0; idx -= idx & -idx) {if (tree[idx] > res) res = tree[idx];}return res;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<tuple<int, int, ll>> tri(n); // (a, b, c)vector<int> b_list;for (int i = 0; i < n; ++i) {int a, b;ll c;cin >> a >> b >> c;tri[i] = {a, b, c};b_list.push_back(b);}// 步骤1：按a升序，a相同按b升序排序sort(tri.begin(), tri.end(), [](const tuple<int, int, ll>& t1, const tuple<int, int, ll>& t2) {if (get<0>(t1) != get<0>(t2)) return get<0>(t1) < get<0>(t2);return get<1>(t1) < get<1>(t2);});// 步骤2：b值离散化sort(b_list.begin(), b_list.end());b_list.erase(unique(b_list.begin(), b_list.end()), b_list.end());int max_id = b_list.size();// 步骤3：树状数组优化DPFenwickTree ft(max_id);ll ans = 0;for (auto& t : tri) {int a = get<0>(t), b = get<1>(t);ll c = get<2>(t);// 查找b的离散化idint bid = lower_bound(b_list.begin(), b_list.end(), b) - b_list.begin() + 1; // 1开始// 查询前序最大值ll pre_max = ft.query(bid);ll current = pre_max + c;// 更新树状数组ft.update(bid, current);// 更新答案if (current > ans) ans = current;}cout << ans << endl;return 0;
}