Codeforces Round 827 (Div. 4)

2023-04-28 77

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Codeforces Round 827 (Div. 4)A~G题解

A. Sum

两个小数之和是不是大数

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if(a[0] + a[1] == a[2]) puts("YES");
    else puts("NO");
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

B. Increasing

原数组排完序后，是不是严格单调递增的
也就是数组中不能有重复的元素

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a[102], n;
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    int m = unique(a, a + n) - a;
    if(m == n) puts("YES");
    else puts("NO");
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

C. Stripes

查看是否有一整行都是R，或者一整列都是B，就输出

#include <bits/stdc++.h>
using namespace std;
void solve(){
    char ans;
    char g[10][10];
    for(int i = 0; i < 8; i ++ )
        for(int j = 0; j < 8; j ++ )
            cin >> g[i][j];
    
    for(int i = 0; i < 8; i ++ )
    {
        bool f = true;
        for(int j = 0; j < 8; j ++ )
            if(g[i][j] != 'R')
                f = false;
        if(f) ans = 'R';
    }

    for(int i = 0; i < 8; i ++ )
    {
        bool f = true;
        for(int j = 0; j < 8; j ++ )
            if(g[j][i] != 'B')
                f = false;
        if(f) ans = 'B';
    }
    cout << ans << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

D. Coprime

找到两个互质的数，使它们的下标之和最大
因为2e5个数据，故暴力必然超时

此时发现每个元素最大为1000，故可以预处理所有元素之间是否互质

提前维护每个数的最大下标，如果两个元素互质，就用它们的最大下标之和更新答案

#include <bits/stdc++.h>
using namespace std;

void solve(){
    unordered_map<int, int> p;
    int ans = -1;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        p[x] = i;
    }
    for(int i = 1; i <= 1000; i ++ )
        for(int j = i; j <= 1000; j ++ )
            if(__gcd(i, j) == 1 && p.count(i) && p.count(j))
                ans = max(ans, p[i] + p[j]);
    cout << ans << endl;
    
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

E. Scuza

题意：有很多台阶，如果腿长大于台阶高度，就可以上去，最终问最高可以到多高
求最终高度肯定需要前缀和，难度在于怎么找到数组中第一个大于自己数的下标

有2e5个数，暴力循环必定会超时，二分又没有单调性

这时需要进行一个操作b[i] = max(b[i - 1], a[i]);，开一个b数组，存i之前最大的数，然后对b数组进行二分，找到第一个大于自己数的下标

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N], b[N], s[N];
void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = max(b[i - 1], a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while (q--)
    {
        int x;
        cin >> x;
        int t = upper_bound(b + 1, b + n + 1, x) - b - 1;
        cout << s[t] << " ";
    }
    cout << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while (_t--)
    {
        solve();
    }
    return 0;
}

F. Smaller

可以发现性质，

只要第二个字符串包含不是a的字母，我们就把它排到第一个，而把第一个字符串第一个排成a，这样必定YES.

如果第二个字符串没有除a意外的其他字母，而第一个字符串有除a以外的其他字母，则必NO

如果两个都没有除a意外的其他字母，则比较两个字符串a的数量，如果第一个小，则YES，否则NO

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    long long cnt1 = 0, cnt2 = 0;
    bool st1 = 0, st2 = 0;
    while(n -- )
    {
        int d, k;
        string s;
        cin >> d >> k >> s;
        if(d == 1)
        {
            for(auto c : s)
                if(c != 'a')
                    st1 = true;
                else cnt1 += k;
        }
        else
        {
            for(auto c : s)
                if(c != 'a')
                    st2 = true;
                else cnt2 += k;
        }

        if(st2 || (!st1 && cnt1 < cnt2)) puts("YES");
        else puts("NO");
    }
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

G. Orray

题意：给定n个数的数组a，定义一个数组b，$b_i = a_1|a_2 |...or|a_i$，现在为了使b数组的字典序最大，应该使a数组怎样排序
有关或运算，我们按每一数位来看，

首先最大值肯定放第一个，然后出去第一个已经是1的数位，只看其他数位做比较，找出第二个最大值，以此类推，最后全称为1后就不在改变，按放到顺序也无所谓了

那怎么去掉已经变为1的数位呢，我们设置一个mask，初始为(1 << 30) - 1，每个数位全为1，哪个数位变为1，就把mask相应的数位变为0，做法就是mask ^= maxv，在找除去变为1的数位的最大值时，可以使每个数先与mask在比大小，这样可以去掉已经变为1的数位

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
bool st[N];
void solve(){
    int n;
    cin >> n;

    memset(st, 0, sizeof st);

    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    long long mask = (1 << 30) - 1;

    for(int i = 1; i <= n; i ++ )
    {
        int maxv = 0, k = 0;
        for(int j = 1; j <= n; j ++ )
        {
            int t = a[j] & mask;            // 出去已经变为1的数位
            if(t > maxv)
            {
                maxv = t;
                k = j;
            }
        }

        if(maxv == 0)                    // 已经全部变为1了，那剩下的数只要没用过的就随便排
        {
            for(int j = 1; j <= n; j ++ )
                if(!st[j])
                    cout << a[j] << " ";
            cout << "\n";
            return;
        }

        cout << a[k] << " ";
        st[k] = true;
        mask ^= maxv;                // 把已经是1的数位在mask相应位置变为0
    }
    cout << "\n";
}

int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}