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

Codeforces Round 927 (Div. 3)

时间：2024-02-19 19:45:12浏览次数：28  
标签：int ll Codeforces long back vector using Div 927

Codeforces Round 927 (Div. 3)

A - Thorns and Coins

解题思路:

出现连续两个障碍之前，所有金币都能拿到。

代码:

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

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '@')
        {
            ans++;
        }
        else if (s[i] == '*')
        {
            if (i - 1 > 0 && s[i - 1] == s[i])
            {
                break;
            }
        }
    }
    cout << ans << endl;
}

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

B - Chaya Calendar

解题思路:

遍历，找到大于已过当前年的最小倍数。

代码:

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

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll cur = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            cur = a[i] + 1;
        }
        else
        {
            ll k = (cur + (a[i] - 1)) / a[i];
            cur = k * a[i] + 1;
        }
    }
    cout << cur - 1 << endl;
}

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

C - LR-remainders

解题思路:

从全部开始删不好搞，我们先按步骤走到最后一点，然后反着加起来。

代码:

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

void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n + 1, 1);
    ll ans = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    string s;
    cin >> s;
    int l = 1;
    int r = n;
    int idx = 0;
    for (auto c : s)
    {
        if (c == 'L')
        {
            l++;
        }
        else
        {
            r--;
        }
    }
    reverse(s.begin(), s.end());
    vector<int> v;
    for (auto c : s)
    {
        if (c == 'L')
        {
            l--;
            ans = ans * a[l] % m;
        }
        else
        {
            r++;
            ans = ans * a[r] % m;
        }
        v.push_back(ans);
    }
    for (int i = v.size() - 1; i >= 0; i--)
    {
        cout << v[i] << ' ';
    }
    cout << endl;
}

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

D - Card Game

解题思路:

模拟吐了。

代码:

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

void solve()
{
    int n;
    cin >> n;
    string jok;
    cin >> jok;
    map<char, int> q;
    q['C'] = 1;
    q['D'] = 2;
    q['H'] = 3;
    q['S'] = 4;
    map<int, char> inv;
    inv[1] = 'C';
    inv[2] = 'D';
    inv[3] = 'H';
    inv[4] = 'S';
    vector<vector<int>> cards(10, vector<int>());
    for (int i = 1; i <= 2 * n; i++)
    {
        string t;
        cin >> t;
        int x = q[t[1]];
        cards[x].push_back(t[0] - '0');
    }
    for (int i = 1; i <= 4; i++)
    {
        sort(cards[i].begin(), cards[i].end());
    }
    // for (int i = 1; i <= 4; i++)
    // {
    //     for (auto x : cards[i])
    //     {
    //         cout << x << ' ';
    //     }
    //     cout << endl;
    // }
    vector<pair<string, string>> ans;
    for (int i = 1; i <= 4; i++)
    {
        // cerr << i << endl;
        if (q[jok[0]] == i)
        {
        }
        else
        {
            int len = cards[i].size();
            for (int j = len - 1; j >= 1; j -= 2)
            {
                // cerr << j << ' ';
                int a = cards[i].back();
                cards[i].pop_back();
                int b = cards[i].back();
                cards[i].pop_back();
                char cb = char('0' + b);
                string tb;
                tb.push_back(cb);
                tb.push_back(inv[i]);
                char ca = '0' + a;
                string ta;
                ta.push_back(ca);
                ta.push_back(inv[i]);
                ans.push_back({tb, ta});
            }
            // cerr << endl;
        }
    }
    for (int i = 1; i <= 4; i++)
    {
        if (q[jok[0]] != i)
        {
            while (!cards[i].empty())
            {
                int a = cards[i].back();
                cards[i].pop_back();
                if (cards[q[jok[0]]].size())
                {
                    int b = cards[q[jok[0]]].back();
                    cards[q[jok[0]]].pop_back();
                    char cb = char('0' + b);
                    string tb;
                    tb.push_back(cb);
                    tb.push_back(jok[0]);
                    char ca = '0' + a;
                    string ta;
                    ta.push_back(ca);
                    ta.push_back(inv[i]);
                    ans.push_back({ta, tb});
                }
                else
                {
                    puts("IMPOSSIBLE");
                    return;
                }
            }
        }
    }
    if (cards[q[jok[0]]].size())
    {
        int len = cards[q[jok[0]]].size();
        for (int j = len - 1; j >= 1; j -= 2)
        {
            int a = cards[q[jok[0]]].back();
            cards[q[jok[0]]].pop_back();
            int b = cards[q[jok[0]]].back();
            cards[q[jok[0]]].pop_back();
            char cb = char('0' + b);
            string tb;
            tb.push_back(cb);
            tb.push_back(inv[q[jok[0]]]);
            char ca = '0' + a;
            string ta;
            ta.push_back(ca);
            ta.push_back(inv[q[jok[0]]]);
            ans.push_back({tb, ta});
        }
    }
    for (int i = 1; i <= 4; i++)
    {
        if (cards[i].size())
        {
            puts("IMPOSSIBLE");
            return;
        }
    }
    for (auto t : ans)
    {
        cout << t.fi << ' ' << t.se << endl;
    }
}

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

