Blog - Floating Ocean
0%

Codeforces - Round 859 Div 4

发表于
本文字数： 5.6k 阅读时长 ≈ 10 分钟
阅读次数： Valine：

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)

题意

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

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

思路

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

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

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

因此，我们排个序，然后判断所有 $ai是否大于等于sum{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();
}

很有趣一贪