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

Codeforces Round #820 (Div. 3) A~F泛做

时间：2023-01-19 16:01:12浏览次数：55  
标签：const clock int double Codeforces second Div 820 define

一套题学到不少东西

A.Two Elevators

模拟

#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() {
    int a, b, c;
    cin >> a >> b >> c;
    int timea = 0, timeb = 0;
    timea = a - 1;
    timeb = abs(c - b) + c - 1;
    if (timea < timeb) cout << 1 << endl;
    else if (timea > timeb) cout << 2 << endl;
    else cout << 3 << endl;
    return;
}

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

B.Decode String

把类似\(“150”、“230”\)的数字单独处理，也是模拟题

#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 = 50 + 5, M = 1e8, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;
char ch[30] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
               'u', 'v', 'w', 'x', 'y', 'z'};
int n, b[N];
char a[N];

bool cmp(PII a, PII b) {
    return a.first < b.first;
}

void solve() {
    cin >> n;
    string s;
    map<int, bool> m;
    vector<PII > v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i] - '0';
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {
            if (b[i + 1] == 0 && i + 1 <= n) continue;
            v.push_back({i - 2, b[i - 2] * 10 + b[i - 1]});
            m[i - 1] = m[i - 2] = m[i] = 1;
        }
    }

    for (int i = 1; i <= n; i++)
        if (!m[i]) v.push_back({i, b[i]});
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++)
        cout << ch[v[i].second - 1];
    cout << endl;
}

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

C.Jumping on Tiles

首先易知最短距离就是\(1\rightarrow n\)的距离，要求经过点最大且是最短距离，显然经过的数一定是非严格单调的。

所以经过的数即为路径上所有\(\geq\)初始值的数。

#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;

bool cmp(PII a, PII b) {
    return a.second > b.second;
}

bool cmp2(PII a, PII b) {
    return a.second < b.second;
}

int b[N];

void solve() {
    string s;
    vector<PII > v;
    cin >> s;
    int n = s.length();
    for (int i = 0; i < n; i++)
        b[i] = s[i] - '0' + 1;
    int sum = 0, ans = abs(b[0] - b[n - 1]);
    if (b[0] > b[n - 1]) {
        for (int i = 1; i < n - 1; i++) {
            if (b[i] <= b[0] && b[i] >= b[n - 1]) v.push_back({i + 1, b[i]}), sum++;
        }
        cout << ans << " " << sum + 2 << endl;
        sort(v.begin(), v.end(), cmp);
        cout << 1 << " ";
        for (auto i: v) cout << i.first << " ";
        cout << n << endl;
    } else {
        for (int i = 1; i < n - 1; i++) {
            if (b[i] >= b[0] && b[i] <= b[n - 1]) v.push_back({i + 1, b[i]}), sum++;
        }
        cout << ans << " " << sum + 2 << endl;
        sort(v.begin(), v.end(), cmp2);
        cout << 1 << " ";
        for (auto i: v) cout << i.first << " ";
        cout << n << endl;
    }
    return;

}

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

D.Friends and the Restaurant

令\(k_i=y_i-x_i\)，如果选取若干数满足\(\sum y \geq \sum x\)，则\(\sum k_i \geq 0\)

注意到要求分组最大且每组不少于两人，故最优情况一定是两两分组。

排序\(k_i\),如果\(max\{k_i\}+min\{k_i\}＜ 0\)，那么\(min\{k_i\}\)一定是无法去餐厅的，我们考虑舍弃。

故基本思路：\(two\ points\)法，每次选择\(k_l+k_r\)判断大小，如果\(k_l+k_r<0\)则\(l++\)。

#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 x[N], y[N];

bool cmp(PII a, PII b) {
    return a.second > b.second;
}

void solve() {
    int n;
    cin >> n;
    vector<int> v;
    int sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> y[i];
    for (int i = 1; i <= n; i++) {
        v.push_back(y[i] - x[i]);
    }
    sort(v.begin(), v.end());
    int l = 1, r = n;
    while (l < r) {
        if (v[l - 1] + v[r - 1] >= 0) {
            sum++;
            l++, r--;
        } else l++;
    }
    cout << sum << endl;
    return;

}

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

E. Guess the Cycle Size

第一次做交互题，还蛮神奇的。

我们发现，如果对于询问\(\{1,i\}\)和询问\(\{i,1\}\)，两者的回答不一致，那我们认为我们已经找到了环的最大边数。因为两者之和等于\(m\)。

