题目

题目评级

A.Too Many Requests

题目描述

给你正整数 $N$ 和 $M$ 。
打印 $N$ 行。
如果是 $i\leq M$ ，则 $i$ /th行 $(1\leq i\leq N)$ 应包含 “OK”，否则应包含 “Too Many Requests”。

思路

语法题，所以就做完了

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cout << (i <= m ? "OK" : "Too Many Requests") << '\n';
    }
    return 0;
}

B.N - 1

题目描述

给你一个长度为 $N$ , $A=(A_1,A_2,\ldots,A_N)$ 和一个整数 $M$ 的整数序列。

请判断是否有可能从 $A$ 的 $N$ 元素中删除一个，从而使剩余的 $(N-1)$ 元素之和正好是 $M$ 。

思路

语法题，所以就做完了

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = accumulate(a.begin(), a.end(), 0LL);
    for (int i = 0; i < n; i++) {
        if (cnt - a[i] == m) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

C.Odd One Subsequence

题目描述

给你一个长度为 $N$ , $A=(A_1,A_2,\ldots,A_N)$ 的整数序列。
求满足以下条件的整数 $(i,j,k)$ 满足 $1\leq i<j<k\leq N$ 的三元组的个数：

$A_i,A_j,A_k$ 中恰好包含两个不同的值。也就是说， $A_i,A_j,A_k$ 中的两个值相等，剩下的一个值不同。

思路

用map全记一遍出现次数然后排列组合就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for (auto it : mp) {
        if (it.second >= 2) {
            ans += it.second * (it.second - 1) / 2 * (n - it.second);
        }
    }
    cout << ans;
    return 0;
}

D.On AtCoder Conference

题目描述

有一个周长为 $M$ 的池塘，池塘边有一间小屋和 $N$ 人。
对于实数 $x$ $(0\leq x <M)$ , 定义点 $x$ $(0\leq x <M)$ . $(0\leq x <M)$ ，定义点 $x$ 为小屋顺时针方向距离 $x$ 的位置。
第 $i$ 个人位于 $A_i$ 点。**多人可能站在同一位置。

此外，还给出了一个不大于 $N$ 的整数 $C$ 。对于 $i=0,1,\ldots,M-1$ ，定义 $X_i$ 如下：

高桥从点 $(i+0.5)$ 开始顺时针方向移动。
1. 只要高桥遇到的人的总数少于 $C$ ，他就会继续（顺时针）移动；当总数达到或超过 $C$ 时，他就会停止移动。在这里，"在 $y$ 点遇到一个人 "意味着高桥到达了 $y$ 点。
设 $X_i$ 为高桥在停止前遇到的人数。在这里，如果高桥停下的点有多人，那么那里的人都算作他遇到的人，特别是 $X_i$ 可能大于 $C$ 。

求 $X_i$ 与 $i=0,1,\ldots,M-1$ 之和，即 $\displaystyle\sum_{i=0}^{M-1} X_i$ 。

思路

这玩意是环，先把相同位置的人数统计一下，然后把位置数组复制一倍来处理跨边界。

对于每个区间，计算从这个区间内每个点出发走多少人停止，用前缀和优化一下。

对于每个区间，二分找到满足条件（遇到至少 $C$ 个人）的位置，然后用前缀和快速计算这一段对答案的贡献即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<int> pos;
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        if (pos.empty() || pos.back() != a[i]) {
            pos.push_back(a[i]);
        }
        cnt[a[i]]++;
    }
    vector<int> v1, v2;
    vector<int> pre;
    pre.push_back(0);
    for (int i = 0; i < 2 * pos.size(); i++) {
        v1.push_back(pos[i % pos.size()] + (i >= pos.size() ? m : 0));
        v2.push_back(cnt[pos[i % pos.size()]]);
        pre.push_back(pre.back() + v2[i]);
    }
    int ans = 0;
    for (int i = 0; i < pos.size(); i++) {
        int tp = (i == pos.size() - 1) ? pos[0] + m : pos[i + 1];
        tp -= pos[i];
        int l = i + 1, r = i + 1 + pos.size(), res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (pre[mid + 1] - pre[i + 1] >= c) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (res == -1) {
            continue;
        }
        ans += tp * (pre[res + 1] - pre[i + 1]);
    }
    cout << ans;
    return 0;
}

E.Hit and Away

题目描述

给你一个简单相连的无向图 $G$ ，其中有 $N$ 个顶点和 $M$ 条边。
$G$ 的顶点和边分别编号为顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,M$ ，边 $i$ 连接顶点 $U_i$ 和 $V_i$ 。
在时间 $1$ 中，您可以在边连接的顶点之间双向移动。

此外，每个顶点要么是安全的，要么是危险的，这种状态由长度为 $N$ 的字符串 $S$ 表示，字符串由 S 和 D 组成。
具体来说，当 $S$ 的 $i$ -th 字符 $(1\leq i\leq N)$ 是 S 时，顶点 $i$ 是安全的；当 $i$ 是 D 时，顶点 $i$ 是危险的。
可以保证至少有两个安全顶点和至少一个危险顶点。

求每个危险顶点 $v$ 的值：

从某个安全顶点出发，经过 $v$ 并移动到与出发顶点**不同的安全顶点所需的最短时间。

思路

从每个安全点出发跑dijk，然后你维护到每个点的前2个不同源点的最短距离

所以答案是危险点的2个距离之和就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> edges[200005];
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    vector<int> dist1(n + 1, INT_MAX), dist2(n + 1, INT_MAX);
    vector<int> s1(n + 1, -1), s2(n + 1, -1);
    string s;
    cin >> s;
    priority_queue<pair<int, pair<int, int>>> pq;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'S') {
            dist1[i] = 0;
            s1[i] = i;
            pq.push({0, {i, i}});
        }
    }
    while (!pq.empty)() {
        int d = pq.top().first;
        int u = pq.top().second.first;
        int k = pq.top().second.second;
        pq.pop();
        int dist = -d;
        if ((s1[u] == k && dist1[u] != dist) || (s2[u] == k && dist2[u] != dist)) {
            continue;
        }
        for (auto nex : edges[u]) {
            bool flag = 0;
            if (k == s1[nex]) {
                if (dist + 1 < dist1[nex]) {
                    dist1[nex] = dist + 1;
                    flag = 1;
                }
            } else if (k == s2[nex]) {
                if (dist + 1 < dist2[nex]) {
                    dist2[nex] = dist + 1;
                    flag = 1;
                }
            } else {
                if (dist + 1 < dist1[nex]) {
                    dist2[nex] = dist1[nex];
                    s2[nex] = s1[nex];
                    dist1[nex] = dist + 1;
                    s1[nex] = k;
                    flag = 1;
                } else if (dist + 1 < dist2[nex]) {
                    dist2[nex] = dist + 1;
                    s2[nex] = k;
                    flag = 1;
                }
            }
            if (flag) {
                pq.push({-dist - 1, {nex, k}});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'D') {
            cout << dist1[i] + dist2[i] << '\n';
        }
    }
    return 0;
}

复盘

没啥好写的

马上CSP-S了希望能高分 QAQ