首页 > 其他分享 >Codeforces Round 933 (Div. 3)

Codeforces Round 933 (Div. 3)

时间：2024-03-12 21:22:06浏览次数：17  
标签：int vi Codeforces long vector 933 using Div TC

A. Rudolf and the Ticket

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vi a(n), b(m);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    int res = 0;
    for (auto &i: a)
        for (auto &j: b)
            if (i + j <= k) res++;

    cout << res << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

B. Rudolf and 121

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);

vector<pii> path;

void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    int f = 1;
    for (int i = 0; f and i + 2 < n; i++) {
        if (a[i] < 0) f = 0;
        else if (a[i] == 0) continue;
        a[i + 1] -= a[i] * 2, a[i + 2] -= a[i], a[i] = 0;
    }
    if (a[n - 2] != 0 or a[n - 1] != 0) f = 0;
    if (f) cout << "YES\n";
    else cout << "NO\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

C. Rudolf and the Ugly String

TC = int(input())

for _ in range(TC):
    n = int(input())
    s = input()
    a = s.count("map")
    b = s.count("pie")
    c = s.count("mapie")
    print(a + b - c)

D. Rudolf and the Ball Game

只要保证当前没有重复的状态，则总状态数不超过\(2\cdot10^5\)

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);

vector<pii> path;

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    set<int> f;
    f.insert(x - 1);
    string op;
    for (int r; m; m--) {
        cin >> r >> op;
        set<int> g;
        if (op == "0") {
            for (auto i: f)
                g.insert((i + r) % n);
        } else if (op == "1") {
            for (auto i: f)
                g.insert((i - r + n) % n);
        } else {
            for (auto i: f)
                g.insert((i - r + n) % n), g.insert((i + r) % n);
        }
        f.swap(g);
    }
    cout << f.size() << "\n";
    for (auto &i: f)
        cout << i + 1 << " ";
    cout << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

E. Rudolf and k Bridges

如果可以每一行都 dp 出答案，然后双指针扫描出最优解即可。

对于单行的 dp，首先\(f[i]\)表示把桥修到\(i\)的最小花费，转移看似是\(O(d)\)但实际上只要区间最小值，所以可以用set维护前\(d\)个状态即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = LLONG_MAX;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);

vector<pii> path;

void solve() {
    int n, m, k, d;
    cin >> n >> m >> k >> d, d++;
    vi g(n), a(m), f(m);
    for (auto &val: g) {
        for (auto &i: a) cin >> i;
        multiset<int> cnt;
        cnt.insert(1), f[0] = 1;
        for (int i = 1; i < m; i++) {
            f[i] = *cnt.begin() + a[i] + 1;
            cnt.insert(f[i]);
            if (cnt.size() > d) cnt.erase(cnt.find(f[i - d]));
        }
        val = f.back();
    }
    int res = inf, cnt = 0;
    for (int i = 0; i < k - 1; i++)
        cnt += g[i];
    for (int l = 0, r = k - 1; r < n; l++, r++)
        cnt += g[r], res = min(res, cnt), cnt -= g[l];
    cout << res << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

F. Rudolf and Imbalance

首先我们要使得最大值减小，这必要在最大值的所在的区间内内插入一个值。

如果最大区间是\([l,r]\)，插入的值是\(x\)，次大值是\(ans2\)，则答案就是\(\max(x - l , r - x , ans2)\)

所以，如果可以枚举\(d_i\)则对于\(f_j\)答案就是一个单谷函数，我们找到离\([l-x,r-x]\)最近的点就是当前的最优解。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = LLONG_MAX;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);

vector<pii> path;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vi a(n), d(m), f(k);
    for (auto &i: a) cin >> i;
    for (auto &i: d) cin >> i;
    for (auto &i: f) cin >> i;

    int ans = -1, L, R, ans2 = -1;
    for (int i = 1, x; i < n; i++) {
        x = a[i] - a[i - 1];
        if (x > ans) ans2 = ans, ans = x, L = a[i - 1], R = a[i];
        else ans2 = max(ans2, x);
    }
    if (ans == ans2) {
        cout << ans << "\n";
        return;
    }
    sort(f.begin(), f.end());
    int res = ans;
    int mid;
    for (auto &di: d) {
        if (di + f.front() >= R) continue;
        if (di + f.back() <= L) continue;
        mid = (L + R) / 2 - di;
        mid = lower_bound(f.begin(), f.end(), mid) - f.begin();

        for (int i = max(0ll, mid - 5); i <= min(k - 1, mid + 5); i++)
            res = min(res, max({ans2, abs(f[i] + di - L), abs(f[i] + di - R)}));
    }
    cout << res << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

G. Rudolf and Subway

把地铁线路抽象为若干个虚点，然后结点到地铁的权值为 1，地铁到节点的权值为 0，相当于上地铁花费 1，下地铁没有花费。然后求一下最短路即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = LLONG_MAX;
const int N = 1e4;

vi vis(N);
vector<vector<pii>> e(N);

