AtCoder Beginner Contest 362

A - Buy a Pen (abc362 A)

题目大意

给定红蓝绿三支笔的价格,并不买指定颜色的笔,问买一支笔最少需要多少钱。

解题思路

三种情况逐一判断,取最小即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int r, g, b;
    string c;
    cin >> r >> g >> b >> c;
    if (c[0] == 'R') {
        r = 999;
    } else if (c[0] == 'G') {
        g = 999;
    } else {
        b = 999;
    }
    cout << min({r, g, b}) << '\n';

    return 0;
}



B - Right Triangle (abc362 B)

题目大意

给定三点坐标,问是否形成直角三角形。

解题思路

枚举直角点,然后向量点积判断是否成90度即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    array<array<int, 2>, 3> p;
    for (auto& x : p)
        cin >> x[0] >> x[1];
    auto vertical = [](array<int, 2>& a, array<int, 2>& b, array<int, 2>& c) {
        return (a[0] - b[0]) * (a[0] - c[0]) + (a[1] - b[1]) * (a[1] - c[1]) ==
               0;
    };
    if (vertical(p[0], p[1], p[2]) || vertical(p[1], p[2], p[0]) ||
        vertical(p[2], p[0], p[1])) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

    return 0;
}



C - Sum = 0 (abc362 C)

题目大意

给定两个\(n\)个数的数组 \(l,r\),构造 \(n\)个数 \(x_i\),满足:

  • \(l_i \leq x_i \leq r_i\)
  • \(\sum_{i=1}^{n} x_i = 0\)

解题思路

先假定\(x_i = l_i\),此时如果\(\sum_{i=1}^{n} x_i > 0\)则无解。

否则遍历\(i = 1, 2, 3, ..., n\),对于每个 \(x_i\),依次增大 \(x_i\),直到 \(\sum_{i=1}^{n} x_i = 0\)或者\(x_i = r_i\)。贪心增加即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }
    vector<int> x = l;
    LL sum = accumulate(l.begin(), l.end(), 0ll);
    for (int i = 0; i < n; i++) {
        if (sum < 0) {
            int c = min(-sum, 0ll + r[i] - l[i]);
            x[i] += c;
            sum += c;
        }
    }
    if (sum != 0) {
        cout << "No" << '\n';
    } else {
        cout << "Yes" << '\n';
        for (int i = 0; i < n; i++) {
            cout << x[i] << " \n"[i == n - 1];
        }
    }

    return 0;
}



D - Shortest Path 3 (abc362 D)

题目大意

给定一张无向图,点有点权\(a_i\),边有边权\(w_i\),问\(1\)号点到其他点的最短距离。

距离为沿途的所有点的点权和边的边权和。

解题思路

