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

Codeforces Round 834 (Div. 3)

时间：2023-10-10 17:14:36浏览次数：31  
标签：834 int Codeforces long ++ while using Div pn

A. Yes-Yes?

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

const string T = "Yes";

void solve() {
    string s;
    cin >> s;
    int i = -1;
    if( s[0] == 'Y' ) i = 0;
    else if( s[0] == 'e' ) i = 1;
    else if( s[0] == 's' ) i = 2;
    if( i == -1 ){
        cout << "NO\n";
        return ;
    }
    for( auto c : s ){
        if( c != T[i] ){
            cout << "NO\n";
            return ;
        }
        i = ( i + 1 ) % 3;
    }
    cout << "YES\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B. Lost Permutation

枚举序列的最大值

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int m, s, b = 0;
    cin >> m >> s;
    for (int i = 1, x; i <= m; i++)
        cin >> x, b = max(b, x), s += x;
    while (b * (b + 1) / 2 < s) b++;
    cout << (b * (b + 1) / 2 == s ? "YES\n" : "NO\n");
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Thermostat

情况数量不多

\[a=b\\ a\rightarrow b\\ a \rightarrow l \rightarrow b\\ a \rightarrow r \rightarrow b\\ a \rightarrow l \rightarrow r \rightarrow b\\ a \rightarrow r \rightarrow l \rightarrow b \]

逐个判断就好了

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int l, r, a, b, x;
    cin >> l >> r >> x >> a >> b;

    bool ab = abs(a - b) >= x;
    bool al = abs(a - l) >= x;
    bool ar = abs(a - r) >= x;
    bool lr = abs(l - r) >= x;
    bool lb = abs(l - b) >= x;
    bool rb = abs(r - b) >= x;


    if (a == b)cout << "0\n";
    else if (ab) cout << "1\n";
    else if (al and lb) cout << "2\n";
    else if (ar and rb) cout << "2\n";
    else if (al and lr and rb) cout << "3\n";
    else if (ar and lr and lb) cout << "3\n";
    else cout << "-1\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Make It Round

对于一个数字\(x=2^a\times5^b\times c\)，那么末尾0的数量就是\(\min(a,b)\)

所以我们枚举乘数中2 和5的次方数就好了

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n, m, res, cnt, a = 0, b = 0;
    cin >> n >> m;
    for (int t = n; t > 0 and t % 2 == 0; t /= 2, a++);
    for (int t = n; t > 0 and t % 5 == 0; t /= 5, b++);
    res = n, cnt = min(a, b);
    for (int i = 0, x = 1; x <= m; i++, x *= 2)
        for (int j = 0, y = 1; x * y <= m; j++, y *= 5) {
            int t = min(a + i, b + j), p = m / (x * y) * (x * y) * n;

            if (t == cnt and p > res) res = p;
            else if (t > cnt) cnt = t, res = p;
        }
    if (cnt == min(a, b)) res = n * m;
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. The Humanoid

使用药剂的顺序只有三种，三种顺序每种都贪心的取一下，最后取最优解即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

int n, h;
vi a;

int ggb() {
    int i = 0, w = h;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 3;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    return i;
}

int gbg() {
    int i = 0, w = h;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 3;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    return i;
}

int bgg() {
    int i = 0, w = h;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 3;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    w *= 2;
    while (i < n and a[i] < w)
        w += a[i] / 2, i++;
    return i ;
}


void solve() {
    cin >> n >> h;
    a = vi(n);
    for (auto &i: a) cin >> i;
    sort(a.begin(), a.end());
    cout << max({ggb(), bgg(), gbg()}) << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F. All Possible Digits

其实我们只能对末尾进行操作，且只能加一。

末尾数字是\(pn\)，我们只用考虑两种情况

  1. \([0,pn]\)中所有的数字都已经出现过了，我们只需要找到\((pn,p)\)中没出现过的最大值，然后加过去即可。
  2. \([0,pn]\)中所有的数字没有都出现过，首先一直加直到进位，此时\((pn,p)\)中所有的都已经出现过，当前末尾是0，找到\((0,pn)\)中没有出现过的最大值，加过去就好
#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    int pn = a.back();
    auto b = a;
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    if (pn < a.size() and a[pn] == pn) {
        p--;
        while (p == a.back() and p > pn)
            p--, a.pop_back();
        cout << p - pn << "\n";
    } else {
        reverse(b.begin(), b.end());
        int res = p - pn;
        b[0] = p;
        for (int i = 0; i < n - 1; i++) {
            if (b[i] < p) continue;
            b[i + 1] += b[i] / p, b[i] %= p;
        }

        for (int x; b.back() >= p;)
            x = b.back() / p, b.back() %= p, b.push_back(x);

        for (auto i: b)
            a.push_back(i);
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end()) - a.begin());
        auto it = lower_bound(a.begin(), a.end(), pn);
        while (*it == pn and pn >= 0)
            it--, pn--;
        res += max(pn, 0ll);
        cout << res << "\n";
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. Restore the Permutation

对于相邻的两个数，取最大值，所以一定是把当前所有数字放在偶数位上，然后在奇数位置放一个较小的数字。

首先我们判断时候有解。

我们把所有没有放置的数字存起来，然后正序操作，每次放置一个尽可能大的，如果不能全部放完，则无解。

然后找字典序最小的解，反序操作一遍即可。

然后其实发现，我们直接反序操作就行，放不完直接就可以判断出无解。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n;
    cin >> n;
    vi vis(n + 1), res(n + 1);
    for (int i = 2; i <= n; i += 2)
        cin >> res[i], vis[res[i]]++;
    if (*max_element(vis.begin(), vis.end()) > 1) {
        cout << "-1\n";
        return;
    }
    set<int> a;
    for (int i = 1; i <= n; i++)
        if (vis[i] == 0) a.insert(i);
    for (int i = n; i >= 1; i -= 2) {
        auto it = a.lower_bound(res[i]);
        if (it == a.begin()) {
            cout << "-1\n";
            return;
        }
        it = prev(it), res[i - 1] = *it, a.erase(it);
    }
    for( int i = 1 ; i <= n ; i ++ )
        cout << res[i] << " ";
    cout << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

标签：834,int,Codeforces,long,++,while,using,Div,pn
From： https://www.cnblogs.com/PHarr/p/17755157.html

相关文章

  • Codeforces Round 902 Div 1 (CF 1876)
    A.HelmetsinNightLight按花费sort一下，\(b<p\)就让他用\(b\)的花费告诉别人，剩下的人一开始用\(p\)的花费告诉即可。B.EffectsofAntiPimples发现一个数会被所有它的因数贡献，\(O(n\sqrt{n})\)随便算一算，式子略。C.AutosynthesisSolution1想到了建图但没有完......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    EducationalCodeforcesRound156(RatedforDiv.2)A.SumofThree解题思路:如果\(n\leq6或n=9\),无解。若\(n\%3==0，t=\lfloor\frac{3}{n}\rfloor\):若\(t=0\)构造\(1,4,n-5\)否则，构造\(t-3,t,t+3\)若\(n\%3==1:构造1,2，n-3\)若\(n......
  • Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
    目录写在前面ABCDE写在最后写在前面比赛地址：https://codeforces.com/contest/1877。呜呜铃果唱歌太好听了、、、我宣布是第二喜欢的声线，第三喜欢是东北切蒲英，第一喜欢绝赞招募中。这下不得不成为数码推了、、、A答案为\(-\suma_i\)。懒得写代数式子推了，赛时看完题直接......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路：双指针找连续正数段//若段中出现2，则更新两头的0的情况，若为涂色则改为true//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......
  • 练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)
    好久没打了还是就出了三道不过还好没掉分A.SumofThree就是问能不能把一个数拆成三个不同的且都不能被三整除的数我的思路就是拆成1+2+一个大于等于4的数如果拆了后另一个数是%3==0那么我拆成1+4它肯定就不被整除然后判下相同#include<bits/stdc++.h>#defineclose......
  • Codeforces Round 902 (Div. 2) C. Joyboard 规律
    CodeforcesRound902(Div.2)C.Joyboard//思路：在k=1，k=2，k=3时有解//当k=1时为全0//当k=2时，若m>=n,则先是0然后为1~n，最后一位可以为n的倍数也符合，即n+m/n-1//若m<n则为1~m即m//当k=3时，只能在n+1位是第3个不同情况（大于n），且不能为n的倍数，即(m-n)-(m/n-1)//只......
  • CSS 将div撑满body
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>测试</title><style>html,body{height:100%;margin:0;overflow:hidden;}.con......
  • Codeforces Round 726 (Div. 2) B. Bad Boy
    给一个\(n\timesm\)的平面，一个初始位置\((i,j)\)。需要放两个废弃物在平面上，位置为\((x_1,y_1),(x_2,y_2)\)。使得从\((i,j)\)出发，捡起两个废弃物后，回到原位置，所经过的曼哈顿距离最长。询问一组合法的\((x_1,y_1),(x_2,y_2)\)。性质：二维平面上有关的曼哈......
  • 题解 - CF1972E - Divisors and Table
    这题正解是虚树，本解法卡常，仅适合不会虚树的。(例如本人)注意：下文中根节点深度定义为1.第一步:转化问题我们把$g(x,y,z)$拆开，考虑每个质数是哪些点的因子。包含这个质数的点构成一个点集，我们只需求这个点集S的$\sum\limits_{x,y,z\inS}f(x,y,z)$。第二步:对......
  • Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
    Preface难得这么好时间的CF，我直接找来队友组队练题当然比赛的过程没有三人三机，就跟平时训练一样搞了个新号三人一机的写中间因为溜去先看F了导致E题留给徐神solo因此出的偏慢，不过后面一起讨论了一下还是出了最后开F结果好家伙我和祁神双双看错题，对着假题意苦战1h最后无奈投降，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99