vector<pii> path;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edge(m);
    vi line;
    for (auto &[x, y, z]: edge) cin >> x >> y >> z, line.push_back(z);
    sort(line.begin(), line.end());
    line.resize(unique(line.begin(), line.end()) - line.begin());
    vector<set<pii>> e(n + line.size() + 1);
    for (auto &[x, y, z]: edge) {
        z = lower_bound(line.begin(), line.end(), z) - line.begin() + n + 1;
        e[x].emplace(z, 1);
        e[y].emplace(z, 1);
        e[z].emplace(x, 0);
        e[z].emplace(y, 0);
    }
    int sta, ed;
    cin >> sta >> ed;
    vi dis(n + line.size() + 1, inf);
    dis[sta] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.emplace(0, sta);
    vi vis(n + line.size() + 1);
    while (not q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w]: e[u]) {
            if (vis[v]) continue;
            if (dis[v] > d + w) {
                dis[v] = d + w;
                q.emplace(dis[v], v);
            }
        }
    }
    cout << dis[ed] << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC = 1;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

标签：int,vi,Codeforces,long,vector,933,using,Div,TC
From： https://www.cnblogs.com/PHarr/p/18069319

相关文章

  • Codeforces Round 933 (Div. 3) A-F
    CodeforcesRound933(Div.3)A.RudolfandtheTicket题意：有两个数组\(b_n\)和\(c_m\),两个数组中分别取一个数相加是否小于k，有几种方法使\(b_f\)+\(c_s\)<=k思路：暴力枚举所有方案，时间复杂度O(nm)代码：#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e......
  • SMU Winter 2024 div2 ptlks的周报Week 5（3.4-3.10）
    维护子树的全部子树的权值和时，需要用到树的DFS序列，树的每个子树都对应DFS序列中的连续一段黄金树影题意：给定一棵树及每个节点的权值，给定一组操作，输入1ax，表示节点a权值加上x；输入2a，表示询问节点a的子树权值和（包含a）。考虑到树的DFS序列，则问题转变为对某个序列维护区间和以......
  • Codeforces Round 656 (Div. 3) F. Removing Leaves
    ProblemDescription给出一棵\(n\)个节点的无根树。你可以进行以下操作：选择\(k\)个共同父节点的叶子节点，将\(k\)个节点和与父节点相连的边删去。求最大操作次数。Input第一行输入一个整数\(t\)\((1\let\le2\times10^4)\)，表示测试组数。接下来每组测试数据第......
  • A. k-th divisor
    https://codeforces.com/problemset/problem/762/AThisisaeasyproblembasedonnumbertheory.Wejustsimplyiterateifrom1tothevalueofsqrt(n),andcheckifnisdivisblebythevalueofiandfindallofitsdivisors,thensortthemandgetthea......
  • Add, Divide and Floor
    我们不妨将这个式子看做取中点，然后就会发现每次操作不改变相对大小，然后看这篇洛谷题解解释一下他这个合理性，主要是害怕讨论每次操作后的\(a,b\)的奇偶而已这里其实官方题解给出了一个提示我们设最开始的\(b-a=x\)，那么根据这篇洛谷题解，而每次操作要么让\(x=\lfloor\frac{x}{2}......
  • 二进制变化_cf1+2_C. Divisor Chain
    目录题目概述思路想法参考代码做题反思题目概述原题参考：C.DivisorChain给出一个数x，可以对他做以下的变换若y是x的除数，x-=y任意的y不能使用超过两次可以证明的是，对于任意的数，都可以在1000次操作内将其变成1，请输出将x变为1的操作次数与过程思路想法首先是如果随机除以因......
  • Codeforces Round 932 (Div. 2)
    目录写在前面ABCDE写在最后写在前面比赛地址：https://codeforces.com/contest/1935。被精心构造的C的样例鲨了的一集。妈的天使骚骚☆REBOOT完全就是他妈拔作啊我草，要是被人知道我他妈推了全线要被笑话一辈子吧、、、A签到。操作偶数次，则答案仅可能为s或reverse(s)+s......
  • CF contest 1935 Round 932 (Div. 2) A-D题解
    CodeforcesRound932(Div.2)A-D题解CodeforcesRound932(Div.2)绪言很菜，AB速度慢，卡在C，想DP，但是时间优化不下来，说服自己\(2\times10^3\)能过\(n^3\)，D稍微简单，但是没看D，遂掉分。A.EntertainmentinMAC给你一个字符串\(s\)和一个偶整数\(n\)。你可以对它进行两种运......
  • Codeforces 专区
    CodeforcesRound#932（Div.2）怎么只会A啊。\(\text{ProblemA}\)题目大意对于一个字符串\(s\)，可以进行\(n\)次操作（\(n\)为偶数），每次操作有两种形式：令\(t\)为\(s\)的反串，\(s=s+t\)。令\(t\)为\(s\)的反串，\(s=t\)。要求操作完后\(s\)的字典序最小，并输......
  • Though Our Paths May Diverge（JSOI 2024 游记）
    Isn’titsupposedtobesunnynow?且当是JSOI2024的游记吧。省选前的精神状态处于一种微妙的平衡。确实也不断在给自己心理暗示，自己有省队水平，但是其实无论是哪边的模拟打得都属于比较稀烂的水平，有的时候真的是一题不会签不上到。跟不上zhy和黄色蜜蜂的节奏啊，大概就......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99