AtCoder Beginner Contest 362

o-Sakurajimamai-o / 2024-07-14 / 原文

来补题了, 晚上有事没打比赛(还好没打不然掉大分

A Buy a Pen

按照题目给的意思模拟即可, 一共有三种情况:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int a, b, c; cin >> a >> b >> c;
    string s; cin >> s;
    if(s == "Red") cout << min(b, c);
    else if(s == "Blue") cout << min(a, b); 
    else cout << min(a, c);
    return 0;
}

B Right Triangle

用三个点计算出三条边, 然后根据判断直角三角形的充分必要条件以及勾股定理进行判断即可

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
int main() {
    int xA, yA, xB, yB, xC, yC;
    cin >> xA >> yA >> xB >> yB >> xC >> yC;
    int AB = (xB - xA) * (xB - xA) + (yB - yA) * (yB - yA);
    int BC = (xC - xB) * (xC - xB) + (yC - yB) * (yC - yB);
    int CA = (xC - xA) * (xC - xA) + (yC - yA) * (yC - yA);
    if (AB + BC == CA || AB + CA == BC || BC + CA == AB) {
        cout << "Yes";
    } 
    else {
        cout << "No";
    }
    return 0;
}

C Sum = 0

这题真是折磨我了, 一开始思路错了, 由于有 $L, R$ 的范围, 所以我们可以考虑直接全拿最小和全拿最大的极端情况, 如果此时我们全拿最小的, 总和还是大于 $0$, 那一定无解, 因为不能再取更小的负数了, 全拿最大的同理.

接下来考虑是否还有其它无解的情况. 发现对于不满足上述条件的情况, 我们都可以将正数调大或者将负数调大来修正答案以达到 $0$, 这里只拿全拿最小来举例, 我们通过调整若干个正数或者负数来接近 $0$, 此时有三种可能:

调整完之后仍小于 $0$, 不可能, 因为我们已知全拿最大的大于 $0$
调整完之后大于 $0$, 不可能, 因为我们在调整的过程中, 调整的加数为 $\text min(x, r - l)$, 所以不存在浪费的情况
调整完之后等于 $0$, 一定

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct node{
    int l, r;
};
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<node> p(n + 1);
    vector<int> res(n + 1);
    int suml = 0, sumr = 0;
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        suml += l, sumr += r;
        p[i] = {l, r};
        res[i] = l;
    }
    if(suml > 0 || sumr < 0) return cout << "No" << '\n', 0;
    cout << "Yes" << '\n';
    for(int i = 1; i <= n; i++){
        int l = p[i].l, r = p[i].r;
        if(suml < 0 && r - l > 0){
            int x = min(abs(suml), r - l);
            res[i] += x, suml += x;
        }
    }
    for(int i = 1; i <= n; i++) cout << res[i] << ' ';
    return 0;
}

D Shortest Path 3

最简单的一集, 直接拿最短路模板即可通过

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m;
struct node{
    int u, w;
};
typedef pair<int, int> pii;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    vector<int> val(n + 1);
    vector<node> g[n + 1];
    for(int i = 1; i <= n; i++) cin >> val[i];
    for(int i = 1; i <= m; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c}), g[b].push_back({a, c});
    }  
    auto dijkstra = [&]() -> vector<int>{
        vector<int> dist(n + 1, 1e18);
        vector<bool> vis(n + 1);
        dist[1] = val[1];
        priority_queue<pii, vector<pii>, greater<pii>> que;
        que.push({val[1], 1});
        while(!que.empty()){
            auto now = que.top(); que.pop();
            int x = now.second, y = now.first;
            if(vis[x]) continue;
            vis[x] = true;
            for(auto t : g[x]){
                int u = t.u, w = t.w;
                if(dist[u] > dist[x] + w + val[u]){
                    dist[u] = dist[x] + w + val[u];
                    que.push({dist[u], u});
                }
            }
        }
        return dist;
    };
    vector<int> dist = dijkstra();
    for(int i = 2; i <= n; i++) cout << dist[i] << " ";
    return 0;
}

E Count Arithmetic Subsequences

第一种做法

设 $dp_{i, j, k}$ 中, $i$ 为数列的起点, $j$ 为数列的终点, $k$ 为等差数列的长度, 那么我们此时对三个符合等差数列的数 $(a_i, a_j, a_l)$ 有以下转移方程:

\[dp_{i,j,k} = (dp_{i,j,k} + dp_{l,i,k-1}) \]

当且仅当符合等差性质 : $a_i - a_l = a_j - a_i, l < i < j$
对于长度为 $2$ 和 $1$ 的情况, 我们直接统计即可
这里解释一下为什么只需要判断三个数即可, 若三个数等差, 那么前两个数与后两个数中间蕴含的那些公差小的等差长度, 即 $k$ 也一定相等, 故可以直接转移

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100, mod = 998244353;
int dp[N][N][N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            dp[i][j][2] ++, dp[i][j][2] %= mod;
            for(int k = 3; k <= n; k++){
                for(int l = 1; l < i ; l++){
                    if(a[i] - a[l] == a[j] - a[i]){
                        dp[i][j][k] = (dp[i][j][k] + dp[l][i][k - 1]) % mod;
                    }
                }

        }
    }
    for(int i = 1; i <= n; i++){
        if(i == 1) cout << n << ' ';
        else{
            int res = 0;
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    res = (res + dp[j][k][i]) % mod;
                }
            }
            cout << res << ' ';
        }
    }
    return 0;
}

第二种做法

设 $dp_{i, j, k}$ 中, $i$ 为数列的长度, $j$ 为数列的终点, $k$ 为等差数列的公差, 那么我们此时对三个符合等差数列的数($a_i, a_j, a_l$)有以下转移方程:

\[f_{i,j,k}=\sum_{j=1}^{i-1}f_{k-1,j,a_i-a_j} \]

由于公差较大, 我们选择使用 $map$ 来统计
同上, 这里对于长度为 $2$ 和 $1$ 的情况依然直接统计

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100 + 10, mod = 998244353;
map<int, int> dp[N][N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        dp[1][i][0] = 1;
        for(int j = 1; j < i; j++){
            dp[2][i][a[i] - a[j]] ++;
        }
        for(int k = 3; k <= n; k++){
            for(int j = 1; j < i; j++){
                dp[k][i][a[i] - a[j]] = (dp[k][i][a[i] - a[j]] + dp[k - 1][j][a[i] - a[j]]) % mod;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int res = 0;
        for(int j = 1; j <= n; j++){
            for(auto x : dp[i][j]){
                res = (res + x.second) % mod;
            }
        }
        cout << res << ' ';
    }
    return 0;
}