Codeforces Round #820 (Div. 3) A-G

乎语百科 2022-11-02 19:05:47 268 0

A

题解

知识点：模拟

时间复杂度 $O(1)$

空间复杂度 $O(1)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int x = a - 1;
    int y = abs(b - c) + c - 1;
    if (x > y) cout << 2 << '\n';
    else if (x < y) cout << 1 << '\n';
    else cout << 3 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

题解

知识点：模拟。

倒着来，很方便。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    string T;
    cin >> T;
    string S;
    for (int i = T.length() - 1;i >= 0;i--) {
        if (T[i] == '0') {
            S = (char)((T[i - 1] - '0') + (T[i - 2] - '0') * 10 + 'a' - 1) + S;
            i -= 2;
        }
        else {
            S = (char)(T[i] - '0' + 'a' - 1) + S;
        }
    }
    cout << S << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题解

知识点：贪心，枚举。

显然最小花费是 $|s[n]-a[1]|$ ，最大化路线的方式是按序走过 $s[1]$ 到 $s[n]$ 的所有字母。

把每个字母的下标放进桶中， $s[1]$ 比 $s[n]$ 小则从 $s[1]$ 正序，否则从 $s[1]$ 倒序。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    string s;
    cin >> s;
    int n = s.length();
    s = "?" + s;
    vector<vector<int>> v(26);
    for (int i = 1;i <= n;i++) {
        v[s[i] - 'a'].push_back(i);
    }
    int x = s[1] - 'a', y = s[n] - 'a';
    if (x < y) {
        int cnt = 0;
        for (int i = x;i <= y;i++) {
            cnt += v[i].size();
        }
        cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';
        for (int i = x;i <= y;i++)
            for (auto j : v[i]) cout << j << ' ';
    }
    else {
        int cnt = 0;
        for (int i = x;i >= y;i--) {
            cnt += v[i].size();
        }
        cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';
        for (int i = x;i >= y;i--)
            for (auto j : v[i]) cout << j << ' ';
    }
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题解

知识点：贪心，枚举，双指针。

