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

吐槽在前面

太菜了赛后6min过掉的G1，本来以为是因为G1没出没上蓝，结果System Test直接给我C题卡掉了，一看发现我数组开小了一倍，最后险些掉分。

总之就是状况频出的滑铁卢战役qwq。

A. Cipher Shifer

题目大意

给你一个加密过的字符串，加密方式是对原串的每个字符做如下操作：

在他的后面加上任意多的任意字母，再加上这个字母本身。

这样得到一个很长的串，现在要解出原串。

解题思路

我们发现，不管怎么变换，原串中的字符都是两次连续出现的，而题目又说保证解唯一，那么就不存在加入的字母含有原字母的情况，所以只需要从第一个字符开始找相同字母即可，中间其他的字母全部忽略。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#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

题目大意

咖啡馆提供 \(k\) 种甜点，标号 \(0 \sim k - 1\) ，第 \(i\) 种咖啡的花费是 \(2^i\)。现在手上有 \(n\) 元，问最多能有多少种方式买甜点。

解题思路

首先看样例就猜出答案啦。

实际上有 \(2^i\)，我们就可以通过二进制的方式理解，因为每个数都可以表示成二进制，那么我们只需要比较上界，如果 \(2^k\) 大一些，那么就有 \(n + 1\) 种选法，多的一种是什么都不点的情况。如果 \(n\) 大的话，就有 \(2 ^ k\) 种选法，也就是 \(1+\sum_{i=0}^{k-1}2^i\)。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#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

题目大意

给定 \(n, k, q\)，分别代表数组元素个数，最小长度，最大温度。

接下来需要我们在数列中找满足连续至少 \(k\) 天温度都低于 \(q\) 的选择方案数。

解题思路

我们可以计数连续的低于 \(q\) 的天数，注意到大于 \(k\) 天的部分可以扩散出去，在原结果的基础上进行计算，最后得到一段长度为 \(cnt\) 的部分，对方案的贡献是 \(\frac{(cnt - k + 1) \times (cnt - k + 2)}{2}\)。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#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

题目大意

有三名雕刻师，每个人可以选择一个基准值 \(c_i\)，有 \(n\) 个玩具需要雕刻，他们的花样是 \(a_j\)，那么第 \(i\) 个雕刻师制作第 \(j\) 个玩具需要的时间就是 \(|c_i - a_j|\)，现在想求最大制作时间的最小值。

解题思路

求最大的最小值明显是二分题，我们可以二分时间，检验的时候，就看模拟过程中需要的雕刻师傅会不会多于三个即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#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

题目大意

给出两个串，然后给出 \(q\) 次操作，每秒执行一次，分别是：

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

解题思路

题目已经把我们需要做的全部说清楚了，所以这是个模拟题，现在要考虑如何实现。封锁我们可以通过一个队列实现，每次操作的时候正好也是时间过去 \(1s\)，那么就可以弹出队头模拟时间流动。其次是判断两个串是否相等，可以用一个计数变量记录串有几个不同字符，如果封锁或者交换，我们可以重新对这个变量进行加减调整。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define endl '\n'
#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

题目大意

起始位于坐标点\((0,0)\)，需要到达坐标点\((n,m)\)。每次移动可以使得横坐标或者纵坐标加一，也可以选择不动。外星人会发射 \(r\) 次激光炮，每次会贯穿一行或者一列。如果射击时处在射击轨道上就寄了，那么问到达目的地的最短时间是多少。

解题思路

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 '\n'
#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)

题目大意

这是一个交互题，游戏设置在一个圆盘上，有 \(n\) 个数在圆盘上，\(i \in [1, n]\)，现在我们可以让圆盘指针顺时针或者逆时针移动 \(k\) 格，控制台回显指向的数，要在 \(2023\) 次询问内找到 \(n\) 值。

解题思路

我们使用 \(2000\) 次询问，前 \(1000\) 次询问顺时针移动 \(1\) 格，后 \(1000\) 次询问移动 \(1000\) 格。我们使用一个map存起来所有回显的值以及此时我们移动的总格数，直到我们遇到两个一样的数，第二次遇到它时移动的总格数减去我们存在map里面的值就是答案 \(n\)。由于数据范围在 \(1 \le n \le 10^6\) 所以这种情况下是一定可以遇到两个一样的数的。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
//#define endl '\n'
//#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)

题目大意

和G1一样，但是我们只能使用 \(1000\) 次以内的询问完成查询。

解题思路

这种情况下我们不能保证能得到答案，但是可以通过随机数取值使得 \(1000\) 次内得到答案的概率相当高，可以用mt19937来完成。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <chrono>
#include <random>
//#define endl '\n'
//#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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

LL max_, res = 0x3f3f3f3f;
LL sum;

void ask(LL x) {
    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++) {
        ask(rng() % (100000) + 1);
    }
    for (int i = 1; i < 333; i++) {
        ask(1);
    }
    ask(max_);
    for (int i = 1; i < 333; i++) {
        ask(200);
    }
    cout << "! " << res << endl;
}

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

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• AT_arc125_c [ARC125C] LIS to Original Sequence 题解
• P5321 [BJOI2019] 送别 题解--zhengjun
• P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version) 题解
• P2198 杀蚂蚁 题解
• P3243 [HNOI2015] 菜肴制作 题解
• AT_abc243_g [ABC243G] Sqrt题解
• AT_abc243_g [ABC243G] Sqrt题解
• P9754 题解
• AT_arc167_e 题解

题解 Codeforces Round 878 Divcodeforces round 878 div codeforces round div3 878 题解codeforces round 878 题解codeforces div round 题解codeforces round div2 题解codeforces round div3 codeforces resort round 878 codeforces round 911 div codeforces round 864 div codeforces round 887 div