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

Codeforces Round 933 (Div. 3)

时间：2024-03-12 22:46:52浏览次数：35  
标签：int ll Codeforces long pair 933 using Div define

Codeforces Round 933 (Div. 3)

A - Rudolf and the Ticket

解题思路：

暴力。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i] + b[j] <= k)
            {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B - Rudolf and 121

解题思路:

从左到右变成\(0\)即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 2; i <= n - 1; i++)
    {
        if (a[i - 1] < 0)
        {
            puts("NO");
            return;
        }
        a[i] -= a[i - 1] * 2;
        a[i + 1] -= a[i - 1];
        a[i - 1] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != 0)
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - Rudolf and the Ugly String

解题思路:

\(mapie,map, pie\)都一次能消掉。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i + 4 <= n)
        {
            string t = s.substr(i, 5);
            if (t == "mapie")
            {
                cnt++;
                i = i + 4;
                continue;
            }
        }
        if (i + 2 <= n)
        {
            string t = s.substr(i, 3);
            if (t == "map" || t == "pie")
            {
                cnt++;
                i = i + 2;
            }
        }
    }
    cout << cnt << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D - Rudolf and the Ball Game

解题思路:

\(O(nm)\)，直接暴力模拟转移。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n, m, x;
    cin >> n >> m >> x;
    vector<bool> dp(n + 1, false);
    dp[x] = true;
    for (int j = 1; j <= m; j++)
    {
        vector<bool> cur(n + 1, false);
        int d;
        char t;
        cin >> d >> t;
        if (t == '0')
        {
            for (int i = 1; i <= n; i++)
            {
                int idx = (i - 1 + d) % n + 1;
                cur[idx] = cur[idx] | dp[i];
            }
        }
        else if (t == '1')
        {
            for (int i = 1; i <= n; i++)
            {
                int idx = (((i - 1 - d) % n) + n) % n + 1;
                cur[idx] = cur[idx] | dp[i];
            }
        }
        else
        {
            for (int i = 1; i <= n; i++)
            {
                int idx = (((i - 1 - d) % n) + n) % n + 1;
                cur[idx] = cur[idx] | dp[i];
                idx = (i - 1 + d) % n + 1;
                cur[idx] = cur[idx] | dp[i];
            }
        }
        dp = cur;
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (dp[i])
        {
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for (auto c : ans)
    {
        cout << c << ' ';
    }
    cout << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E - Rudolf and k Bridges

解题思路:

单调队列优化\(dp\)求取每一列的建桥的最小花费。然后取最小连续段。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n, m, k, d;
    cin >> n >> m >> k >> d;
    vector<vector<ll>> a(n + 1, vector<ll>(m + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if (j != 1 && j != m)
            {
                a[i][j]++;
            }
        }
    }
    vector<ll> ans(1, 0);
    for (int i = 1; i <= n; i++)
    {
        vector<ll> q(m + 1);
        int hh = 0;
        int tt = -1;
        vector<ll> dp(m + 1);
        for (int j = 1; j <= m; j++)
        {
            while (hh <= tt && j - (q[hh]) > d + 1)
            {
                hh++;
            }
            dp[j] = a[i][j];
            if (hh <= tt)
            {
                dp[j] += dp[q[hh]];
            }
            // cerr << i << ' ' << j << ' ' << dp[j] << endl;
            while (hh <= tt && dp[j] < dp[q[tt]])
            {
                tt--;
            }
            q[++tt] = j;
        }
        // cerr << dp[m] << endl;
        ans.push_back(dp[m]);
    }
    for (int i = 1; i <= n; i++)
    {
        ans[i] += ans[i - 1];
    }
    ll res = 1e18;
    for (int i = 1; i <= n; i++)
    {
        if (i >= k)
        {
            res = min(res, ans[i] - ans[i - k] + k * 2);
        }
    }
    cout << res << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

F - Rudolf and Imbalance

解题思路:

找到最大间距和次大间距。

如果最大间距不止一个，答案就是最大间距。

否则想要减小最大间距，就是要往最大间距之间添数字，对于每个\(d\)找能将间距尽量均分，然后和次大间距取较小。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n + 1), d(m + 1), f(k + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> d[i];
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> f[i];
    }
    sort(a.begin() + 1, a.end());
    sort(d.begin() + 1, d.end());
    sort(f.begin() + 1, f.end());
    ll dist = -1;
    ll sd = -1;
    int cnt = 0;
    ll l = 0;
    ll r = 0;
    for (int i = 2; i <= n; i++)
    {
        ll t = a[i] - a[i - 1];
        if (t > dist)
        {
            if (dist != -1)
            {
                sd = dist;
            }
            dist = t;
            cnt = 1;
            l = a[i - 1];
            r = a[i];
        }
        else if (t == dist)
        {
            cnt++;
            sd = dist;
        }
        else
        {
            if (sd < t)
            {
                sd = t;
            }
        }
    }
    if (cnt > 1)
    {
        cout << dist << endl;
        return;
    }
    // cerr << l << ' ' << sd << endl;
    ll ans = dist;
    ll mid = (l + r + 1) / 2;
    for (int i = 1; i <= m; i++)
    {
        ll x = mid - d[i];
        auto it = lower_bound(f.begin() + 1, f.end(), x);
        if (it != f.end())
        {
            x = *it;
            ll t = d[i] + x;
            if (t >= l && t <= r)
            {
                ans = min(ans, max(r - t, t - l));
                if (sd != -1)
                {
                    ans = max(ans, sd);
                }
            }
        }
        if (it != f.begin() + 1)
        {
            it--;
            x = *it;
            ll t = d[i] + x;
            if (t >= l && t <= r)
            {
                ans = min(ans, max(r - t, t - l));
                if (sd != -1)
                {
                    ans = max(ans, sd);
                }
            }
        }
        // cerr << i << ' ' << d[i] << ' ' << x << endl;
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

G - Rudolf and Subway

解题思路:

根据某些点或者边的分类特点减虚点。

将原图转化到和虚点相连的图，然后在上面操作。

本题将点与颜色虚点建边，点到颜色单向边权值为\(1\)，颜色向点建单向边权值为\(0\)。

跑\(01bfs\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;

void solve()
{
    map<int, int> mp;
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> e(n + m + 1, vector<pii>());
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (mp.find(c) == mp.end())
        {
            mp[c] = ++n;
        }
        c = mp[c];
        e[a].push_back({c, 1});
        e[c].push_back({a, 0});
        e[b].push_back({c, 1});
        e[c].push_back({b, 0});
    }
    deque<int> q;
    int st, ed;
    cin >> st >> ed;
    q.push_front(st);
    vector<ll> dist(n + 1, inf);
    vector<bool> vis(n + 1, false);
    dist[st] = 0;
    while (q.size())
    {
        auto u = q.front();
        q.pop_front();
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (auto t : e[u])
        {
            auto v = t.fi;
            auto w = t.se;
            // cerr << u << ' ' << v << endl;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (w)
                {
                    q.push_back(v);
                }
                else
                {
                    q.push_front(v);
                }
            }
        }
    }
    cout << dist[ed] << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签：int,ll,Codeforces,long,pair,933,using,Div,define
From： https://www.cnblogs.com/value0/p/18069521

相关文章

  • D. Divide by three, multiply by two
    https://codeforces.com/contest/977/problem/Dvoidsolve(){intn;cin>>n;vector<pair<int,longlong>>a(n);for(auto&[x,y]:a){cin>>y;x=0;longlongtemp=y;while(......
  • Codeforces Round 933 (Div. 3)
    A.RudolfandtheTicket#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingldb=longdouble;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;constintinf=1e9;co......
  • 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\)。你可以对它进行两种运......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99