# Codeforces Round 878 (Div. 3) 题解 A - G2

## A. Cipher Shifer

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
int n;
string s;
cin >> n >> s;
for (int i = 0, j = 1; i < n && j < n; ++j) {
while (s[j] != s[i] && j < n) j++;
cout << s[i];
i = j + 1;
j++;
}
cout << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## B. Binary Cafe

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
LL n, k;
cin >> n >> k;
if (k >= 31) {
k = 30;
}
cout << min(n + 1, (LL)(1 << k)) << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## C. Ski Resort

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int a[N];

void solve() {
int n, k, q;
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
LL res = 0;
LL cnt = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] <= q) {
cnt++;
} else {
if (cnt >= k) {
res += ((cnt - k + 1) * (cnt - k + 2)) >> 1;
}
cnt = 0;
}
}
if (cnt >= k) {
res += ((cnt - k + 1) * (cnt - k + 2)) >> 1;
}
cout << res << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## D. Wooden Toy Festival

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int n;
int a[N];

bool check(LL mid) {
int cnt = 0;
int res = -1;
for (int i = 1; i <= n; ++i) {
if (abs(a[i] - res) > mid || !~res) {
cnt++;
res = a[i] + mid;
}
if (cnt > 3) return true;
}
return false;
}

void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
LL l = 0, r = MOD;
while (l < r) {
LL mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
} else {
r = mid;
}
}
cout << l << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## E. Character Blocking

### 题目大意

1. 给两个串第 (i) 位置封锁 (t) 秒。
2. 交换某个串的某个位置。
3. 检查两个串除去封锁位置之外是否相等。

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int a[N];
// a counter for difference
int dif = 0;
int cnt[N], cntP[N];
string s, t;

void difon(int p) {
if (s[p - 1] != t[p - 1]) dif++;
}
void difoff(int p) {
if (s[p - 1] != t[p - 1]) dif--;
}

