Blog - Floating Ocean
0%

Codeforces - Round 835 Div 4

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

Practice

A. Medium Number

题意

给定三个数，输出中位数。

思路

排序，输出中间的。

时间复杂度： (确信)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a[3];
        for(int i=0;i<3;i++) cin >> a[i];
        sort(a, a + 3);
        cout << a[1] << '\n';
    }
    return 0;
}

过于打卡

B. Atilla’s Favorite Problem

题意

给定一个字符串，输出最大字母在字母表的位置。

思路

如题，暴力模拟

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int r = 0;
        for(char e : s){
            r = max(r, (int) (e - 'a'));
        }
        cout << r + 1 << '\n';
    }
    return 0;
}

为啥不直接学一段区间内的呢（划掉

C. Advantage

题意

给定一个数组 ，对于所有 ，输出其与除它之外的元素中的最大值的差值。

思路

如题，暴力模拟。

可以找出整个数组中的最大值和次大值，然后遍历到最大值时输出其与次大值的差即可，其余直接减去最大值。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 10;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int maxx = 0, smax = 0;
        for(int i=0;i<n;i++){
            cin >> a[i];
            if(a[i] >= maxx){
                smax = maxx;
                maxx = a[i];
            }else if(a[i] >= smax) smax = a[i];
        }
        for(int i=0;i<n;i++){
            if(a[i] == maxx) cout << a[i] - smax << ' ';
            else cout << a[i] - maxx << ' ';
        }
        cout << '\n';
    }
    return 0;
}

差点没读懂题（

D. Challenging Valleys

题意

给定一个数组 ，输出是否只有一组满足下面条件的 ：

  2. $al = a{l+1} = a_{l+2} = \dots = a_r$

  3. 或 $a{l-1} > a{l}$

  4. 或 $ar < a{r+1}$

思路

我们可以遍历整个数组，找出所有拐点，并记录其与其之后的单调性。

之后，我们可以遍历整个拐点数组，找出所有 “递减，递增” 和 “递减，不变，递增” 段，统计数量。

特别地，考虑到条件 的特殊性，我们还需找出下面的情况：

  1. 整个数组单调

  2. 第一段单调区间值不变，第二段单调区间单调递增

  3. 最后一段单调区间值不变，倒数第二段单调区间单调递减

统计数量，判断数量是否为 即可。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 10;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int pre;
        cin >> pre;
        if(n == 1) {
            cout << "YES\n";
            continue;
        }
        vector<int> trend;
        int inc = -1, cnt = 0;
        for(int i=1;i<n;i++){
            int cur;
            cin >> cur;
            if(pre < cur && inc != 1) {
                inc = 1;
                trend.emplace_back(inc), cnt ++;
            }else if(pre == cur && inc != 2){
                inc = 2;
                trend.emplace_back(inc), cnt ++;
            }else if(pre > cur && inc != 0){
                inc = 0;
                trend.emplace_back(inc), cnt ++;
            }
            pre = cur;
        }
        if(cnt == 1){
            cout << "YES\n";
        } else {
            int ans = 0;
            if ((trend[0] == 2 && trend[1] == 1) || trend[0] == 1) ans++;
            if ((trend[cnt - 1] == 2 && trend[cnt - 2] == 0) || trend[cnt - 1] == 0) ans++;
            for (int i = 0; i < cnt; i++) {
                if (trend[i] == 0) {
                    if(i + 1 < cnt && trend[i + 1] == 1) ans ++;
                    if(i + 2 < cnt && trend[i + 1] == 2 && trend[i + 2] == 1) ans ++;
                }
            }
            cout << (ans == 1 ? "YES\n" : "NO\n");
        }
    }
    return 0;
}

无脑模拟题，纯纯费时间

E. Binary Inversions

题意

给定一个二进制数组，定义操作为将任意元素 改为 ，在操作最多只能执行一次的情况下，输出逆序对个数的最大值。

思路

显然，我们可以贪心地认为，我们只需找出最后一个 和第一个 ，判断不执行操作以及只对这两个元素执行操作后的结果的最大值。

对于找逆序对，我们可以维护一个前缀 个数的数组 和后缀 个数的数组 ，然后遍历所有的 ，统计 个数即可。

对于最后一个 的替换，价值为其前面 的个数，代价为后面 的个数。对第一个 的替换同理。

