AtCoder Beginner Contest 340 题解

AtCoder Beginner Contest 340 题解

去我的洛谷博客里看这篇文章！

A - Arithmetic Progression

模拟即可。

// 2024/2/11 PikachuQAQ

#include <iostream>

using namespace std;

int a, b, d;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> a >> b >> d;
    for (int i = a; i <= b; i += d) {
        cout << i << ' ';
    }

    return 0;
}

B - Append

用 vector 模拟即可。

// 2024/2/11 PikachuQAQ

#include <iostream>
#include <vector>

using namespace std;

int q, t, x;
vector<int> v;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (cin >> q; q--; ) {
        cin >> t >> x;
        if (t == 1) {
            v.push_back(x);
        } else {
            cout << v[v.size() - x] << '\n';
        }
    }

    return 0;
}

C - Divide and Divide

丢到 OEIS 里得到规律即可。

// 2024/2/11 PikachuQAQ

#include <iostream>

using namespace std;

typedef long long ll;

ll n, s, i, z;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    s = n - 1, i = n - 1, z = 1;
    while (i >= 0) {
        s += i, i -= z, z += z;
    }
    cout << s;

    return 0;
}

D - Super Takahashi Bros.

我们可以把这个问题转化为最短路问题。

对于每个点 \(i\) 建两条到 \(i + 1\) 和到 \(x_i\) 的边，边权分别为 \(a_i\) 和 \(b_i\)，求点 \(1\) 到点 \(n\) 的最短路即可。

// 2024/2/11 PikachuQAQ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

const int kMaxN = 2e5 + 7;
const ll INF = 1e18;

struct E {
    ll v, w;
    friend bool operator > (const E& a, const E& b) {
        return a.w > b.w;
    }
};

int n, m;
ll dis[kMaxN];
bool vis[kMaxN];
vector<E> g[kMaxN];
priority_queue<E, vector<E>, greater<E> > q;

void Dijkstra(int s) {
    fill(dis + 1, dis + n + 1, INF);
    dis[s] = 0;
    q.push({s, 0});
    while (q.size()) {
        int u = q.top().v; q.pop();
        if (vis[u] == 0) {
            vis[u] = 1;
            for (E e : g[u]) {
                ll v = e.v, w = e.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    q.push({v, dis[v]});
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, a, b, c; i < n; i++) {
        cin >> a >> b >> c;
        g[i].push_back({i + 1, a});
        g[i].push_back({c, b});
    }
    Dijkstra(1);
    cout << dis[n];

    return 0;
}

E - Mancala 2

可以把操作转为给每个 \(i\) 加上 \(\lfloor\dfrac{n}{b_i}\rfloor\)，将剩下的 \(n\) 取出来给相应区间加 \(1\)。当要加 \(1\) 的 \(i\) 超过 \(n\)，那么将多出来的区间从 \(1\) 开始补到后面即可。

// 2024/2/11 PikachuQAQ

#include <iostream>

using namespace std;

typedef long long ll;

const int kMaxN = 2e5 + 7;

ll n, m, c[kMaxN];

int lowbit(int x) {
    return x & -x;
}

void Update(ll x, ll y) {
    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += y;
    }
}

ll Query(int x) {
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, a, x = 0; i <= n; i++) {
        cin >> a;
        Update(i, a - x), x = a;
    }
    for (ll i = 1, b, x; i <= m; i++) {
        cin >> b, b++, x = Query(b);
        Update(b, -x), Update(b + 1, x);
        if (x > n - b) {
            x -= n - b;
            Update(b + 1, 1), Update(1, x / n + 1);
            Update(x % n + 1, -1);
        } else {
            Update(b + 1, 1), Update(b + x + 1, -1);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << Query(i) << ' ';
    }

    return 0;
}

F - S = 1

注意到已知其中两个点坐标分别为 \((a,b)\) 和 \((0,0)\)，面积为 \(S\)，则有 \(\dfrac{|ay-bx|}{2}=1\)，据题得 \(ay-bx=±2\)。这种形式的方程，可以用 exgcd 解决。当 \(a\) 和 \(b\) 的最大公因数大于 \(2\)，那么无解。

我们通过 exgcd 得到了一对解，为 \(ay_0-bx_0=±\gcd(a,b)\)，将 \((x_0,y_0)\) 分别除以 \(-\dfrac{g}{2}\) 和 \(\dfrac{g}{2}\) 即可得到正确解 \((x,y)\)。

// 2024/2/11 PikachuQAQ

#include <iostream>

using namespace std;

typedef long long ll;

ll a, b, x, y, g;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    } else {
        ll d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> a >> b, g = exgcd(a, b, y, x);
    if (abs(g) > 2) {
        cout << "-1";
        return 0;
    }
    x *= -2 / g, y *= 2 / g;
    cout << x << ' ' << y;

    return 0;
}

G - Leaf Color

不会虚树。