0%

Codeforces - Round 827 Div 4

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();
}

想不到就绕死了(