首页 > 其他分享 >Codeforces Round #834 (Div. 3) A~E泛做

Codeforces Round #834 (Div. 3) A~E泛做

时间：2023-01-18 17:56:08浏览次数：44  
标签：const cout 834 int double Codeforces long Div define

A.Yes-Yes?

构造一个\(N=50\)的字符串，判断是不是子串即可。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define PLL pair<LL,LL>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;
const char ch[] = "Yes";
char t[500 + 10], tot;

void solve() {
    int n, ans = 0;
    char s[50 + 10];
    cin >> s;

    if (strstr(t, s)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main() {
    IOS;
    cin >> T;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 3; j++)
            t[tot++] = ch[j];
    }
    //cout << t << endl;
    while (T--) {
        solve();
    }
}

B.Lost Permutation

设最高项数为\(t\)，因为排列是个等差数列，所以构造式子：

\[t^2+t-2(sum+s)=0 \]

其中\(sum\)是给定数列元素之和。

由\(t+1-\frac{2(sum+s)}{t}=0\)可知\(t\)的范围是\([m,\frac{2(sum+s)}{m+1}]\)，枚举。

上述推导都基于等差数列的充分性，对于枚举满足的\(t\)仍需要判断是否仅满足和相等而不是一个合法排列。这里我手动构造了排列，看是否满足条件。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define PLL pair<LL,LL>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;

void solve() {
    LL m, s, a[50 + 5];
    cin >> m >> s;
    map<LL, LL> m2;
    LL sum = 0;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        m2[a[i]]++;
        sum += a[i];
    }
    for (int i = 1; i <= 50; i++)
        if (m2[i] >= 2) {
            cout << "NO" << endl;
        }
    for (LL t = m; t <= 2 * (sum + s) / (m + 1); t++) {
        if (t * t + t - 2 * (sum + s) == 0) {
            LL res = 0;
            for (LL i = 1; i <= t; i++) {
                if (m2[i]) continue;
                res += i;
            }
            if (res + sum == t * (t + 1) / 2) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

signed main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
}

C.Thermostat

分析样例的结论是，答案只能在\({-1,0,1,2,3}\)中出现。

  • 如果\(abs(b-a)>=x\)，一步就能跳过去，\(ans=1\)

  • 如果\(a=b\)，\(ans=0\)

接下来进行分析，\(a\)只能沿着以下路径到达\(b\)，即a->l->b、a->r->b、a->l->r->b、a->r->l->b

  • \(b\)既可以从\(l\)处转移又可以从\(r\)处转移：只需要判断\(a\)能不能转移到\(l\)或\(r\)即可。不能\(ans=-1\)

  • \(b\)既可以从\(l\)处转移：只需要判断\(a\)能不能转移到\(l\)即可。如果无法转移到\(l\)，判断\(a\)能不能转移到\(r\)，再从\(r\)转移到\(l\)。以上都不能时\(ans=-1\)

  • \(b\)既可以从\(r\)处转移：同理

  • 均不能转移：\(ans=-1\)

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define PLL pair<LL,LL>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;
int l, r, x;
int a, b;

void solve() {

    cin >> l >> r >> x;
    cin >> a >> b;
    if (a == b) {
        cout << 0 << endl;
        return;
    }
    if (abs(a - b) >= x) {
        cout << 1 << endl;
        return;
    }
    if (r - b >= x && b - l >= x) {
        if (r - a >= x || a - l >= x) {
            cout << 2 << endl;
            return;
        }
        cout << -1 << endl;
        return;
    }
    if (r - b >= x) {
        if (r - a >= x) {
            cout << 2 << endl;//a->r->x
            return;
        } else if (a - l >= x) {
            cout << 3 << endl;//a->l->r->x
            return;
        }
        cout << -1 << endl;
        return;
    }
    if (b - l >= x) {
        if (a - l >= x) {
            cout << 2 << endl;
            return;
        } else if (r - a >= x) {
            cout << 3 << endl;
            return;
        }
        cout << -1 << endl;
        return;
    }
    cout << -1 << endl;
}

int main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D.Make It Round

可以发现对0产生贡献最低的只有\(2\)、\(5\)和\(10\)

将\(n\)因数分解，看有多少\(2\)和\(5\)，如果\(cnt2>cnt5\)则乘以\((cnt2-cnt5)\)个5，反之相同。最后令\(k*=10\)直到\(k*10>m\)

怎么找到同一个答案下的最大\(k\)？令\(k=m/k*k*n\)，就是比\(m\)小的最大数。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define PLL pair<LL,LL>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;

LL lowbit(LL x) {
    return x & (-x);
}

void solve() {
    LL n, m;
    cin >> n >> m;
    LL t = n;
    int cnt2 = 0, cnt5 = 0;
    while (t % 2 == 0) {
        cnt2++;
        t /= 2;
    }
    t = n;
    while (t % 5 == 0) {
        cnt5++;
        t /= 5;
    }
    LL ans = 1;
    while (cnt2 < cnt5 && ans * 2 * 1LL <= m)
        ans *= 2 * 1LL, cnt2++;
    while (cnt2 > cnt5 && ans * 5 * 1LL <= m)
        ans *= 5 * 1LL, cnt5++;
    while (ans * 10 <= m) ans *= 10 * 1LL;
    cout << m / ans * ans * n << endl;
}

int main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E.The Humanoid

暴力\(dp\)枚举喝药次数

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define PLL pair<LL,LL>
#define int long long
//#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;
int dp[N][5][5];
int n, t, a[N];

void solve() {
    int ans = 0;
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= 2; j++)
            for (int k = 0; k <= 1; k++) dp[i][j][k] = 0;
    dp[0][0][0] = t;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 2; j++)
            for (int k = 0; k <= 1; k++) {
                int num1 = 1;
                for (int j1 = 0; j1 <= j; j1++) {
                    if (j1) num1 *= 2;
                    int num2 = 1;
                    for (int k1 = 0; k1 <= k; k1++) {
                        if (k1) num2 *= 3;
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - j1][k - k1] * num1 * num2);
                    }
                }
                if (dp[i][j][k] > a[i]) {
                    dp[i][j][k] += a[i] / 2;
                    ans = max(ans, i);
                }
            }
    cout << ans << endl;
    return;
}

