Blog - Floating Ocean
0%

Codeforces - Round 827 Div 4

发表于 更新于
本文字数： 5.2k 阅读时长 ≈ 9 分钟
阅读次数： Valine：

Practice.

A. Sum

题意

给定三个数，输出是否可以找出一个数，满足其为另外两个数的和。

思路

如题。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a + b == c || a + c == b || b + c == a ? "YES\n" : "NO\n");
}

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

如题

B. Increasing

题意

给定一个序列，满足是否可以重新排列序列，使序列严格单调递增。

思路

没有重复元素即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

void solve(){
    int n;
    cin >> n;
    map<int, bool> mp;
    bool f = true;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(mp[cur]) {
            f = false;
        }
        mp[cur] = true;
    }
    cout << (f ? "YES\n" : "NO\n");
}

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

说那么复杂干嘛（

C. Stripes

题意

给定一个 的矩阵，定义操作为将某一行全部涂成红色，或将某一列全部涂成蓝色，后面的颜色会覆盖前面的颜色。给定任意次操作后的矩阵，输出最后涂上的是什么颜色。

思路

首先，既然存在覆盖，那么被覆盖的某行或某列一定不是在最后操作的。

那么，我们可以找出全为红色的行，或者全为蓝色的列，若能找到就为答案。不然，一定存在覆盖。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

void solve(){
    vector<string> s(8);
    for(int i=0;i<8;i++) cin >> s[i];
    bool f = false;
    for(int i=0;i<8;i++){
        bool now = true;
        for(int j=0;j<8;j++){
            if(s[i][j] == 'B') now = false;
        }
        if(now){
            f = true;
            cout << "R\n";
            break;
        }
    }
    if(!f) for(int j=0;j<8;j++){
        bool now = true;
        for(int i=0;i<8;i++){
            if(s[i][j] == 'R') now = false;
        }
        if(now){
            f = true;
            cout << "B\n";
            break;
        }
    }
}

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

略微有点小思维

D. Coprime

题意

给定一个序列 ，找出 ，满足 互质。输出满足条件的 的最大值。

思路

虽然整体数据量很大，但是需要留意的是 。

因而，我们不妨记录出现过的数对应的下标最大值。然后，我们直接对 中出现过的数字遍历，统计出最大值即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

int gcd(int a, int b){
    return a == 0 ? b : gcd(b % a, a);
}

void solve(){
    int n;
    cin >> n;
    vector<int> a(1001);
    for(int i=1;i<=n;i++){
        int cur;
        cin >> cur;
        a[cur] = max(a[cur], i);
    }
    int ans = -1;
    for(int i=1;i<=1000;i++)
        for(int j=i;j<=1000;j++){
            if(gcd(i, j) == 1 && a[i] > 0 && a[j] > 0) ans = max(ans, a[i] + a[j]);
        }
    cout << ans << '\n';
}

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

来绕一个弯（（

E. Scuza

题意

给定一个上升台阶的所有相邻两层的高度差，对于 个询问给定的腿长 ，输出能登上的台阶距离地面的最大高度。

思路

首先，台阶上升，所以台阶距离地面的高度具有单调性。

那么，二分不就好了么。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), s(n + 2);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i] += a[i - 1];
        s[i] = max(s[i - 1], a[i] - a[i - 1]);
    }
    s[n + 1] = inf;
    while(q--){
        int x;
        cin >> x;
        cout << a[upper_bound(s.begin(), s.end(), x) - s.begin() - 1] << ' ';
    }
    cout << '\n';
}

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

考虑到lower_bound找不到会指向最后一个点，那么我们不妨在最后插一个无穷大

F. Smaller

题意

给定两个初始均为 的字符串 ，定义操作为下面两种任选一：

  1. ，在 后面循环拼接上 个 ；

  2. ，在 后面循环拼接上 个 。

对于每次操作，输出是否可以重新排列两个字符串，使 的字典序小于 。

思路

我们不妨直接考虑怎么样才能让字典序较小：

  1. 既然可以重新排序，而且一开始两个字符串是一样的，且只有一种字母，那么，只要 中出现了不是 的字符，我们直接把他放到第一个，而 的第一个直接放上 ，就一定可以满足 ；

  2. 但是，若没有非 字符，我们就只能统计有多少个 ，个数少的字典序自然小。

那么，我们只要按照上述思路，统计 中是否出现了非 字符，以及 出现的次数即可。

最后，若 出现了非 字符而 中没有出现，或者都没出现但 的 数量更多，那么输出 ，否则为 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void init(){}

void solve() {
    int cnt1 = 1, cnt2 = 1;
    bool h1 = false, h2 = false;
    int q;
    cin >> q;
    while(q --){
        int d, k;
        cin >> d >> k;
        string s;
        cin >> s;
        for(char e : s){
            if(d == 1){
                if(e == 'a') cnt1 += k;
                else h1 = true;
            }
            if(d == 2){
                if(e == 'a') cnt2 += k;
                else h2 = true;
            }
        }
        cout << ((!h1 && !h2 && cnt1 >= cnt2) || (h1 && !h2) ? "NO\n" : "YES\n");
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t;
    cin >> t;
    while (t --) solve();
}

略微绕了一下（

G. Orray

题意

给定一个序列 ，定义 为 前 个数按位或的值。将序列重新排序，满足 的字典序最大。输出任意一种满足条件的方案。

思路

首先，按位或一定是越或越大的，因而我们一定会把最大的数放在第一个。

接着，要让下个数尽可能大，我们当然希望找到一个数，对于当前的数的最高位 ，这个数的该位为 。

我们可能找不到这个数，但是有趣的是，既然数据范围为 ，那么我们一定可以找出 个以内的数，让按位或的值递增。

因而，我们不妨直接遍历 次，找出剩下的让按位或的结果最大的数，输出该数即可。

而，当我们拿不出数字使按位或的结果变大时，就结束了。剩余的数随便输出即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    vector<int> ans;
    vector<bool> vis(n);
    int tot = 0;
    for(int i=31; i>=0;i--){
        int idx = -1, now = 0;
        for(int j=0;j<n;j++){
            if(vis[j]) continue;
            if((tot | a[j]) > now){
                now = tot | a[j];
                idx = j;
            }
        }
        if(idx == -1) break;
        vis[idx] = true;
        ans.emplace_back(a[idx]);
        tot |= a[idx];
    }
    for(auto e : ans) cout << e << ' ';
    for(int i=0;i<n;i++) if(!vis[i]) cout << a[i] << ' ';
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t;
    cin >> t;
    while (t --) solve();
}

想不到就绕死了（