如果对于当前预设\(m\)，回答超出了\(m\)，那么也认定找到了最大边数。

询问的上限是\(50\)，每次询问给出相同回答的概率是\(\frac{1}{2}\)，50次询问后仍无不同答案的概率是\(\frac{1}{2^{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;

void solve() {
    LL x, x2;
    for (int i = 1; i <= 49; i++) {
        printf("? 1 %d\n", i + 1);
        fflush(stdout);
        scanf("%lld", &x);
        if (x == -1) {
            printf("! %d\n", i);
            fflush(stdout);
            return;
        }
        printf("? %d 1\n", i + 1);
        fflush(stdout);
        scanf("%lld", &x2);
        if (x != x2) {
            printf("! %lld\n", x + x2);
            fflush(stdout);
            return;
        }
    }

}

signed main() {
    //IOS;
    //freopen("input.txt",'r',stdin);
    //freopen("output.txt",'w',stdout);
    solve();
}

F.Kirei and the Linear Function

字符串哈希好题。

阅读理解可知\(v(l,r)\)就是构造一个\(p=10\)的\(hash\)区间,\(v(l,r)\in [0,8]\)。

注意到\(t=v(l,r)\)是定值，故\((t*v(L1,R1)+v(L2,R2))\%9=k\)可以通过枚举\(v \in [0,8]\)来判断。

#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 p[N], h[N];

int calc(int l, int r) {
    return (h[r] - h[l - 1] * p[r - l + 1] % 9 + 9) % 9;
}

void solve() {
    int n, w, m;
    vector<int> v[10 + 5];
    string s;
    cin >> s;
    n = s.length();
    s = "!" + s;
    cin >> w >> m;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * 10 % 9;
        h[i] = (h[i - 1] * 10 + s[i] - '0') % 9;
    }
    for (int l = 1, r = l + w - 1; r <= n; l++, r++) {
        v[calc(l, r)].push_back(l);
    }
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        PII res = {inf, inf};
        for (int i = 0; i <= 9; i++) {
            if (v[i].empty()) continue;
            for (int j = 0; j <= 9; j++) {
                if (v[j].empty()) continue;
                int t = calc(l, r);
                if ((i * t + j) % 9 == k) {
                    if (i == j && v[i].size() >= 2) res = min(res, {v[i][0], v[i][1]});
                    if (i != j) res = min(res, {v[i][0], v[j][0]});
                }
            }
        }
        if (res.first == inf) {
            cout << -1 << " " << -1 << endl;
            continue;
        }
        cout << res.first << " " << res.second << endl;
    }
}

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

标签：const,clock,int,double,Codeforces,second,Div,820,define
From： https://www.cnblogs.com/MrWangnacl/p/17061668.html

相关文章

  • CodeForces 构造题专项解题报告（二）
    CodeForces构造题专项解题报告（二）\(\newcommand\m\mathbf\)\(\newcommand\oper\operatorname\)\(\newcommand\txt\texttt\)\(\text{ByDaiRuiChen007}\)来源：CodeF......
  • [CSS]背景图片很大，根据屏幕缩小适配后，div之间有空隙的问题
    RT。美术给的素材宽度是1080px的。在不缩放的情况下，1080px宽度的屏幕显示div之间正常，没有空隙，但使用transform属性之后，div缩小，div之间有空隙（白线） 百度有人说给这些div......
  • luogu P8207 题解
    在暴力建边的情况下可以kruskal求生成树。但是这样是\(O(n^2)\)的。因为\(lcm(x,y)=x\timesy/\gcd(x,y)\)。所以\(\gcd(x,y)\)越大我们的答案越优。但是......
  • Codeforces Round #807 (Div. 2)
    题目链接A核心思路排序加贪心就好了。//Problem:A.MarkthePhotographer//Contest:Codeforces-CodeforcesRound#807(Div.2)//URL:https://codeforces.......
  • Div高度控制问题
    做网页时尽量是不用设置固定高度的，这样拓展起来更灵活，如果非要设固定高度，就有一些需要注意的地方。IE6和IE7对CSS的解释存在很多差别，今天谈其中一点：height。例子：<div......
  • Codeforces Round #834 (Div. 3) A~E泛做
    A.Yes-Yes?构造一个\(N=50\)的字符串，判断是不是子串即可。#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definecerr(x)std::cerr<<(#x)<<......
  • 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。这两天一个人在家自己糊弄饭吃，炒饭切上一整根腊肠实在是太爽了，比杀软大学的杀软小几......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99