Atcoder ABC416游记（A~E)

这把手速场吧那我纯吃亏了一个多小时才过了E

但是F题又没写完赛后30min过呜呜

A.Vacation Validation

题目描述

给你一个长度为 $N$ 的字符串 $S$ ，它由 o 和 x 以及整数 $L$ 和 $R$ 组成。

请判断从 $S$ 的 $L$ -th到 $R$ -th的所有字符是否都是o。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, l, r;
    cin >> n >> l >> r;
    string s;
    cin >> s;
    for (int i = l; i <= r; i++) {
        if (s[i - 1] == 'x') {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes" ;
    return 0;
}

B.1D Akari

题目描述

给你一个由 . 和 # 组成的字符串 $S$ 。

在满足以下所有条件的所有字符串 $T$ 中，找出一个 o 数量最多的字符串。

$T$ 的长度等于 $S$ 的长度。
$T$ 由 .、# 或 o 组成。
$T_i=$ 当且仅当 $S_i=$ #.#.
如果 $T_i=T_j=$ o。 $(i \leq j)$ ，那么 $T_{i+1},\ldots,T_{j-1}$ 中至少存在一个#。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    string tp = s;    
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '.') {
            tp[i] = 'o';
        }
    }
    int pos = -1;
    for (int i = 0; i < s.length(); i++) {
        if (tp[i] == 'o') {
            if (pos != -1) {
                bool flag = 0;
                for (int k = pos + 1; k < i; k++) {
                    if (tp[k] == '#') {
                        flag = 1;
                        break;
                    }
                }
                if (!flag) {
                    tp[pos] = '.';
                }
            }
            pos = i;
        }
    }
    cout << tp;
    return 0;
}

C.Concat (X-th)

题目描述

给你 $N$ 字符串 $S_1,\ldots,S_N$ 。

对于长度为 $K$ 的序列 $(A_1,\ldots,A_K)$ ，其中所有元素都在 $1$ 和 $N$ 之间（含），请将字符串 $f(A_1,\ldots,A_K)$ 定义为 $S_{A_1}+S_{A_2}+\dots+S_{A_K}$ 。这里的 + 表示字符串连接。

将 $N^K$ 序列的所有 $f(A_1,\dots,A_K)$ 按词序排序后，找出 $X$ /th最小的字符串。

思路

$N^K$ 的复杂度都能做，直接硬刚即可

代码

#include<bits/stdc++.h>
using namespace std;
int n, k, x;
vector<string> a;
vector<string> ans;
void calc(vector<int> tp)
{
    if (tp.size() == k) {
        string ttp = "";
        for (int i = 0; i < tp.size(); i++) {
            ttp += a[tp[i]];
        }
        ans.push_back(ttp);
        return;
    }
    for (int i = 0; i < n; i++) {
        tp.push_back(i);
        calc(tp);
        tp.pop_back();
    }
}
int main() {
    cin >> n >> k >> x;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> tp;
    calc(tp);
    sort(ans.begin(), ans.end());
    cout << ans[x - 1] << endl;
    return 0;
}

D.Match, Mod, Minimize 2

题目描述

给你长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$ ，由非负整数和一个正整数 $M$ 组成。

当你可以自由地重新排列 $A$ 中的元素时，求 $\displaystyle \sum_{i=1}^N \left((A_i+B_i) \bmod M\right)$ 的最小可能值。

给出了 $T$ 个测试用例，请找出每个测试用例的答案。

思路

写到这题的时候同学们已经开始E题了于是我直接开始狂猜结论

一开始没看完全部样例，以为全部加和取模就完事然后发现WA了

然后一拍脑袋发现是贪心炸了就因为这个罚时我不知道少加了多少分

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt1 += a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        cnt2 += b[i];
    }
    vector<int> tp(n);
    for (int i = 0; i < n; i++) {
        tp[i] = m - b[i];
    }
    sort(a.begin(), a.end());
    sort(tp.begin(), tp.end());
    int cnt = 0;
    int i = 0, j = 0;
    while (i < n && j < n) {
        if (a[i] >= tp[j]) {
            cnt++;
            i++;
            j++;
        } else {
            i++;
        }
    }
    int ans = cnt1 + cnt2 - 1 * cnt * m;
    cout << ans << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E.Development

题目描述

AtCoder 国家有 $N$ 座城市，编号从 $1$ 到 $N$ ， $M$ 条公路和 $K$ 个机场。

$i$ -th公路双向连接 $A_i$ 和 $B_i$ 两个城市，全程需要 $C_i$ 个小时。 $D_1,\ldots,D_K$ 个城市有机场，您可以在 $T$ 个小时内往返于有机场的城市之间。

按顺序处理 $Q$ 个查询。每个查询都是以下三种类型之一：

1 x y t`：在 $t$ 小时内建造一条双向连接 $x$ 和 $y$ 两个城市的道路。
2 x:在城市 $x$ 建造机场。
3:设 $f(x,y)$ 为从城市 $x$ 出发，使用公路和机场到达城市 $y$ 所需的最小小时数，若无法到达，则为 $0$ 。求 $\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)$ .

思路

一眼看到 $1 \leq N \leq 500$ 和时间限制 $3.5$ 秒，直接找到floyed糊了上去发现过了

没错感觉没有什么营养因为我都不知道写点什么了全程在贴板子和敲代码

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        edges[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (edges[a][b] > c) {
            edges[a][b] = c;
            edges[b][a] = c;
        }
    }
    int k1, k2;
    cin >> k1 >> k2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (edges[j][i] + edges[i][k] < edges[j][k]) {
                    edges[j][k] = edges[j][i] + edges[i][k];
                    edges[k][j] = edges[j][k];  
                }
            }
        }
    }
    vector<int> a;
    set<int> st;
    for (int i = 0; i < k1; i++) {
        int x;
        cin >> x;
        if (st.find(x) == st.end()) {
            a.push_back(x);
            st.insert(x);
        }
    }
    int T;
    cin >> T;
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int x, y;
            int t;
            cin >> x >> y >> t;
            if (edges[x][y] > t) {
                edges[x][y] = t;
                edges[y][x] = t;
            }
            for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (edges[i][x] + edges[x][j] < edges[i][j]) {
                            edges[i][j] = edges[i][x] + edges[x][j];
                        }
                    }
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (edges[i][y] + edges[y][j] < edges[i][j]) {
                        edges[i][j] = edges[i][y] + edges[y][j];
                    }
                }
            }
        } else if (ch == 2) {
            int x;
            cin >> x;
            if (!st.count(x)) {
                a.push_back(x);
                st.insert(x);
            }
        } else {
            vector<int> dist(n + 1, INF);
            if (!a.empty()) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 0; j < a.size(); j++) {
                        if (edges[i][a[j]] < dist[i]) {
                            dist[i] = edges[i][a[j]];
                        }
                    }
                }
            }
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        continue;
                    }
                    int dist1 = edges[i][j];
                    int dist2 = INF;
                    if (!a.empty()) {
                        dist2 = dist[i] + k2 + dist[j];
                    }
                    int now = min(dist1, dist2);
                    if (now < INF) {
                        ans += now;
                    }
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

很好一口气加了七十多分算是把那次没打比赛但开了 $\text{rated}$ 的掉分加回来了马上冲进1200分