Codeforces Round 913 (Div. 3) 题解
A. 车的移动范围
题目要求：给出一个车在国际象棋棋盘上的位置，输出它可以到达的所有坐标。
思路分析：车可以沿着行或列移动任意格数。因此，只需枚举除当前位置外的所有行和列上的点。
#include <iostream>
#include <string>
using namespace std;
void process() {
string pos;
cin >> pos;
char col = pos[0];
int row = pos[1] - '0';
for (int i = 1; i <= 8; ++i) {
if (i != row) cout << col << i << "\n";
}
for (char c = 'a'; c <= 'h'; ++c) {
if (c != col) cout << c << row << "\n";
}
}
int main() {
int T;
cin >> T;
while (T--) process();
return 0;
}
B. 键盘删除问题
题目描述：模拟键盘输入，其中 'b' 和 'B' 分别删除最近的小写或大写字母。
解决方法：使用两个栈分别记录小写和大写字母的位置，并根据按键类型执行相应的删除操作。
#include <iostream>
#include <stack>
#include <string>
using namespace std;
void solve() {
string input;
cin >> input;
stack<char> lower, upper;
string result = "";
for (char c : input) {
if (c == 'b') {
if (!lower.empty()) {
lower.pop();
}
} else if (c == 'B') {
if (!upper.empty()) {
upper.pop();
}
} else {
if (c >= 'a' && c <= 'z') {
lower.push(c);
} else if (c >= 'A' && c <= 'Z') {
upper.push(c);
}
result += c;
}
}
cout << result << "\n";
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
C. 最短字符串长度
题目说明：给定一个字符串，每次可以删除相邻的不同字符，求最终可能的最短长度。
解决策略：统计每个字符出现次数，最短长度等于最多字符的数量减去其他字符数量。
#include <iostream>
#include <string>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int freq[26] = {0};
for (char c : s) freq[c - 'a']++;
int max_freq = 0;
for (int i = 0; i < 26; ++i) max_freq = max(max_freq, freq[i]);
cout << max(1, n % 2 + (max_freq * 2 - n)) << "\n";
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
D. 数轴跳跃
题目描述：在数轴上进行跳跃，目标是找到最小的跳跃距离 k。
解决方法：通过二分查找确定最小的 k 值。
#include <iostream>
#include <vector>
using namespace std;
bool check(int k, const vector<pair<int, int>>& segments) {
int left = 0, right = 0;
for (auto [l, r] : segments) {
left -= k; right += k;
if (right < l || left > r) return false;
left = max(left, l); right = min(right, r);
}
return true;
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> segments(n);
int max_r = 0;
for (auto& [l, r] : segments) {
cin >> l >> r;
max_r = max(max_r, r);
}
int low = 0, high = max_r;
while (low < high) {
int mid = (low + high) / 2;
if (!check(mid, segments)) low = mid + 1;
else high = mid;
}
cout << low << "\n";
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
E. 数字三元组
题目要求：找到满足特定条件的三元组数量。
解决方案：逐位计算贡献值。
#include <iostream>
#include <string>
using namespace std;
void solve() {
string num;
cin >> num;
long long res = 1;
int dp[10] = {1};
for (int i = 1; i <= 9; ++i) dp[i] = dp[i - 1] + i + 1;
for (char c : num) res *= dp[c - '0'];
cout << res << "\n";
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
F. 数组排序操作
题目解释：通过移位和翻转操作使数组非递增排列。
解决步骤：将数组扩展为环形结构，尝试找到合适的起始点和方向。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solve(vector<int>& arr) {
int n = arr.size();
vector<int> doubled_arr = arr;
for (int i = 0; i < n; ++i) doubled_arr.push_back(arr[i]);
int min_steps = INT32_MAX;
for (int start = n - 1; start < doubled_arr.size() - 1; ++start) {
bool valid = true;
int steps = 0;
for (int i = start; i > start - n; --i) {
if (doubled_arr[i] < doubled_arr[i + 1]) {
valid = false;
break;
}
steps++;
}
if (valid) min_steps = min(min_steps, steps);
}
return min_steps == INT32_MAX ? -1 : min_steps;
}
void process() {
int n;
cin >> n;
vector<int> arr(n);
for (int &x : arr) cin >> x;
if (n == 1) {
cout << "0\n";
return;
}
int res = solve(arr);
reverse(arr.begin(), arr.end());
res = min(res, solve(arr) + 1);
cout << (res == INT32_MAX ? "-1" : to_string(res)) << "\n";
}
int main() {
int T;
cin >> T;
while (T--) process();
return 0;
}
