第二次ak，纪念一下。

比赛链接：https://atcoder.jp/contests/abc183/tasks

A - ReLU

题解

模拟。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int x;

    cin >> x;

    cout << (x >= 0 ? x : 0) << "\n";

    return 0;

}

B - Billiards

题解

过两点向 \(x\) 轴作垂线，由两个直角三角形相似得：

\[\frac{x - sx}{gx - x} = \frac{sy}{gy}
\]

移项展开得:

\[(gy + sy) \times x = sy \times gx + sx \times gy
\]

即：

\[x = \frac{sy \times gx + sx \times gy}{gy + sy}
\]

Tips

要求误差小于 \(10^{-6}\) ，所以至少要输出小数点后 \(6\) 位。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout << fixed << setprecision(6);

    double sx, sy, gx, gy;

    cin >> sx >> sy >> gx >> gy;

    cout << (sy * gx + sx * gy) / (sy + gy) << "\n";

    return 0;

}

C - Travel

题解

枚举所有情况即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, k;

    cin >> n >> k;

    vector<vector<int>> a(n, vector<int>(n));

    for (auto &v : a)

        for (auto &x : v) cin >> x;

    int ans = 0;

    vector<int> p(n);

    iota(p.begin(), p.end(), 0);

    do {

        if (p[0] != 0) continue;

        int sum = a[p[n - 1]][p[0]];

        for (int i = 1; i < n; i++) sum += a[p[i - 1]][p[i]];

        if (sum == k) ++ans;

    } while (next_permutation(p.begin(), p.end()));

    cout << ans << "\n";

    return 0;

}

D - Water Heater

题解

差分。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, w;

    cin >> n >> w;

    vector<long long> cnt(N);

    for (int i = 0; i < n; i++) {

        int s, t, p;

        cin >> s >> t >> p;

        cnt[s] += p;

        cnt[t] -= p;

    }

    bool ok = cnt[0] <= w;

    for (int i = 1; i < N; i++) {

        cnt[i] += cnt[i - 1];

        if (cnt[i] > w) ok = false;

    }

    cout << (ok ? "Yes" : "No") << "\n";

    return 0;

}

E - Queen on Grid

题解

模拟做法：对于每个不为 '#' 的点，将水平、垂直、对角线上可达的点都加上走到当前点的方案数

for (int x = i + 1; x <= h and MP[x][j] == '.'; x++) {

    dp[x][j] += dp[i][j];

}

for (int y = j + 1; y <= w and MP[i][y] == '.'; y++) {

    dp[i][y] += dp[i][j];

}

for (int x = i + 1, y = j + 1; x <= h and y <= w and MP[x][y] == '.'; x++, y++) {

    dp[x][y] += dp[i][j];

}

为了避免超时可以分别将三个方向用差分维护。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2010;

constexpr int MOD = 1e9 + 7;

char MP[N][N];

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int h, w;

    cin >> h >> w;

    for (int i = 1; i <= h; i++) {

        for (int j = 1; j <= w; j++) {

            cin >> MP[i][j];

        }

    }

    vector<vector<long long>> dp(N, vector<long long>(N));

    vector<vector<long long>> row(N, vector<long long>(N));

    vector<vector<long long>> col(N, vector<long long>(N));

    vector<vector<long long>> diag(N, vector<long long>(N));

    dp[1][1] = 1;

    for (int i = 1; i <= h; i++) {

        for (int j = 1; j <= w; j++) {

            if (MP[i][j] == '#') continue;

            (row[i][j] += row[i - 1][j]) %= MOD;

            (col[i][j] += col[i][j - 1]) %= MOD;

            (diag[i][j] += diag[i - 1][j - 1]) %= MOD;

            (dp[i][j] += row[i][j] + col[i][j] + diag[i][j]) %= MOD;

            if (MP[i + 1][j] == '.') row[i + 1][j] += dp[i][j];

            if (MP[i][j + 1] == '.') col[i][j + 1] += dp[i][j];

            if (MP[i + 1][j + 1] == '.') diag[i + 1][j + 1] += dp[i][j];

        }

    }

    cout << dp[h][w] << "\n";

    return 0;

}

F - Confluence

题解

并查集+启发式合并。

Tips

为了避免超时需要始终用大堆合并小堆，最坏时间复杂度为 \(O_{((\frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots )log_n)}\) ，用小堆合并大堆复杂度可能达到 \(O_{(n^2log_n)}\) 。
map<int, int> mp[N] 快于 map<int, map<int, int>> mp 。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 100;

int n, q;

int fa[N], clas[N];

map<int, int> son_num[N];

int Find(int x) {

    return fa[x] == x ? fa[x] : fa[x] = Find(fa[x]);

}

void Union(int x, int y) {

    x = Find(x);

    y = Find(y);

    if (x != y) {

        if (son_num[x].size() < son_num[y].size()) swap(x, y);

        fa[y] = x;

        for (const auto &[_class, num] : son_num[y]) {

            son_num[x][_class] += num;

        }

    }

}

void Init() {

    for (int i = 0; i < N; i++) {

        fa[i] = i;

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    Init();

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {

        cin >> clas[i];

        son_num[i][clas[i]] = 1;

    }

    for (int i = 0; i < q; i++) {

        int op, x, y;

        cin >> op >> x >> y;

        if (op == 1) {

            Union(x, y);

        } else {

            cout << son_num[Find(x)][y] << "\n";

        }

    }

    return 0;

}

巴特西

AtCoder Beginner Contest 183

A - ReLU

题解

代码

B - Billiards

题解

Tips

代码

C - Travel

题解

代码

D - Water Heater

题解

代码

E - Queen on Grid

题解

代码

F - Confluence

题解

Tips

代码

最新文章

热门文章