Practice

A. Medium Number

题意

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

思路

排序，输出中间的。

时间复杂度：\(O(1)\) (确信)

对应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

题意

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

思路

如题，暴力模拟

时间复杂度：\(O(n)\)

对应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

题意

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

思路

如题，暴力模拟。

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

时间复杂度：\(O(n)\)

对应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

题意

给定一个数组 \(a\)，输出是否只有一组满足下面条件的 \(l, r\)：

\(0 \le l \le r \le n-1\)
\(a_l = a_{l+1} = a_{l+2} = \dots = a_r\)
\(l = 0\) 或 \(a_{l-1} > a_{l}\)
\(r = n - 1\) 或 \(a_r < a_{r+1}\)

思路

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

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

特别地，考虑到条件 \(3, 4\) 的特殊性，我们还需找出下面的情况：

整个数组单调
第一段单调区间值不变，第二段单调区间单调递增
最后一段单调区间值不变，倒数第二段单调区间单调递减

统计数量，判断数量是否为 \(1\) 即可。

时间复杂度：\(O(n)\)

对应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

题意

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

思路

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

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

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

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

时间复杂度：\(O(n)\)

对应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

题意

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

若不存在该 \(k\)，输出 \(impossible\)；若 \(k\) 无穷大，输出 \(infinity\)。

思路

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

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

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

当然，若最后的答案落在左边界，输出 \(impossible\)，落在右边界输出 \(infinity\)。

时间复杂度：\(O(n \log n + t \log n)\)

对应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

题意

给定一个带权值的无向无环图，给定两个点 \(a, b\)，定义 \(x = 0\)，从 \(a\) 开始向子节点走，到达节点 \(i\) 就会将 \(x\) 修改为 \(x\ XOR\ {w_i}\) 。在任意节点，可以选择传送到除 \(b\) 外的任意节点，并继续走。输出是否存在一种路径，使到达 \(b\) 后 \(x = 0\)。

思路

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

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

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

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

时间复杂度：不会分析

对应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