E - Final Countdown

解题思路:

举例:\(12345 \to 12345 + 1234 + 123 + 12 + 1 = 13715\)

显然，全部加起来，边除边模往上进位即可。

代码:

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

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        if (s[i] != '0')
        {
            s = s.substr(i);
            break;
        }
    }
    n = s.size();
    s = ' ' + s;
    vector<ll> pre(n + 10, 0);
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + (s[i] - '0');
    }
    string ans;
    ll res = 0;
    for (int i = n; i > 0; i--)
    {
        char c = (pre[i] % 10) + '0';
        ans += c;
        if (i > 1)
        {
            pre[i - 1] += pre[i] / 10;
        }
        else
        {
            res += pre[i] / 10;
        }
    }
    while (res)
    {
        char c = (res % 10) + '0';
        res /= 10;
        ans += c;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

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

F - Feed Cats

解题思路:

\(dp[i]:考虑前i个点的选取，能得到的最大线段数。\)

  • 如果选第\(i\)个点，那么我们要找到覆盖点\(i\)的线段中，最小的左端点位置\(idx\)，\(dp[i] \leftarrow dp[idx - 1] + cnt\)。其中，\(cnt\)为经过点\(i\)的线段数量。
  • 如果不选第\(i\)个点，就是考虑前\(i\)个点得到的最大答案\(dp[i] \leftarrow dp[i - 1]\)。

代码:

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

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> l(n + 1, vector<int>());
    vector<int> d(n + 10);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        l[b].push_back(a);
        d[a]++;
        d[b + 1]--;
    }
    for (int i = 1; i <= n; i++)
    {
        d[i] += d[i - 1];
    }
    // 左侧最远可影响i处的点。
    vector<int> w(n + 10, n + 1);
    for (int i = n; i; i--)
    {
        w[i] = min(i, w[i + 1]);
        for (auto x : l[i])
        {
            w[i] = min(w[i], x);
        }
    }
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i - 1], dp[w[i] - 1] + d[i]);
    }
    cout << dp[n] << endl;
}

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

G - Moving Platforms

解题思路:

\((u,v)\)之间连通情况。

根据题意，\(l_u + ks_u \equiv l_v + ks_v \mod h\)

\[k(s_u - s_v) \equiv l_v - l_u \mod h \\ \]

\[k(s_u - s_v) + h y = l_v - l_u \]

扩展欧几里得解不定方程，得到\((k_0, y_0)\)。\(gcd((s_u - s_v),h) = d\)

根据裴蜀定理,判断是否有解，如果无解，就无法连边。

特解\((k_0,y_0)\)，通解为\((k_0 + t\frac{h}{d},y_0 - t\frac{s_u - s_v}{d})\)

求最小非负整数\(k\)，以及合法时间点间隔\(\frac{h}{d}\)。

然后跑最短路。转移时找到最近合法可转移的时间进行转移。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 50;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

struct node
{
    ll v, st, step;
};

void solve()
{
    ll n, m, h;
    cin >> n >> m >> h;
    vector<ll> l(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    vector<vector<node>> e(n + 1, vector<node>());
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ll c = l[v] - l[u];
        ll a = s[u] - s[v];
        ll b = h;
        ll x, y;
        ll d = exgcd(a, b, x, y);
        if (c % d)
        {
            continue;
        }
        ll step = abs(b / d);
        ll k = c / d % step;
        x = x * k % step;
        x = ((x % step) + step) % step;
        e[u].push_back((node){v, x, step});
        e[v].push_back((node){u, x, step});
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    vector<ll> dist(n + 1, inf);
    dist[1] = 0;
    vector<bool> vis(n + 1);
    q.push({dist[1], 1});
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int u = t.se;
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (auto x : e[u])
        {
            ll v = x.v;
            ll sp = x.st;
            ll step = x.step;
            // 找到最小合法转移时间
            if (dist[u] > sp)
            {
                sp += (dist[u] - sp + (step - 1)) / step * step;
            }
            if (dist[v] > sp + 1)
            {
                dist[v] = sp + 1;
                q.push({dist[v], v});
            }
        }
    }
    if (dist[n] >= inf)
    {
        puts("-1");
    }
    else
    {
        cout << dist[n] << endl;
    }
}

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

