Codeforces 984 赛题题解与实现
Codeforces 984 赛题题解与实现
https://codeforces.com/contest/2036
A
题目要求判断序列中相邻元素的差值是否只能是5或7。我们可以遍历整个序列，检查每一对相邻元素是否满足这个条件。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int sequence[MAXN];
bool validateSequence(int length) {
for (int i = 1; i < length; i++) {
int diff = abs(sequence[i] - sequence[i-1]);
if (diff != 5 && diff != 7) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> sequence[i];
}
if (validateSequence(n)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
B
本题需要计算每种品牌的价值总和，并选取价值最高的前n个品牌。由于数据规模不大，我们可以使用数组存储各品牌价值，排序后直接选取前n个最大的值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int brandValues[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
int n, k;
cin >> n >> k;
// Reset brand values
fill(brandValues, brandValues + MAXN, 0);
// Read and accumulate brand values
for (int i = 0; i < k; i++) {
int brand, value;
cin >> brand >> value;
brandValues[brand] += value;
}
// Sort in descending order
sort(brandValues, brandValues + MAXN, greater<int>());
// Sum top n brands
long long total = 0;
for (int i = 0; i < min(n, MAXN); i++) {
total += brandValues[i];
}
cout << total << '\n';
}
return 0;
}
C
题目要求统计字符串中"1100"模式的出现次数，并处理多次修改操作。每次修改只会影响局部区域，我们可以通过检查修改前后的变化来高效更新计数。
#include <bits/stdc++.h>
using namespace std;
bool checkPattern(const string &s, int position) {
if (position < 0 || position + 4 > s.length()) {
return false;
}
return s[position] == '1' && s[position+1] == '1' &&
s[position+2] == '0' && s[position+3] == '0';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
string text;
int queries;
cin >> text >> queries;
// Add a dummy character at the beginning for 1-based indexing
text = " " + text;
int n = text.length();
int patternCount = 0;
// Count initial patterns
for (int i = 1; i <= n - 4; i++) {
if (checkPattern(text, i)) {
patternCount++;
}
}
while (queries--) {
int index;
char newChar;
cin >> index >> newChar;
// Check if the change actually affects the string
if (text[index] == newChar) {
continue;
}
// Check positions that might be affected by the change
for (int i = max(1, index-3); i <= min(n-4, index); i++) {
if (checkPattern(text, i)) {
patternCount--;
}
}
// Apply the change
text[index] = newChar;
// Check positions that might be affected after the change
for (int i = max(1, index-3); i <= min(n-4, index); i++) {
if (checkPattern(text, i)) {
patternCount++;
}
}
cout << (patternCount > 0 ? "Yes\n" : "No\n");
}
}
return 0;
}
D
对于矩阵的每一层，按顺时针方向提取数据。由于只需要判断4位连续的模式，我们在提取的数据末尾添加前三个字符形成环形结构，然后统计"1543"模式的出现次数。
#include <bits/stdc++.h>
using namespace std;
bool checkPattern(const string &s, int position) {
if (position < 0 || position + 4 > s.length()) {
return false;
}
return s[position] == '1' && s[position+1] == '5' &&
s[position+2] == '4' && s[position+3] == '3';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
int rows, cols;
cin >> rows >> cols;
vector<string> grid(rows);
for (int i = 0; i < rows; i++) {
cin >> grid[i];
}
int totalPatterns = 0;
int layer = 0;
while (rows > 2 * layer && cols > 2 * layer) {
string spiral;
int x = layer, y = layer;
// Right
while (y < cols - layer) {
spiral += grid[x][y++];
}
y--;
x++;
// Down
while (x < rows - layer) {
spiral += grid[x++][y];
}
x--;
y--;
// Left
while (y >= layer) {
spiral += grid[x][y--];
}
y++;
x--;
// Up
while (x > layer) {
spiral += grid[x--][y];
}
// Make it circular by adding first 3 characters at the end
spiral += spiral.substr(0, 3);
// Count patterns
for (int i = 0; i < spiral.length() - 3; i++) {
if (checkPattern(spiral, i)) {
totalPatterns++;
}
}
layer++;
}
cout << totalPatterns << '\n';
}
return 0;
}
E
我们需要预处理一个二维数组，利用按位或操作的单调性进行二分查找来确定范围。需要注意的是，应将列索引作为第一维以便于二分操作，同时要特别注意边界条件的处理。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int rows, cols, queries;
cin >> rows >> cols >> queries;
// Preprocess the grid column-wise
vector<vector<int>> columnOr(cols, vector<int>(rows));
for (int j = 0; j < cols; j++) {
for (int i = 0; i < rows; i++) {
int value;
cin >> value;
if (i == 0) {
columnOr[j][i] = value;
} else {
columnOr[j][i] = columnOr[j][i-1] | value;
}
}
}
while (queries--) {
int left = 1, right = rows, valid = 0;
int operations;
cin >> operations;
while (operations--) {
int col;
char op;
int value;
cin >> col >> op >> value;
col--;
if (op == '<') {
// Find the first position where columnOr[col][i] >= value
int pos = lower_bound(columnOr[col].begin(), columnOr[col].end(), value) - columnOr[col].begin();
if (pos == 0) {
valid = 1;
} else {
right = min(right, pos);
}
} else {
// Find the first position where columnOr[col][i] > value
int pos = upper_bound(columnOr[col].begin(), columnOr[col].end(), value) - columnOr[col].begin();
if (pos == rows) {
valid = 1;
} else {
left = max(left, pos);
}
}
}
if (valid || left > right) {
cout << -1 << '\n';
} else {
cout << left << '\n';
}
}
return 0;
}
F
利用连续自然数异或的特殊性质，我们可以推导出从0到x的异或结果规律。对于区间内满足特定模条件的数，我们可以将其分解为两部分计算：满足模条件的部分和剩余部分，最后组合得到结果。
#include <bits/stdc++.h>
using namespace std;
// Function to compute XOR from 0 to x
long long xorRange(long long x) {
if (x <= 0) return 0;
switch (x % 4) {
case 0: return x;
case 1: return 1;
case 2: return x + 1;
case 3: return 0;
default: return 0;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
long long left, right, exponent, modulus;
cin >> left >> right >> exponent >> modulus;
// Compute XOR from left to right
long long total = xorRange(right) ^ xorRange(left - 1);
// Calculate the range of j values
right = (right - modulus) >> exponent;
left = ((left - modulus + (1LL << exponent) - 1) >> exponent);
if (left < 0) left = 0;
// If the count is odd, include the modulus
if ((right - left + 1) & 1) {
total ^= modulus;
}
// XOR the higher bits
total ^= (xorRange(right) ^ xorRange(left - 1)) << exponent;
cout << total << '\n';
}
return 0;
}
