首页 > 其他分享 >Codeforces Round #820 (Div. 3) A-G

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

时间：2022-11-02 17:16:49浏览次数：72  
标签：cout int 复杂度 Codeforces tot solve long Div 820

比赛链接

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;
}

标签：cout,int,复杂度,Codeforces,tot,solve,long,Div,820
From： https://www.cnblogs.com/BlankYang/p/16851597.html

相关文章

  • Codeforces Round #611 (Div. 3) E
    E.NewYearParties对于最大值我们显然可以sort之后贪心一下即可正确性显然对于最小值我们发现会有三种情况一种是三个挨在一起一种是两个挨在一起还有一种就是......
  • div'可拖拽宽度
    <template><divclass="x-handle"@mousedown="mouseDown"></div></template><script>exportdefault{name:'HandleEvent',data(){return{lastX:''......
  • J - Just Arrange the Icons CodeForces - 1267J （思维+暴力）
    题意n个软件，每个软件都有种类，而屏幕有容量s(自己决定)，有两个限制：一个屏幕只能放s-1或者s个软件一个屏幕上只能防同种的软件求最小的屏幕数。思路枚举s代......
  • 「题解」Codeforces 1322B Present
    看上去异或里面套了层加法不好拆位，但是依然可以对每个二进制位处理。现在考虑第\(k\)位，那么产生贡献的数字对一定满足以下条件之一：第\(k\)位相同且前\((k-1)\)位......
  • 「题解」Codeforces 930E Coins Exhibition
    看到题就先容斥。然后容斥系数太难算了就寄了，大概要分好几种情况讨论，于是就弃了。不容斥也能做。考虑限制将串划分成了若干段，然后一段一段dp．有没有什么好的方法描述这个......
  • 洛谷 P8820 [CSP-S 2022] 数据传输 题解
    首先考虑对于每一次询问暴力DP。设\(f_{u,i}\)表示从\(s\)开始，传到一个到\(u\)距离为\(i\)的点，需要的最短时间。当\(k=3\)时，可能会传到不在\(s\tot\)路......
  • Codeforces - 1391C - Cyclic Permutations（思维 + 组合数学 + 数论 + 图论、*1500）
    1391C-CyclicPermutations（⇔源地址）目录1391C-CyclicPermutations（⇔源地址）tag题意思路AC代码错误次数：0tag⇔思维、⇔组合数学、⇔数论、⇔......
  • Codeforces Round #611 (Div. 3) D
    D.ChristmasTrees显然对于一个中间的点要是不能向两边最近的扩展我们直接判定他没有用处了这样我们就有了bfs的做法我们先把原点放进去要是能扩展我们显然可以直接......
  • Codeforces Round #667 (Div. 3) ABCD
    https://codeforces.com/contest/1409A.YetAnotherTwoIntegersProblem题目大意：k∈[1;10]我们每次可以选择a:=a+kora:=a−k问a要经历多少次操作变成b？input......
  • Codeforces 1730 D
    Codeforces1730D题意定义一次“操作”为把字符串$a$的前$k$个字母与字符串$b$的后$k$个字母交换。问能不能经过有限次操作后，让$a=b$。注：$......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99