signed main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
}

标签：const,cout,834,int,double,Codeforces,long,Div,define
From： https://www.cnblogs.com/MrWangnacl/p/17060325.html

相关文章

  • Codeforces Round #740 C
    C.Bottom-TierReversals题链这种翻转方式显然我们是要从后往前固定元素我们先来判断无解情况因为他只允许在奇数位置rev那么我们可以发现每个位置的奇偶性都不会改......
  • Codeforces Global Round 16 E
    E.BudsRe-hanging题链观察样例我们发现我们要尽可能的分解出来bud然后再来组合拼在一起是最优的当然我们可以从深度最深的开始判断是不是bud但是我们再观察发现只......
  • 解决img和div高度不同的问题（转）
    原文：https://blog.csdn.net/qq_34466755/article/details/1114119861、问题img在div中会在底部产生额外的空隙<body><style>div{color:#fff;......
  • Codeforces Round 844
    目录写在前面ABCD写在最后写在前面比赛地址：https://codeforces.com/contest/1782。这两天一个人在家自己糊弄饭吃，炒饭切上一整根腊肠实在是太爽了，比杀软大学的杀软小几......
  • 前端：flex：弹性盒子属性如何使用，实现div在div内水平垂直居中，div显示在一行，div之间间隔相
    前端：flex：弹性盒子属性如何使用在html中多个div是换行显示的，如果我要一行显示多个div盒子怎么办？这里离我可用float是可以实现的，但是今天我们讲讲flex直接上效果图谷咕咕用......
  • Codeforces Round #742 D
    D.ExpressionEvaluationError题链观察样例发现我们应该应该减少进位并且必须要进位的话我们也是选择小的位来进这样我们的做法就完成了肯定是将所有位都拆开先......
  • Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Rou
    C.EqualFrequencies(贪心)题目大意给定一个由小写字母构成的字符串\(s\)，若该字符串中所有字母出现次数相等，则称其为“平衡字符串”。给定一个字符串\(s\)，问将其修改为......
  • Educational Codeforces Round 14
    EducationalCodeforcesRound14AFashioninBerland做法：模拟代码：voidsolve(){intn;cin>>n;intans=0;for(inti=1;i<=n;i++){......
  • CF1748B-Diverse Substrings
    长度为n的字符串，求出子串（只能从头尾依次删字符来得到子串）中，相同字符出现的最高次数小于等于不同字符的个数，这样的子串的个数以1~n个字符作为起点，枚举终点的位置来判断每种......
  • Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round
    比赛链接A题意设计一条线路要贴着6个墙面走，从\((a,b)\)到\((f,g)\)，线路长度最短。题解知识点：模拟。分类取最短即可。时间复杂度\(O(1)\)空间复杂度\(O(1)\)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99