处理出 $y-x$ 得到每个成员的贡献，从小到大排序，最小的和最大的两人一组即可最大化分组数量，不能分配就跳过较小的。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int diff[100007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> diff[i];
    for (int i = 1;i <= n;i++) {
        int y;
        cin >> y;
        diff[i] = y - diff[i];
    }
    sort(diff + 1, diff + n + 1);
    int ans = 0;
    int l = 1, r = n;
    while (l < r) {
        if (diff[l] + diff[r] >= 0) ans++, r--;
        l++;
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

E

题解

知识点：贪心。

$i$ 从 $2$ 开始依次询问。先询问 $(1,i)$ ，如果结果 $-1$ 则输出 $i-1$ ；否则，再询问一次 $(i,1)$ ，如果答案和 $(1,i)$ 不同则输出两个答案之和，否则继续下一个 $i$ 。除去特判 $n \in [3,25]$ 会因为询问到 $-1$ 结束的情况，其他情况只需要一组答案不同即可，概率很高。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll query(ll a, ll b) {
    cout << "? " << a << ' ' << b << endl;
    ll ans;
    cin >> ans;
    return ans;
}

void answer(ll x) {
    cout << "! " << x << endl;
    exit(0);
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (int i = 2;i;i++) {
        ll ans1 = query(1, i);
        if (!~ans1) answer(i - 1);
        ll ans2 = query(i, 1);
        if (ans1 != ans2) answer(ans1 + ans2);
    }
    return 0;
}

F

题解

知识点：枚举，前缀和，数论。

注意到一个数字 $\mod 9$ 的答案和所有数位加起来 $\mod 9$ 的答案相同，因此先对 $s$ 数位预处理模意义前缀和。

然后处理出所有 $w$ 长度的串的余数，把串首坐标放进桶中对应余数的位置，只需要存两个最左边的即可。

对于每组询问，遍历余数 $a,b$ 满足 $a \cdot re + b \equiv k \pmod 9$ ，其中 $re$ 为 $[l,r]$ 的余数。将余数 $a,b$ 对应的串下标更新一下答案即可，答案可以用 pair 存，方便更新。注意特判 $a = b$ 的情况，需要同一个余数的前两个下标。

时间复杂度 $O(n+m)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    string s;
    cin >> s;
    int n = s.length();
    s = "?" + s;
    for (int i = 1;i <= n;i++) a[i] = (s[i] - '0' + a[i - 1]) % 9;
    int w, m;
    cin >> w >> m;
    vector<vector<int>> pos(9);
    for (int i = w;i <= n;i++) {
        int re = (a[i] - a[i - w] + 9) % 9;
        if (pos[re].size() < 2) pos[re].push_back(i - w + 1);
    }
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        int re = (a[r] - a[l - 1] + 9) % 9;
        pair<int, int> ans = { n + 1,n + 1 };
        for (int i = 0;i <= 8;i++) {
            if (pos[i].empty()) continue;
            for (int j = 0;j <= 8;j++) {
                if (pos[j].empty()) continue;
                if ((i * re + j) % 9 == k) {
                    if (i != j) ans = min(ans, { pos[i][0],pos[j][0] });
                    else if (i == j && pos[i].size() == 2) ans = min(ans, { pos[i][0],pos[i][1] });
                }
            }
        }
        if (ans > pair<int, int>{n, n}) cout << -1 << ' ' << -1 << '\n';
        else cout << ans.first << ' ' << ans.second << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

G

题解

知识点：线性dp。

预处理出 $s$ 中所有能删除 $t$ 的下标，暴力 $O(n^2)$ 处理即可，存进 vector 。随后dp一下前 $i$ 个能删除位置的最小删除次数。

设 $f[i]$ 为考虑到第 $i$ 个能删除的位置，删除 $[1,v[i]]$ 所有能删除的段，且一定删除第 $i$ 段的最小删除次数。设 $tot[i]$ 为能够达成 $f[i]$ 删除次数的对应的方案数。

对于 $v[i]$ ，我们枚举上一个删除的位置 $v[j]$ ，先保证 $i,j$ 不重合即 $v[i]-v[j]\geq m$ ，然后保证 $i,j$ 中间没有别的能删除的段即 $v[k] - v[j] < m $ 以及 $ v[i] - v[k] < m$ 。于是可以转移：

if (f[i] > f[j] + 1) {
	f[i] = f[j] + 1;
	tot[i] = tot[j];
}
else if (f[i] == f[j] + 1) {
	tot[i] = (tot[i] + tot[j]) % mod;
}

最后统计末尾重合的一段的最小删除次数，以及对应的总方案数。

时间复杂度 $O(nm^2)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;

bool solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    s = "?" + s;
    vector<int> v;
    v.push_back(0);
    for (int i = m;i <= n;i++)
        if (s.substr(i - m + 1, m) == t) v.push_back(i);
    vector<int> f(507, 0x3f3f3f3f), tot(507, 0);
    f[0] = 0, tot[0] = 1;
    for (int i = 1;i < v.size();i++) {
        for (int j = i - 1;j >= 0;j--) {
            if (v[i] - v[j] < m) continue;
            bool ok = 1;
            for (int k = j + 1;k < i;k++) ok &= v[k] - v[j] < m || v[i] - v[k] < m;
            if (!ok) break;
            if (f[i] > f[j] + 1) {
                f[i] = f[j] + 1;
                tot[i] = tot[j];
            }
            else if (f[i] == f[j] + 1) {
                tot[i] = (tot[i] + tot[j]) % mod;
            }
        }
    }
    int mi = n, ans = 0;
    for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m) mi = min(mi, f[i]);
    for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m && f[i] == mi) ans = (ans + tot[i]) % mod;
    cout << mi << ' ' << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

标签：