当然，需要特判整个数组只有一种元素的情况，根据上面的逻辑，输出 即可。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

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

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

int a[N], pre[N], suf[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        pre[0] = 0; //前面的1
        suf[n + 1] = 0; //后面的0
        int one = -1, zero = -1;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            pre[i] = pre[i - 1];
            if(a[i] == 1) {
                pre[i] ++;
                one = i;
            }else if(zero == -1) zero = i;
        }
        int ans = 0;
        for(int i=n;i>=1;i--){
            suf[i] = suf[i + 1];
            if(a[i] == 0) {
                suf[i] ++;
                ans += pre[i];
            }
        }
        if(one == -1 || zero == -1) cout << n - 1 << '\n';
        else {
            int d1 = suf[zero] - 1 - pre[zero], d0 = pre[one] - 1 - suf[one];
            cout << max(ans, ans + max(d1, d0)) << '\n';
        }
    }
    return 0;
}

依然是模拟（

F. Quests

题意

给定 个操作，操作 可以获得 个硬币，每隔 时间可以进行一次重复的操作。给定硬币的需求 和限定的时间 ，输出在限定时间内满足硬币需求的最大 。

若不存在该 ，输出 ；若 无穷大，输出 。

思路

考虑到 越大，能在 天内获得的硬币数量会减小，存在单调性，因而我们不妨考虑二分答案。

我们可以贪心地认为，我们只需每隔 输出降序排序后的前 个数，因为一次性能获得的硬币更多，我们能间隔的时间就越长。

所以，我们只需 一下按上述操作获得的 天内的硬币数，进行二分即可。

当然，若最后的答案落在左边界，输出 ，落在右边界输出 。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

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

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

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n, c, d;
        cin >> n >> c >> d;
        for(int i=0;i<n;i++) cin >> a[i];
        sort(a, a + n, greater<>());
        int l = 0, r = d + 2, mid;
        while(l <= r){
            mid = (l + r + 1) >> 1;
            if(mid == 0) break;
            int tot = 0;
            for(int i=0;i<d;i++) if(i % mid < n) tot += a[i % mid];
            if(tot >= c) l = mid + 1;
            else r = mid - 1;
        }
        if(r == d + 2) cout << "Infinity\n";
        else if(l == 0) cout << "Impossible\n";
        else cout << r - 1 << '\n';
    }
    return 0;
}

二分一下就好简单（（

G. SlavicG’s Favorite Problem

题意

给定一个带权值的无向无环图，给定两个点 ，定义 ，从 开始向子节点走，到达节点 就会将 修改为 。在任意节点，可以选择传送到除 外的任意节点，并继续走。输出是否存在一种路径，使到达 后 。

思路

考虑到异或的性质，我们不妨跑两遍 ，用回溯搜索即可，每次搜索的起始 值均为 。

第一次搜索，我们从 节点开始走，计算所有 的可能值，用 记录下来；

第二次搜索，我们从 节点开始走，判断当前的 和 异或的值是否被记录过，若被记录过，那么我们一定可以用传送的方式使这两条路径联通，且最后答案符合要求。

当然，我们可以用邻接表存边。

时间复杂度：不会分析

对应AC代码

#include<bits/stdc++.h>

using namespace std;

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

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

struct Node{
    int to, w;
};

vector<Node> e[N];
bool vis[N], ans;
map<int, bool> mp;
int n, a, b;

void add(int u, int v, int w){
    e[u].push_back({v, w});
    e[v].push_back({u, w});
}

void dfs1(int r, int v){
    if(vis[r] || r == b) return;
    vis[r] = true;
    mp[v] = true;
    for(auto x : e[r]){
        dfs1(x.to, v ^ x.w);
    }
    vis[r] = false;
}

void dfs2(int r, int v){
    if(vis[r]) return;
    vis[r] = true;
    if(r != b && mp[v ^ 0]){
        ans = true;
        return;
    }
    for(auto a : e[r]){
        dfs2(a.to, v ^ a.w);
    }
    vis[r] = false;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        cin >> n >> a >> b;
        for(int i=1;i<=n;i++) e[i].clear(), vis[i] = false;
        for(int i=1;i<n;i++){
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
        }
        mp.clear();
        dfs1(a, 0);
        ans = false;
        dfs2(b, 0);
        cout << (ans ? "YES\n" : "NO\n");
    }
    return 0;
}

简简单单的思维 + dfs