0%

Codeforces - Round 859 Div 4

Contestant(alt). Rank 5166. Rating -27(+123 -150).

A. Plus or Minus

题意

给定三个数 ,判断 还是 ,前者输出 ,后者输出 ,保证有解。

思路

如题。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a + b == c) cout << '+' << '\n';
    else cout << '-' << '\n';
}

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

这才应该是低程的签到题啊((

B. Grab the Candies

题意

给定一个序列 ,按次序拿出 ,定义 为偶数时 拿走 ,否则 拿走 。输出是否可以将序列重新排列,使得每次取走后 持有的总和严格大于

思路

如题。

很显然,我们先全排满偶数,再排奇数即可。

那么,题目转化为偶数的总和和奇数的总和的比较。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    int sum1 = 0, sum2 = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(cur % 2 == 0) sum1 += cur;
        else sum2 += cur;
    }
    cout << (sum1 > sum2 ? "YES\n" : "NO\n");
}

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

脑子得稍微动一下的题(

C. Find and Replace

题意

给定一个字符串,规定可将一种字母全部替换为 ,在全部替换后,输出是否可以将字符串变为相邻字符不相同的字符串,即 相间。

思路

显然,我们只需对每一个字母去考虑,如果任意两个距离最近的相同的字母的距离为奇数,那么就构造不出来,否则一定可以。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> pre(26, -1);
    string s;
    cin >> s;
    bool f = true;
    for(int i=0;i<n;i++){
        int cur = s[i] - 'a';
        if(pre[cur] != -1 && (i - pre[cur]) % 2 == 1){
            f = false;
            break;
        }
        pre[cur] = i;
    }
    cout << (f ? "YES\n" : "NO\n");
}

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

差点看错题

D. Odd Queries

题意

给定一个序列,对于 独立 询问,给定一段区间 以及一个整数 ,将区间内的数字全都修改为 后,输出序列的总和是否为奇数。

思路

既然询问是独立的,那么我们直接对所有询问单独考虑即可。

也就是说,我们不需要模拟修改,而只需求出值。

那么,很简单,我们求出前缀和,然后用 的复杂度拿出区间前后的元素总和,最后判断加上区间内的值能否变为奇数即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> sum(n + 1, 0);
    for(int i=1;i<=n;i++){
        int cur;
        cin >> cur;
        sum[i] = sum[i - 1] + cur;
    }
    while(q --){
        int l, r, k;
        cin >> l >> r >> k;
        cout << ((sum[l - 1] + (r - l + 1) * k + sum[n] - sum[r]) % 2 == 1 ? "YES\n" : "NO\n");
    }
}

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

这题怎么更水了(

E. Interview

题意

互动游戏。

背景:给定几堆石子,每堆石子都由权值为 的石子堆叠得到,特殊地,有一堆石子中有一个石子的权值为

初始:给定堆数,以及每堆石子的 个数

互动:输出一段区间的左右端点,返回这段区间内所有石子的 权值和

限制:最多 次。

目标:输出特殊的石子在哪个堆里。

思路

首先,我们可以跑一遍前缀和,方便后续查询。

其次,如果我们询问了区间 ,得到的值等于个数,那么我们可以断定特殊的石子在 里,反之就在前者里。

那么,对于 的选择,我们直接用二分的思路做即可。

最后二分的结果就是答案。

次数为 ,不超过

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> sum(n + 1, 0);
    for(int i=1;i<=n;i++) {
        int cur;
        cin >> cur;
        sum[i] = sum[i - 1] + cur;
    }
    int l = 1, r = n, mid;
    while(l < r){
        mid = (l + r) >> 1;
        cout << "? " << mid - l + 1 << ' ';
        for(int i=l;i<=mid;i++) cout << i << ' ';
        cout << '\n';
        cout.flush();
        int g;
        cin >> g;
        if(g == sum[mid] - sum[l - 1]) l = mid + 1;
        else r = mid;
    }
    cout << "! " << l << '\n';
}

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

我怎么会想着去在两边都询问一次呢,我好铸

F. Bouncy Ball

题意

给定一个矩阵,以左上角为原点建立坐标系,给定两个点 ,以及初始运动方向 表示向左下角走,也就是 ,其余同理)。在碰到边界后,会发生反弹,如向左上角走,碰到上边界后会反弹,向左下角继续移动。在碰到边角后,运动方向反转,此处记反弹次数为 次,而不是 次。

输出从 开始运动,到第一次到达 后,经历了多少次反弹。

无法到达输出

思路

数据量并不大,直接模拟即可。

在模拟的时候,我们记录是否已经从某个方向运动到该格子。那么,只要碰到被我们记录过的格子,只要方向一致,那么就出现了循环,直接打断即可。

时间复杂度:最坏

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, m, i, j, si, sj;
    string ori;
    cin >> n >> m >> i >> j >> si >> sj >> ori;
    bool vis[n + 1][m + 1][4] = {};
    int d = ((ori[0] == 'D' ? 0 : 1) << 1) + (ori[1] == 'R' ? 0 : 1); //00 DR, 01: DL, 10: UR, 11: UL
    int cnt = 0;
    while (!vis[i][j][d]) {
        if (i == si && j == sj) {
            cout << cnt << '\n';
            return;
        }
        vis[i][j][d] = true;
        int new_d = d;
        if ((d == 0 || d == 1) && i == n) new_d += 2;
        if ((d == 0 || d == 2) && j == m) new_d ++;
        if ((d == 1 || d == 3) && j == 1) new_d --;
        if ((d == 2 || d == 3) && i == 1) new_d -= 2;
        if (new_d != d) cnt++;
        d = new_d;
        if (d % 2 == 1) j--;
        else j++;
        if ((d >> 1) == 1) i--;
        else i++;
    }
    cout << -1 << '\n';
}

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

居然,居然,居然就是暴力…

G1. Subsequence Addition (Easy Version)

详见G2,区别是G1的数据量更小

G2. Subsequence Addition (Hard Version)

题意

给定一个初始只含一个数字 的序列,规定操作为选择序列中的任意元素,将选定元素之和加入序列中。

现在,给定一个序列,输出其是否为上述操作所得。

思路

我们可以贪心地认为,排序之后,较大的数一定小于等于所有比他小的数的和,而且只要满足这个条件,一定有一种方案得到这个数。

至于为什么,我们可以想想二分,序列中的数一定是某些数的和,那么如此拆分下去,就是一群 的和,而且数量的集合覆盖 ,所以是成立的。

具体的证明需要用到归纳法。

因此,我们排个序,然后判断所有 $aisum{i - 1}$ 即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    int sum = 1;
    bool f = a[0] == 1;
    for(int i=1;i<n;i++){
        if(!f) break;
        if(i < 2 && a[i] != 1 || a[i] > sum) f = false;
        sum += a[i];
    }
    cout << (f ? "YES\n" : "NO\n");
}

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

很有趣一贪