void solve() {
dif = 0;
cin >> s >> t;
int x, q;
int n = s.length();
cin >> x >> q;
int curTime = 0;
for (int i = 0; i <= n; ++i) {
cnt[i] = cntP[i] = 0;
}
for (int i = 0; i < n; ++i) {
if (cnt[i] <= 0 && s[i] != t[i]) dif++;
}
queue<int> que;
for (int i = 1; i <= q; ++i) {
curTime++;
if (!que.empty()) {
auto top = que.front();
if (cnt[top] == curTime) {
que.pop();
difon(top + 1);
}
}
int op;
cin >> op;
switch (op) {
case 1:
int pos;
cin >> pos;
cnt[pos - 1] = cntP[pos - 1] = curTime + x;
que.push(pos - 1);
difoff(pos);
break;
case 2:
int op1, op2, p1, p2;
cin >> op1 >> p1 >> op2 >> p2;
difoff(p1);
difoff(p2);
if (op1 == 1 && op2 == 1) {
swap(s[p1 - 1], s[p2 - 1]);
} else if (op1 == 1 && op2 == 2) {
swap(s[p1 - 1], t[p2 - 1]);
} else if (op1 == 2 && op2 == 1) {
swap(t[p1 - 1], s[p2 - 1]);
} else {
swap(t[p1 - 1], t[p2 - 1]);
}
difon(p1);
difon(p2);
break;
default:
cout << (dif ? "NO" : "YES") << endl;
}
}
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## F. Railguns

### 解题思路

1. 对数组 `pii` 按照时间进行排序，保证射击按时间顺序处理。

2. 创建一个二维向量 `zz`，用来表示在当前时间点可达的坐标。初始化时，将起点 `(0, 0)` 标记为可达。

3. 使用一个变量 `t` 记录时间，初始值为 0。

4. 使用一个指针 `wz` 指向 `pii` 数组的起始位置。

5. 进入循环，直到目标坐标

``````(n, m)
``````

可达为止：

• 增加时间 `t`
• 使用队列 `qu` 存储当前时间点可达的坐标。
• 遍历二维向量 `zz`，将可达的坐标加入队列 `qu`
• 从队列 `qu` 中取出坐标 `(i, j)`，若 `i+1` 在范围内，则将 `(i+1, j)` 标记为可达。
• 从队列 `qu` 中取出坐标 `(i, j)`，若 `j+1` 在范围内，则将 `(i, j+1)` 标记为可达。
• 处理当前时间点的射击情况：
• 若指针`wz`没有超出`pii`数组的范围且当前射击时间等于 `t`
• 获取射击的坐标 `sz` 和方向，如果方向为 1，则将 `(sz, i)` 的可达状态设置为不可达（即设为 (0)）。
• 如果方向不为 1，则将 `(i, sz)` 的可达状态设置为不可达。
• 将指针 `wz` 向后移动一位。
• 检查是否存在可达的坐标，若不存在，则将 `t` 设置为 -1 并结束循环。

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

pair<int, pair<int, int>> pii[N];

void solve() {
int a, b;
cin >> a >> b;
int r;
cin >> r;
for (int i = 1; i <= r; i++) {
cin >> pii[i].first >> pii[i].second.first >> pii[i].second.second;
}
sort(pii + 1, pii + 1 + r);
vector<vector<int>> zz(a + 2, vector<int>(b + 2, 0));
zz[0][0] = 1;
int t = 0;
int wz = 1;
while (!zz[a][b]) {
t++;
queue<pair<int, int>> qu;
for (int i = 0; i <= a; i++) {
for (int k = 0; k <= b; k++) {
if (zz[i][k]) {
qu.push({i, k});
}
}
}
while (qu.size()) {
auto p = qu.front();
if (p.first < a) {
zz[p.first + 1][p.second] = 1;
}
if (p.second < b) {
zz[p.first][p.second + 1] = 1;
}
qu.pop();
}
while (wz <= r && pii[wz].first == t) {
int sz = pii[wz].second.second;
if (pii[wz].second.first == 1) {
for (int i = 0; i <= b; i++) {
zz[sz][i] = 0;
}
} else {
for (int i = 0; i <= a; i++) {
zz[i][sz] = 0;
}
}
wz++;
}
int pd = 0;
for (int i = 0; i <= a; i++) {
for (int k = 0; k <= b; k++) {
if (zz[i][k]) {
pd = 1;
}
}
}
if (!pd) {
t = -1;
break;
}
}

cout << t << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## G1. In Search of Truth (Easy Version)

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
//#define endl "
"
//#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

map<LL, int> mp;

void solve() {
LL x;
cin >> x;
LL sum = 0;

for (int i = 1; i <= 1000; ++i) {
cout << "+ 1" << endl << endl;
cin >> x;
sum += 1;
if (!mp.contains(x)) {
mp.insert({x, sum});
} else {
cout << "! " << sum - mp[x] << endl;
return;
}
}
for (int i = 1; i <= 1000; ++i) {
cout << "+ 1000" << endl << endl;
cin >> x;
sum += 1000;
if (!mp.contains(x)) {
mp.insert({x, sum});
} else {
cout << "! " << sum - mp[x] << endl;
}
}
}

signed main() {
//    ios;
int T = 1;
//    cin >> T;
while (T--) {
solve();
}
}
``````

## G2. In Search of Truth (Hard Version)

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <chrono>
#include <random>
//#define endl "
"
//#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

map<LL, LL> mp;

LL max_, res = 0x3f3f3f3f;
LL sum;

cout << "+ " << x << endl;
sum += x;
cin >> x;
if (mp.contains(x)) {
res = min(res, sum - mp[x]);
}
mp[x] = sum;
max_ = max(max_, x);
}

void solve() {
int x;
cin >> x;
mp.insert({x, 0});
for (int i = 1; i < 333; i++) {
}
for (int i = 1; i < 333; i++) {
}
for (int i = 1; i < 333; i++) {
}
cout << "! " << res << endl;
}

signed main() {
//    ios;
int T = 1;
//    cin >> T;
while (T--) {
solve();
}
}
``````