AtCoder Beginner Contest 317

A - Potions (abc317 A)

题目大意

解题思路

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, h, x;
    std::cin >> n >> h >> x;

    std::vector<int> a(n);
    for (int i = 0;i < n;i ++) {
        std::cin >> a[i];
    }

    for (int i = 0;i < n;i ++) {
        if (h + a[i] >= x) {
            std::cout << i + 1 << '\n';
            return ;
        }
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

B - MissingNo. (abc317 B)

题目大意

<++>

解题思路

<++>

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0;i < n;i ++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());
    for (int i = 1;i < n;i ++) {
        if (a[i] != a[i - 1] + 1) {
            std::cout << a[i - 1] + 1 << '\n';
            return ;
        }
    }

    std::cout << a[0] - 1 << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

C - Remembering the Days (abc317 C)

题目大意

<++>

解题思路

很裸的一个图上dfs，一直维护最大值就行。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<PII>> g(n + 1, std::vector<PII>());
    for (int i = 0;i < m;i ++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    i64 ans = 0;
    std::bitset<20> vis;
    std::function<void(int, int)> dfs = [&](int u, i64 res) {
        ans = std::max(ans, res);
        for (auto &[v, w] : g[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            dfs(v, res + w);
            vis[v] = false;
        }
    };

    for (int i = 1;i <= n;i ++) {
        vis.reset();
        vis[i] = true;
        dfs(i, 0);
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

D - President (abc317 D)

题目大意

<++>

解题思路

每个地区都有叛变或不叛变两种情况，所以考虑用背包。

由于Z的和很小，所以设\(dp[i][j]\)为前\(i\)个地区收获了\(j\)张选票，需要叛变的人数。

然后正常\(0/1\)就行。

神奇的代码

#include <algorithm>
#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;

constexpr i64 INF = (1LL << 60);

void solve() {
    int n;
    std::cin >> n;

    i64 sum = 0;
    std::vector<i64> x(n + 1), y(n + 1), z(n + 1);
    for (int i = 1;i <= n;i ++) {
        std::cin >> x[i] >> y[i] >> z[i];
        sum += z[i];
    }

    std::vector<i64> dp(sum + 1, INF);
    dp[0] = 0;

    for (int i = 1;i <= n;i ++) {
        for (int j = sum;j >= z[i];j --) {
            i64 cost = std::max(0LL, (x[i] + y[i] + 1) / 2 - x[i]);
            dp[j] = std::min(dp[j], dp[j - z[i]] + cost);
        }
    }

    i64 ans = *std::min_element(dp.begin() + (sum + 1) / 2, dp.end());
    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

E - Avoid Eye Contact (abc317 E)

题目大意

<++>

解题思路

奶奶的还是一题dfs，只不过非常💩。认真判条件就行。

神奇的代码

#include <algorithm>
#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;

constexpr i64 INF = (1LL << 60);
constexpr std::array<int, 4> dy = {1, -1, 0, 0};
constexpr std::array<int, 4> dx = {0, 0, 1, -1};

struct node {
    int x, y, step;
    node() = default;
    node(int x, int y, int step) : x(x), y(y), step(step) {}
};

void solve() {
    int n, m;
    std::cin >> n >> m;

    int sx = {}, sy = {}, ex = {}, ey = {};
    std::vector<PII> view;
    std::vector<std::vector<char>> a(n + 1, std::vector<char>(m + 1));
    std::vector<std::vector<bool>> vis(n + 1, std::vector<bool>(m + 1));

    for (int i = 1;i <= n;i ++) {
        for (int j = 1;j <= m;j ++) {
            std::cin >> a[i][j];
            if (a[i][j] == 'S') {
                sx = i; sy = j;
            } else if (a[i][j] == 'G') {
                ex = i; ey = j;
            } else if (a[i][j] == '>' || a[i][j] == '<' || a[i][j] == 'v' || a[i][j] == '^') {
                view.emplace_back(i, j);
            } else if(a[i][j] == '#') {
                vis[i][j] = true;
            }
        }
    }

    for (auto &[x, y] : view) {
        vis[x][y] = true;
        if (a[x][y] == '>') {
            for (int i = y + 1;i <= m;i ++) {
                if (a[x][i] == '.' || a[x][i] == 'S' || a[x][i] == 'G') vis[x][i] = true;
                else break;
            }
        } else if (a[x][y] == '<') {
            for (int i = y - 1;i >= 1;i --) {
                if (a[x][i] == '.' || a[x][i] == 'S' || a[x][i] == 'G') vis[x][i] = true;
                else break;
            }
        } else if (a[x][y] == 'v') {
            for (int i = x + 1;i <= n;i ++) {
                if (a[i][y] == '.' || a[i][y] == 'S' || a[x][i] == 'G') vis[i][y] = true;
                else break;
            }
        } else if (a[x][y] == '^') {
            for (int i = x - 1;i >= 1;i --) {
                if (a[i][y] == '.' || a[i][y] == 'S' || a[x][i] == 'G') vis[i][y] = true;
                else break;
            }
        }
    }

    auto bfs = [&](void) {
        std::queue<node> q;
        q.emplace(sx, sy, 0);
        while (!q.empty()) {
            auto [x, y, step] = q.front(); q.pop();
            if (x == ex && y == ey) return step;
            for (int i = 0;i < 4;i ++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (xx == ex && yy == ey) return step + 1;
                if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
                if (vis[xx][yy]) continue;
                vis[xx][yy] = true;
                q.emplace(xx, yy, step + 1);
            }
        }
        return -1;
    };

    int ans = bfs();
    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

F - Nim (abc317 F)

题目大意

<++>

解题思路

计数DP，不知道怎么描述。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 N;
    std::cin >> N;
    N++;
    
    int A1, A2, A3;
    std::cin >> A1 >> A2 >> A3;
    
    Z ans = 0;
    Z dp[2][2][2][10][10][10];
    dp[0][0][0][0][0][0] = 1;
    for (int t = 59; t >= 0; t--) {
        int n = N >> t & 1;
        Z g[2][2][2][10][10][10];
        for (auto l1 : {0, 1}) {
            for (auto l2 : {0, 1}) {
                for (auto l3 : {0, 1}) {
                    for (int m1 = 0; m1 < A1; m1++) {
                        for (int m2 = 0; m2 < A2; m2++) {
                            for (int m3 = 0; m3 < A3; m3++) {
                                for (int x1 = 0; x1 <= (l1 ? 1 : n); x1++) {
                                    for (int x2 = 0; x2 <= (l2 ? 1 : n); x2++) {
                                        for (int x3 = 0; x3 <= (l3 ? 1 : n); x3++) {
                                            if ((x1 ^ x2 ^ x3) == 0) {
                                                g[l1 || x1 < n][l2 || x2 < n][l3 || x3 < n][(m1 * 2 + x1) % A1][(m2 * 2 + x2) % A2][(m3 * 2 + x3) % A3]
                                                    += dp[l1][l2][l3][m1][m2][m3];
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        std::swap(dp, g);
    }
    
    ans = dp[1][1][1][0][0][0];
    N--;
    ans -= N / std::lcm(A1, A2);
    ans -= N / std::lcm(A1, A3);
    ans -= N / std::lcm(A2, A3);
    ans -= 1;
    std::cout << ans << "\n";
    
    return 0;
}

---

G - Rearranging (abc317 G)

题目大意

<++>

解题思路

看题解是什么二分图完美匹配+最大流。先学学网络流再来补

神奇的代码

---

Ex - Walk (abc317 Ex)

题目大意

<++>

解题思路

<++>

神奇的代码

---