Codeforces Round #835 (Div. 4) A-G

时间:2022-11-22 21:10:12

比赛链接

题意

给出三个不同的数,求中位数。

题解

知识点:模拟。

显然。

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    vector<int> v(3 + 1);
    for (int i = 1;i <= 3;i++) cin >> v[i];
    sort(v.begin() + 1, v.end());
    cout << v[2] << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

题意

给出一个小写字母字符串,求最少需要字母表前缀多少个字母才能覆盖所有出现的字母。

题解

知识点:模拟。

找到字符串里最大的字母即可。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int mx = 0;
    for (char ch : s) {
        mx = max(mx, ch - 'a' + 1);
    }
    cout << mx << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题意

给出一组数,求出每个数减去这组数中一个数后能得到的最小值。

题解

知识点:模拟。

显然,每个数减去最大的数即可得到最小值。

但注意最大的数可能只有一个,但自己不能减自己,因此我们还需要求出次大值,让所有等于最大值的数减去次大值即可。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int mx1 = 0, mx2 = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i] > mx1) mx2 = mx1, mx1 = a[i];
        else if (a[i] > mx2) mx2 = a[i];
    }
    for (int i = 1;i <= n;i++) {
        if (a[i] < mx1) cout << a[i] - mx1 << ' ';
        else cout << a[i] - mx2 << ' ';
    }
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题意

给出一组数,问其中是否有且只有一个山谷。

山谷的定义是,数组中的一个连续子串 \(a_{l\cdots r}\) ,满足以下条件:

  • \(0≤l≤r≤n−1\)
  • \(a_l=a_{l+1}=a_{l+2}=\cdots =a_r\)
  • \(l=0\)\(a_{l−1} > al\)
  • \(r=n−1\)\(a_r<a_{r+1}\)

题解

知识点:模拟。

显然第一个山谷一定会出现在第一次严格递增前,如果没有则出现在右端点。

因此,这组数一旦有一次严格递增,之后就不能严格递减(可以相等),因为再次严格递减后必然会再出现一个山谷。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    bool dz = 0;
    for (int i = 2;i <= n;i++) {
        if (a[i] < a[i - 1] && dz) return false;
        dz |= a[i] > a[i - 1];
    }
    cout << "YES" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << "NO" << '\n';
    }
    return 0;
}

E

题意

给定一个 01 串,可以选择一位翻转一次,求最大逆序数。

题解

知识点:枚举,前缀和,贪心。

我们只需要知道每位修改后变化量,取最大值即可。

变化量可以通过维护前缀后缀 1 的个数和 \(l1,r1\) 获得。在第 \(i\) 位, 1->0 ,则变化量为 \(l1_{i-1} - (n-i -r1_{i+1})\)0->1 ,则变化量为 \((n-i -r1_{i+1}) - l1_{i-1}\)

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool a[200007];
int l1[200007], r1[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    l1[0] = r1[n + 1] = 0;
    for (int i = 1;i <= n;i++) l1[i] = l1[i - 1] + a[i];
    for (int i = n;i >= 1;i--) r1[i] = r1[i + 1] + a[i];
    int delta = 0;
    ll sum = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i]) delta = max(delta, l1[i - 1] - (n - i - r1[i + 1])), sum += (n - i - r1[i + 1]);
        else delta = max(delta, (n - i - r1[i + 1]) - l1[i - 1]);
    }
    cout << sum + delta << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

F

题意

给定 \(n\) 个任务,任务 \(i\) 完成后能得到金币 \(a_i\) 个。

每天能选择一个任务完成并得到其金币,任务可以重复完成,但每个任务完成后这个任务会冷却 \(k\) 天,之后才能再次选择。

给定需求金币数 \(c\) ,以及总天数 \(d\) ,问在 \(d\) 天内获得 \(c\) 个金币的前提下, \(k\) 最大是多少。

题解

知识点:二分,贪心。

显然用二分检验求解。

\(k \in [0,d]\)\(k<0\) 则无解,\(k\geq d\) 则每个任务只需要完成一次就能满足,则 \(k\) 可以无穷大。