标签：int,ll,Codeforces,long,back,vector,using,Div,927
From： https://www.cnblogs.com/value0/p/18021816

相关文章

  • D. Divisible Pairs
    原题链接题解如果\((a_i+a_j)\mod\x==0\)那么\((a_i\mod\x+a_j\mod\x)\mod\x==0\)如果\((a_i-a_j)\mod\y==0\)那么\(a_i\mod\y==a_j\mod\y\)所以我们可以把每个\(a\)的求模情况存下来，\(a[i]\)的贡献为其前面的\(a\)出现的对应求模情况数量\(co......
  • Codeforces Round 927 (Div. 3)
    CodeforcesRound927(Div.3)C.LR-remaindersDescription给定一个长度为\(n\)的数组\(a\)和\(n\)个指令，每条指令为\(\texttt{L,R}\)中的一种。依次处理每个指令：首先，输出\(a\)中所有元素的乘积除以\(m\)的余数。然后，如果当前指令为\(\textttL\)，则移除数组......
  • Codeforces Round 927 (Div. 3)
    A传送门  根据题意每一步只能走一步或者两步,很显然如果有连续的两个荆棘就不能走了，在不能走之前是一定可以把路上的金币全捡起来所以只需要边捡金币边判断是否能继续走下即可。#include<bits/stdc++.h>usingll=longlong;typedefstd::pair<int,int>PII;typedef......
  • Codeforces Round 923 (Div. 3)
    A.MakeitWhite#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingi128=__int128;usingldb=longdouble;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;usingvii......
  • Codeforces 1661F Teleporters
    先考虑贪心，令\(f(x,k)\)为满足\(\sum\limits_{i=1}^ks_i=x,s_i\in\mathbb{N}_+\)的\(s\)的\(\sum\limits_{i=1}^ks_i^2\)的最小值。也就是题目中在两个固定的点中放\(k-1\)个点这两个点中的最小贡献。平均分肯定是最优的，可以通过\(x\bmodk\)的值\(O(......
  • CF926 Div.2
    C.SashaandtheCasino赌场规则：如果下注\(y(y>0)\)元，如果赢了则除了\(y\)元外，额外获得\(y\times(k-1)\)元，否则则输掉\(y\)元；并且你不能连续输超过\(x\)次最初，你有\(a\)枚硬币，询问是否能够赢取任意数量的硬币题解：思维考虑这样一种策略：假设前面一直输，保......
  • SMU Winter 2024 div2 ptlks的周报Week 3（2.12-2.18）
    这周主要加强了对知识点的掌握。P10161[DTCPC2024]小方的疑惑10从题目可以得知a个连续括号贡献为a(a+1)/2，代价为2a。要求总贡献恰为k，且代价不高于n。一开始我想到了模拟，先取一个贡献低于k最大的a，剩下的再直接在外面套括号，结果wa。又想到可以分出多个a来组成k，就用递归，每次......
  • Codeforces Round 903 (Div. 3)
    题目链接A.按题意模拟字符串find函数if(x.find(s)==string::npos)//没找到#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,m;cin>>n>>m;stringx,s;cin>>x&g......
  • CF1929 Codeforces Round 926 (Div. 2)
    C.SashaandtheCasino当\(k<x\)时,显然我们只需要每次下注一个硬币就好了.当\(k>x\)时.考虑先一个一个的下硬币,那么为了保证不亏本,最多输\(k-2\)局,然后在第\(k-1\)局赢,这样才能盈利\(1\)个硬币.那么在第\(k\)局之后呢?此时我们最少也需要下注两个硬币,这......
  • 【赛后反思】【LGR-175 Div.4】 洛谷入门赛#20 赛后反思
    洛谷入门赛#20赛后反思今日推歌：《水与水之歌feat.绮萱》きくお呆在这里直到精神恍惚为止让我们一起快乐地玩耍我们术术人有自己的《让我们荡起双桨》（大雾Before先看结果（是同步赛的成绩，因为前一天晚上我在死磕dfs）：省流：暴力-纯度75%STL-纯度25%展开目录目录洛谷入......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99