就一个朴素的\(dijkstra\)最短路就解决了,转移的时候边\(u \to v\)的代价从\(w_i\)改成 \(w_i + a_v\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<vector<array<int, 2>>> edge(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    vector<LL> dis(n, 1e18);
    dis[0] = a[0];
    priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>>
        team;
    team.push({dis[0], 0});
    while (!team.empty()) {
        auto [d, u] = team.top();
        team.pop();
        if (dis[u] < d)
            continue;
        for (auto& [v, w] : edge[u]) {
            if (dis[v] > dis[u] + w + a[v]) {
                dis[v] = dis[u] + w + a[v];
                team.push({dis[v], v});
            }
        }
    }
    for (int i = 1; i < n; i++)
        cout << dis[i] << " \n"[i == n - 1];

    return 0;
}



E - Count Arithmetic Subsequences (abc362 E)

题目大意

给定\(n\)个数 \(a_i\),对于 \(k = 1, 2, ..., n\),问长度为 \(k\)\(a\)的子序列中,是等差数列的数量。

解题思路

长度为\(1,2\)的等差数列可以直接算出来,因此考虑长度 \(\geq 3\)的情况。

考虑如何统计等差数列,比如考虑枚举公差,统计不同公差下的子序列数量。

虽然公差的范围\(< 10^9\),但考虑到公差是两个数的差,其取值实际只有 \(O(n^2)\)个,而 \(n \leq 80\),可以考虑枚举公差。然后统计该公差下各个长度的子序列数量,累计求和即为答案。

枚举公差 \(d\),剩下就是考虑如何统计其子序列的个数。考虑朴素搜索,即从左到右依次考虑每个数选或不选,选的话要保证构成公差为 \(d\)的等差数列,需要得知上一个选的数是什么,同时还要保留我已经选了多少个数。

据此容易想到就是一个朴素的 \(dp\)\(dp[i][k]\)表示 考虑前\(i\)个数,且选择了第 \(i\)个数,且已经选了 \(k\)个数的等差为 \(d\)的子序列数量。 转移则枚举\(j\),满足 \(a_i - a_k = d\),则 \(dp[i][k] += dp[j][k - 1]\)。即\(dp[i][k] = \sum_{a_i - a_j = d} dp[j][k - 1]\)

枚举公差 \(O(n^2)\)\(dp\)状态 \(O(n^2)\),转移 \(O(n)\),总复杂度是 \(O(n^5)\),是无法通过的,考虑优化转移。

对于一个转移\(dp[i][k] += dp[j][k - 1]\),其中 \(a_i - a_j = d\),遍历所有的公差时\(d_i\),其实 只有一个\(d_i = d\)时,会发生这个转移。 也就是说,固定了公差,我们就可以预处理出状态转移的前继状态,即\(dp[i]\)可以从什么 \(dp[j]\) 转移过来,预处理的复杂度是\(O(n^2)\),随后在求\(dp\)时,转移就无需遍历 \(j \in [1,i)\) ,直接遍历预处理的转移即可。

这样预处理之后,求\(dp\)的复杂度是多少呢?因为每个公差预处理出来的 \(i\)的前继转移 \(j\)的数量不同,但注意到一个转移\(dp[i][k] += dp[j][k - 1]\),其中 \(a_i - a_j = d\),遍历所有的公差时\(d_i\),其实 只有一个\(d_i = d\)时才发生这个转移,纵观所有的这类转移,其数量有\(O(n^2)\)个,但其因为公差 \(d\)被打散在这 \(O(n^2)\)次求 \(dp\)里,所以所有公差,每个公差遍历预处理的转移前继状态,总的复杂度是\(O(n^2)\)个状态+ \(O(n^2)\)次转移,总的复杂度还是 \(O(n^4)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<int> diff;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            diff.push_back(a[j] - a[i]);
        }
    }
    sort(diff.begin(), diff.end());
    diff.erase(unique(diff.begin(), diff.end()), diff.end());
    vector<int> ans(n + 1, 0);
    ans[1] = n;
    if (n > 1)
        ans[2] = n * (n - 1) / 2;
    for (auto d : diff) {
        vector<vector<int>> tr(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (a[i] - a[j] == d)
                    tr[i].push_back(j);

        vector<vector<int>> dp(n, vector<int>(n + 1, 0));
        for (int i = 0; i < n; ++i) {
            dp[i][1] = 1;
            for (int j = 1; j <= i; ++j) {
                for (auto& k : tr[i]) {
                    dp[i][j + 1] += dp[k][j];
                    if (dp[i][j + 1] >= mo) {
                        dp[i][j + 1] -= mo;
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 3; j <= n; ++j) {
                ans[j] += dp[i][j];
                if (ans[j] >= mo) {
                    ans[j] -= mo;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }

    return 0;
}



F - Perfect Matching on a Tree (abc362 F)

题目大意

给定一棵树,俩俩配对,收益是两个点的最短路边数\(dis(u,v)\)

构造配对方案,使得收益最大。

解题思路

每次收益是边数,配对的收益和最大,换个角度考虑贡献,认为考虑每条边,其出现在配对最短路的次数。

一条边将树拆成两个连通块,假设点数分别为\(v_i, n - v_i\),如果配对的两个点分别在这两个连通块里,这个这条边对答案就有\(1\)的贡献 。那一条边对答案的最大贡献即为\(min(v_i, n - v_i)\)

所有边的最大贡献和,即为收益的上界,考虑这个上界能否取到。很显然,对于一些\(v_i\) 很大或很小的,\(min(v_i, n - v_i)\)都比较小,这些边的贡献上界很容易取到,因此关键要考虑 \(v_i = \frac{n}{2}\) 左右的边。

而这些边实际是在树的重心附近,考虑重心,其特点是最大的儿子数不超过 \(\frac{n}{2}\),重心有好几个儿子,我们的配对目标是,配对的两个点来自于不同的儿子子树。这样每个儿子子树里的边都可以取到上界。

剩下的问题就是如何选择儿子子树。事实上,考虑abc359f,其实构造方法是一样的。

将每个儿子子树看成一个点,子树的点树视为该点的度数,每取两个子树的儿子配对,相当于给这两个子树点连边。然后最终每个点的度数满足要求。

因此构造方法为,每次选择一个儿子子树最大的和非最大的,配对。动态维护子树大小。

如果点数是奇数,则抛弃重心,否则也把重心视为一个子树。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> son(n, 0), weight(n, 0);
    int root = 0;
    auto dfs = [&](auto&& dfs, int u, int fa) -> void {
        son[u] = 1;
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            dfs(dfs, v, u);
            son[u] += son[v];
            weight[u] = max(weight[u], son[v]);
        }
        weight[u] = max(weight[u], n - son[u]);
        if (weight[u] <= n / 2)
            root = u;
    };
    dfs(dfs, 0, 0);
    vector<vector<int>> child;
    auto dfs2 = [&](auto&& dfs2, int u, int fa, vector<int>& cc) -> void {
        cc.push_back(u);
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            dfs2(dfs2, v, u, cc);
        }
    };
    for (auto& u : edge[root]) {
        vector<int> cc;
        dfs2(dfs2, u, root, cc);
        child.push_back(cc);
    }
    if (n % 2 == 0)
        child.push_back({root});
    auto cmp = [&](const int a, const int b) -> bool {
        return child[a].size() < child[b].size();
    };
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    for (int i = 0; i < child.size(); ++i) {
        pq.push(i);
    }
    for (int i = 0; i < n / 2; ++i) {
        auto tu = pq.top();
        pq.pop();
        auto tv = pq.top();
        pq.pop();
        int u = child[tu].back();
        int v = child[tv].back();
        child[tu].pop_back();
        child[tv].pop_back();
        if (child[tu].size() > 0)
            pq.push(tu);
        if (child[tv].size() > 0)
            pq.push(tv);
        cout << u + 1 << " " << v + 1 << '\n';
    }

    return 0;
}



G - Count Substring Query (abc362 G)

题目大意

给定一个字符串\(s\),回答 \(q\)个询问。

每个询问给定一个字符串 \(t\),问字符串 \(t\)在字符串 \(s\)里的出现次数。

解题思路

此即为后缀自动机的一个节点的\(|endpos|\)大小,贴个模板即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

class SAM {
    enum { len = 1000005, vary = 26 };

    int trans[len << 1][vary];
    int maxlen[len << 1];
    int link[len << 1];
    int cnt[len << 1];
    int tot;
    int last;

  public:
    SAM() {
        tot = last = 0;
        link[tot] = -1;
        maxlen[tot] = 0;
        ++tot;
    }

    void clear() {
        for (int i = 0; i < tot; ++i) {
            for (int j = 0; j < vary; ++j) {
                trans[i][j] = 0;
            }
            maxlen[i] = link[i] = cnt[i] = 0;
        }
        tot = last = 0;
        link[tot] = -1;
        maxlen[tot] = 0;
        ++tot;
    }

    void insert(int s) {
        int cur = tot++;
        maxlen[cur] = maxlen[last] + 1;
        int p = last;
        for (; p != -1 && !trans[p][s]; p = link[p])
            trans[p][s] = cur;
        if (p == -1)
            link[cur] = 0;
        else {
            int q = trans[p][s];
            if (maxlen[q] == maxlen[p] + 1)
                link[cur] = q;
            else {
                int clone = tot++;
                maxlen[clone] = maxlen[p] + 1;
                link[clone] = link[q];
                for (int i = 0; i < vary; ++i)
                    trans[clone][i] = trans[q][i];
                for (; p != -1 && trans[p][s] == q; p = link[p])
                    trans[p][s] = clone;
                link[q] = link[cur] = clone;
            }
        }
        cnt[cur] = 1;
        last = cur;
    }

    int tong[len];
    int sa[len << 1];

    void build() {
        tong[0] = 0;
        for (int i = 1; i < tot; ++i)
            ++tong[maxlen[i]];
        for (int i = 1; i < len; ++i)
            tong[i] += tong[i - 1];
        for (int i = 1; i < tot; ++i)
            sa[tong[maxlen[i]]--] = i;
        for (int i = tot - 1; i >= 0; --i) {
            int p = sa[i];
            cnt[link[p]] += cnt[p];
        }
    }

    int solve(string& t) {
        int cur = 0;
        for (auto c : t) {
            auto s = c - 'a';
            if (trans[cur][s] == 0)
                return 0;
            cur = trans[cur][s];
        }
        return cnt[cur];
    }
} sam;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (auto c : s)
        sam.insert(c - 'a');
    sam.build();
    int q;
    cin >> q;
    while (q--) {
        string t;
        cin >> t;
        int ans = sam.solve(t);
        cout << ans << '\n';
    }

    return 0;
}



热门相关:宠妻入骨:神秘老公有点坏   夫人每天都在线打脸   调教初唐   自古红楼出才子   极品明君