对于一个需要检验的 \(k\) ,显然我们优先选金币数大的任务。又因为一个任务完成后 \(k\) 天又可以再完成,因此我们只需要选前 \(\min(k+1,n)\) 个任务重复完成即可,能完整完成 \(\lfloor \frac{d}{k+1} \rfloor\) 轮,并再多完成 \(\min(n,d - (k+1) \cdot \lfloor \frac{d}{k+1} \rfloor)\) 个任务。总额大于等于 \(c\) ,这个答案就合法。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n;
ll c;
int d;
ll a[200007];

bool check(int mid) {
    int cyc = d / (mid + 1);
    int rest = d % (mid + 1);
    return a[min(mid + 1, n)] * cyc + a[min(rest, n)] >= c;
}

bool solve() {
    cin >> n >> c >> d;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1, [&](int a, int b) {return a > b;});
    for (int i = 1;i <= n;i++) a[i] += a[i - 1];
    int l = 0, r = d;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    if (r < 0) cout << "Impossible" << '\n';
    else if (r >= d) cout << "Infinity" << '\n';
    else cout << r << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

G

题意

给一个有 \(n\) 个节点的带权树。

从节点 \(a\) 出发到节点 \(b\) ,开始时 \(x = 0\) ,经过一条边 \(i\) 时,则异或边权 \(w_i\) ,即 \(x = x \oplus w_i\) 。当且仅当进入 \(b\) 时恰好 \(x = 0\) 才能进入 \(b\) ,否则不能进入 \(b\) 。有一次传送机会,可以从任意点出发,传送到除了 \(b\) 的任意点。

问是否存在方案从 \(a\) 走到 \(b\)

题解

知识点:dfs,枚举,位运算。

异或有个性质,\(a \oplus a = 0\)

结合我们可以任意传送考虑,我们发现只需要两个点 \(i,j\) (除了 \(b\) )满足 \(a\)\(i\) 的异或和等于 \(j\)\(b\) 的异或和,那我们就可以从 \(i\) 传送到 \(j\) 即可存在 \(a\)\(b\) 的方案。

因此,先从 \(a\) 遍历每个点的异或和。注意,\(a\) 出发的路径不能跨越 \(b\) ,因为此时 \(b\) 是走不通的。当然有可能到 \(b\) 直接就能进去了,我们可以把这个归类为走到 \(b\) 前的一个点原地传送以后,再从这个点出发进入 \(b\)

随后,我们把 \(a\) 能到达的点的异或和放进 set 里,再从 \(b\) 出发遍历每个点的异或和,因为异或具有交换律,倒着走和正着走结果一样。

最后,在 set 中查找 \(b\) 出发每个点得到的异或和是否已经存在即可。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

template<class T>
struct Graph {
    struct edge {
        int v, nxt;
        T w;
    };
    int idx;
    vector<int> h;
    vector<edge> e;

    Graph(int n, int m) :idx(0), h(n + 1), e(m + 1) {}
    void init(int n) {
        idx = 0;
        h.assign(n + 1, 0);
    }

    void add(int u, int v, T w) {
        e[++idx] = edge{ v,h[u],w };
        h[u] = idx;
    }
};

const int N = 100007, M = 100007 << 1;
int n, a, b;
Graph<int> g(N, M);
int dis[N];

void dfs(int u, int fa) {
    for (int i = g.h[u];i;i = g.e[i].nxt) {
        int v = g.e[i].v, w = g.e[i].w;
        if (v == fa || v == b) continue;
        dis[v] = dis[u] ^ w;
        dfs(v, u);
    }
}

bool solve() {
    cin >> n >> a >> b;
    g.init(n);
    for (int i = 1;i <= n - 1;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add(u, v, w);
        g.add(v, u, w);
    }
    for (int i = 1;i <= n;i++) dis[i] = -1;
    dis[a] = 0;
    dfs(a, 0);
    set<int> st;
    for (int i = 1;i <= n;i++) if (dis[i] != -1)st.insert(dis[i]);
    dis[b] = 0;
    dfs(b, 0);
    for (int i = 1;i <= n;i++) {
        if (i != b && st.count(dis[i])) {
            cout << "YES" << '\n';
            return true;
        }
    }
    cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}