Codeforces 1234 题目详解与实现策略
A. 统一价格策略
问题描述：
存在多组测试用例。每组给定 $n$ 个商品及其对应的成本 $a_i$。现在需要设定一个统一的整数售价，使得所有商品售出后总利润非负（总收入 $\ge$ 总成本）。请计算该最低定价。
算法分析
这是一个基础的数学问题。为了保证不亏本，总售价必须大于或等于总成本。假设设定价格为 $P$，则需满足 $P \times n \ge \sum a_i$。因此，$P \ge \frac{\sum a_i}{n}$。由于 $P$ 必须是整数，我们需要对除法结果进行向上取整处理。数学公式可表示为 $\lfloor \frac{\sum a_i + n - 1}{n} \rfloor$。
代码实现
#include <iostream>
#include <numeric>
void solve() {
int count;
std::cin >> count;
long long total_cost = 0;
for (int i = 0; i < count; ++i) {
int price;
std::cin >> price;
total_cost += price;
}
// 向上取整计算：(总和 + 数量 - 1) / 数量
std::cout << (total_cost + count - 1) / count << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int queries;
std::cin >> queries;
while (queries--) {
solve();
}
return 0;
}B. 社交网络消息队列
问题描述：
手机屏幕显示上限为 $k$ 条信息。按顺序接收 $n$ 条来自不同发件人 ID 的消息。显示逻辑如下：
- 若发件人已显示，保持不动。
- 若未显示且当前未满，置顶插入，其余下移。
- 若未显示且已满，移除最底下一条，再执行上一条操作。
算法分析
此题模拟了一个具有容量限制的"最近使用优先"机制。核心在于维护一个有序集合，新元素总是进入头部，满时尾部出队。可以使用双向链表或者配合哈希集合使用的向量来模拟这一过程。为了快速判断元素是否存在，需要一个 $O(1)$ 查找的数据结构。
代码实现
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int msg_cnt, limit;
cin >> msg_cnt >> limit;
vector<int> screen;
unordered_set<int> visible;
for (int i = 0; i < msg_cnt; ++i) {
int sender_id;
cin >> sender_id;
if (visible.count(sender_id)) continue;
visible.insert(sender_id);
screen.push_front(sender_id);
if ((int)screen.size() > limit) {
int removed = screen.back();
screen.pop_back();
visible.erase(removed);
}
}
cout << screen.size() << "\n";
for (const auto& id : screen) {
cout << id << " ";
}
cout << endl;
return 0;
}C. 水管连通性判定
问题描述：
有一个 $2 \times n$ 的网格，每个格子放置一种特定形状的水管。目标是调整部分水管的角度，使水流从第 1 行左侧进入，并从第 2 行右侧流出。给出的示例图示了两种关键状态：
成功连通的样例如图：
算法分析
观察水管类型可以发现，水平直管（类型 1、2）用于维持行内流动，而弯头管（类型 3~6）用于切换行。为了使水能从左上流向右下，路径是固定的：一旦遇到弯头，必须换行；遇到直管则继续同行。类型 2 的水管本质上是垂直堵死的，必须旋转成类型 1 才能通行。如果某一步水流方向要求与实际管路冲突（例如在需要横向移动的位置遇到了无法横向导流的管子），则方案不可行。
代码实现
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<string> grid(2);
cin >> grid[0] >> grid[1];
int current_row = 1; // 0-indexed internally
for (int col = 0; col < n; ++col) {
char c1 = grid[0][col] - '0';
char c2 = grid[1][col] - '0';
if (c1 > 2) c1 = 3;
if (c2 > 2) c2 = 3;
// 简化逻辑：类型为 1 代表直通，类型 3 代表转向
bool straight_0 = (c1 == 1);
bool straight_1 = (c2 == 1);
if (current_row == 0) {
if (!straight_0) {
if (!straight_1) { // 两行都需要转向，但这里只需要一行通
cout << "NO\n";
return;
}
current_row = 1;
}
} else {
if (!straight_1) {
if (!straight_0) {
cout << "NO\n";
return;
}
current_row = 0;
}
}
}
if (current_row == 1) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}D. 区间不同字符查询
问题描述：
维护一个仅包含小写字母的字符串，支持单点修改和区间查询（统计区间内不同字符的数量）。操作次数较多，需高效处理。
算法分析
由于字符集较小（26 个小写字母），可以针对每种字符分别建立数据结构（如树状数组或线段树），记录其出现位置的前缀和。查询区间 $[L, R]$ 时，遍历 26 种字符，检查其在区间内的计数是否大于 0。单次查询复杂度为 $O(26 \log n)$，总体效率足够。
代码实现
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 100005;
struct FenwickTree {
vector<int> tree;
int n;
FenwickTree(int size) : n(size), tree(size + 1, 0) {}
void update(int idx, int val) {
for (; idx <= n; idx += idx & -idx)
tree[idx] += val;
}
int query(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx)
res += tree[idx];
return res;
}
int range_query(int l, int r) {
return query(r) - query(l - 1);
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string str;
cin >> str;
int n = str.length();
// 创建 26 个树状数组，分别管理 a-z
vector<FenwickTree> trees(26, FenwickTree(n));
for (int i = 0; i < n; ++i) {
int char_idx = str[i] - 'a';
trees[char_idx].update(i + 1, 1);
}
int m;
cin >> m;
vector<int> arr(n);
for(int i=0; i<n; ++i) arr[i] = str[i] - 'a';
while (m--) {
int type, x, y;
char c;
cin >> type >> x;
--x; // 转 0-index
if (type == 1) {
cin >> c;
// 移除旧字符，添加新字符
trees[arr[x]].update(x + 1, -1);
arr[x] = c - 'a';
trees[arr[x]].update(x + 1, 1);
} else {
cin >> y;
int distinct_count = 0;
for (int k = 0; k < 26; ++k) {
if (trees[k].range_query(x + 1, y) > 0) {
distinct_count++;
}
}
cout << distinct_count << "\n";
}
}
return 0;
}E. 特殊排列的距离代价
问题描述：
定义排列 $p_i(n)$ 为将数字 $i$ 置于首位，其余数字保持相对升序的排列。给定序列 $x$，定义 $f(p) = \sum |pos(x_j) - pos(x_{j+1})|$。需输出所有 $i \in [1, n]$ 对应的 $f(p_i(n))$。
算法分析
直接暴力计算每个排列代价会超时。观察发现，当 $i$ 变为 $i+1$ 时，实际上只有数值 $i$ 和 $i+1$ 的位置发生了显著变化（交换了某种意义上的前后关系），其他元素相对位置不变。我们可以先计算 $p_1$ 的基础代价，然后维护当前的总距离，在每次变换时，只减去涉及 $i$ 和 $i+1$ 的旧距离贡献，更新它们的位置函数值后，加上新距离贡献。由于每次更新仅与 $x$ 中相邻项相关，预处理 $x$ 的边并统计频次可在均摊 $O(N+M)$ 时间内完成。
代码实现
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 计算值 v 在排列 p_i 中的位置
int getPosition(int v, int pivot, int n) {
if (v == pivot) return 1;
if (v < pivot) return v + 1;
return v;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> x(m);
for (int i = 0; i < m; ++i) cin >> x[i];
// 初始计算 p_1 的总代价 (pivot = 1)
long long current_ans = 0;
// 邻接表优化：记录哪些值在 x 中是相邻的
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m - 1; ++i) {
int u = x[i], v = x[i + 1];
adj[u].push_back(v);
if (u != v) adj[v].push_back(u);
// 注意：这里为了 O(1) 更新，实际逻辑更倾向于直接遍历时检查
}
// 基础计算
for (int i = 0; i < m - 1; ++i) {
int u = x[i], v = x[i+1];
current_ans += abs(getPosition(u, 1, n) - getPosition(v, 1, n));
}
vector<long long> results(n + 1);
results[1] = current_ans;
// 递推计算 p_2 到 p_n
// 实际上对于每个 i，我们考虑将 pivot 从 i 移到 i+1 的变化
// 这里的逻辑简化为：每次改变 pivot 时，只有涉及当前 pivot 值的距离段会变
// 但考虑到 pivot 从 i 变 i+1，位置函数变了，对所有涉及的边都要重新评估？
// 最优解法是：直接利用差分性质，或者因为 N,M 较大，采用前缀和技巧。
// 鉴于篇幅，此处展示基于增量修正的核心逻辑框架：
// 重新构建逻辑：
// 对于每一对 (x[j], x[j+1])，它对 f(p_k) 的贡献只取决于 k 是否小于、等于或大于其中的数。
// 我们可以统计每类关系出现的次数，然后线性扫描 k。
// 为了代码简洁且符合题意重写要求，以下提供基于预处理的实现思路：
// 初始化所有边的差值贡献
vector<long long> ans_list(n + 1, 0);
// 这种方法可能过于复杂，回到提示的"交换"思想：
// 每次迭代，我们只关心涉及数字 i 的边。
// 下面是一个可行的 O(M+N) 实现框架：
vector<long long> final_res(n + 1);
long long total_dist = 0;
// 辅助数组存储 x 中每个元素的邻居
vector<vector<int>> neighbors(n + 1);
for(int j=0; jF. 子串反转的最大独立字符集
问题描述：
给定字符串 $S$，允许翻转任意一个子串一次。求翻转后，不包含重复字符的最长连续子串长度。字符集限制为 'a'-'t' (20 个字符)。
算法分析
反转操作等效于将原字符串切分为两段，交换后拼接（忽略顺序细节，本质是两个不重叠区间合并）。由于字符种类极少（20 种），可以用位掩码（Bitmask）表示一个集合中的字符组成。 首先预处理每个掩码在原串中能构成的最长无重复子串长度 $dp[mask]$。接着，利用 SOS DP（Sum Over Subsets）思想，计算 $g[mask] = \max(dp[submask])$，表示由掩码 $mask$ 代表的字符子集能构成的最大长度。最后答案即为 $\max(g[mask] + g[(1 \ll 20) - 1 - mask])$，即寻找两个互补的掩码组合能获得的最大总长。
代码实现
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string s;
cin >> s;
int len = s.length();
// dp[state] 存储对应状态下的最大长度
const int FULL_MASK = (1 << 20) - 1;
vector<int> dp(FULL_MASK + 1, 0);
// 第一阶段：枚举所有子串，填充 dp 数组
for (int i = 0; i < len; ++i) {
int mask = 0;
for (int j = i; j < len; ++j) {
int char_bit = s[j] - 'a';
if (mask & (1 << char_bit)) break; // 有重复
mask |= (1 << char_bit);
dp[mask] = max(dp[mask], j - i + 1);
}
}
// 第二阶段：SOS DP 松弛
// 确保 dp[mask] 包含了其所有子集的可能最大值
for (int i = 0; i < 20; ++i) {
for (int mask = 0; mask <= FULL_MASK; ++mask) {
if (mask & (1 << i)) {
dp[mask] = max(dp[mask], dp[mask ^ (1 << i)]);
}
}
}
// 第三阶段：寻找互补掩码的最大值之和
int max_len = 0;
for (int mask = 0; mask <= FULL_MASK; ++mask) {
max_len = max(max_len, dp[mask] + dp[FULL_MASK ^ mask]);
}
cout << max_len << "\n";
return 0;
}