AtCoder Beginner Contest 340

A - Arithmetic Progression (abc340 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 a, b, d;
    cin >> a >> b >> d;
    while (a <= b) {
        cout << a << ' ';
        a += d;
    }
    cout << '\n';

    return 0;
}



B - Append (abc340 B)

题目大意

依次进行\(Q\)次操作,分两种。

  • 1 x,将x放到数组\(a\)的末尾。
  • 2 k,输出数组\(a\)的倒数第 \(k\)项。

解题思路

vector模拟即可,操作2可快速寻址访问。

神奇的代码
#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 q;
    cin >> q;
    vector<int> a;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            a.push_back(x);
        } else {
            int k;
            cin >> k;
            cout << a[a.size() - k] << '\n';
        }
    }

    return 0;
}



C - Divide and Divide (abc340 C)

题目大意

黑板一个数\(x\),依次进行以下操作,直到黑板上的数全是\(1\)

  • \(x\)擦去,写上 \(\lfloor x \rfloor\)\(\lceil x \rceil\),耗费 \(x\)精力。

问最后耗费精力的和。

解题思路

朴素做法就一个简单的队列模拟即可。

但这会超时,因为对于同一个数可能会出现多次,而上述做法会对每个数都进行一次操作,这样之后的数的个数是指数增长的。

如何优化呢?那就是对于出现多次的同一个数,我们一次全部做完。

即记录\(cnt[x]\)表示黑板上 \(x\) 的出现次数,然后我们分解它,\(cnt[\lfloor x \rfloor] += cnt[x], cnt[\lceil x \rceil] += cnt[x]\)。为了不重复分解,每次取最大的数进行分解即可。

感觉上这样分解的次数不会超过 \(O(\log)\)或者 \(O(\log^2)\) 次。

神奇的代码
#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);
    LL n;
    cin >> n;
    set<LL> team;
    map<LL, LL> cnt;
    cnt[n] = 1;
    team.insert(n);
    LL ans = 0;
    while (!team.empty()) {
        LL u = *team.rbegin();
        if (u == 1)
            break;
        team.erase(u);
        if (cnt[u] > 0) {
            ans += u * cnt[u];
            team.insert(u / 2);
            cnt[u / 2] += cnt[u];
            team.insert(u - u / 2);
            cnt[u - u / 2] += cnt[u];
            cnt[u] = 0;
        }
    }
    cout << ans << '\n';

    return 0;
}




D - Super Takahashi Bros. (abc340 D)

题目大意

\(n\)个关卡,初始只能打第一关卡。

对于第 \(i\)关卡,可以花 \(a_i\)代价解锁第 \(i+1\)关卡,或花 \(b_i\)代价解锁第 \(x_i\)关卡。

问解锁第 \(n\)关卡的最小代价。

解题思路

虽然说是解锁,但很显然打的下一关肯定是刚刚解锁的关卡。

根据上述解锁关系建一张图,边权就是解锁代价,原问题就是问点\(1\)到点 \(n\)的最短距离,跑一遍 dijkstra即可。

神奇的代码
#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<array<int, 2>>> edge(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b, d;
        cin >> a >> b >> d;
        --d;
        edge[i].push_back({i + 1, a});
        edge[i].push_back({d, b});
    }
    priority_queue<array<LL, 2>, vector<array<LL, 2>>, greater<array<LL, 2>>>
        pq;
    vector<LL> dis(n, 1e18);
    dis[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dis[u])
            continue;
        for (auto [v, w] : edge[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
    cout << dis[n - 1] << endl;

    return 0;
}



E - Mancala 2 (abc340 E)

题目大意

\(n\)个盒子,第 \(i\)个盒子有 \(a_i\)个球。

依次进行以下 \(m\)次操作:

  • \(i\)次操作,将第 \(b_i\)个盒子的所有球均分,多余的球从第\(b_i + 1\)个盒子依次放一个。

问最后每个盒子的球数量。

解题思路

朴素做法为\(O(nm)\),考虑优化每次操作的复杂度。

注意到均分放一个都是区间加法,用线段树维护即可,时间复杂度是\(O(m\log n)\)

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

const int N = 5e5 + 10;

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    LL sum[N << 2];
    LL lazy[N << 2];

    void build(int root, int l, int r, vector<int>& a) {
        if (l == r) {
            sum[root] = a[l - 1];
            lazy[root] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, a);
        build(rson, mid + 1, r, a);
        lazy[root] = 0;
    }

    void pushdown(int root) {
        if (lazy[root]) {
            sum[lson] += lazy[root];
            sum[rson] += lazy[root];
            lazy[lson] += lazy[root];
            lazy[rson] += lazy[root];
            lazy[root] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, LL val) {
        if (L <= l && r <= R) {
            sum[root] += val;
            lazy[root] += val;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update(lson, l, mid, L, R, val);
        if (R > mid)
            update(rson, mid + 1, r, L, R, val);
    }

    LL query(int root, int l, int r, int pos) {
        if (l == r) {
            return sum[root];
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return query(lson, l, mid, pos);
        else
            return query(rson, mid + 1, r, pos);
    }
} sg;

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& i : a)
        cin >> i;
    sg.build(1, 1, n, a);
    for (int i = 0; i < m; ++i) {
        int b;
        cin >> b;
        ++b;
        LL cnt = sg.query(1, 1, n, b);
        sg.update(1, 1, n, b, b, -cnt);
        LL div = cnt / n;
        if (div)
            sg.update(1, 1, n, 1, n, div);
        LL mo = cnt % n;
        if (mo) {
            if (b + mo <= n) {
                sg.update(1, 1, n, b + 1, b + mo, 1);
            } else {
                sg.update(1, 1, n, b + 1, n, 1);
                sg.update(1, 1, n, 1, mo - (n - b), 1);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << sg.query(1, 1, n, i) << " \n"[i == n];
    }

    return 0;
}



F - S = 1 (abc340 F)

题目大意

给定点\((x_0, y_0)\),求一整数点 \((a,b)\),使得 \((0,0), (a, b), (x_0,y_0)\) 形成的三角形的面积为\(1\)

解题思路

考虑将\((0,0) \to (x_0,y_0)\) 作为三角形的底,高的长度\(h\) 需满足\(\frac{1}{2} h \sqrt{x_0^2 + y_0^2} = 1\)

即将直线\((0,0) \to (x_0,y_0)\) 平移一下,距离其为\(h\)的直线即为 \((a,b)\)所处的位置。

直线 \((0,0) -> (x_0,y_0)\) 的直线方程为\(y_0 x - x_0 y = 0\)

根据两平行直线的方程,得\((a,b)\)所处的直线为 \(y_0 x - x_0 y + c = 0\)

根据俩平行直线距离公式,得其距离为\(\frac{|c|}{\sqrt{x_0^2 + y_0^2}}\),其为三角形的高 \(h\),代入上述公式得 \(|c| = 2\)

因此得到了 \((a,b)\)所处的直线方程为 \(y_0 x - x_0 y + 2 = 0\)以及\(y_0 x - x_0 y - 2 = 0\)

现在的问题就是找到一组整数解\((x,y)\),满足上述方程。

注意到上述即为一个不定方程,用扩展欧几里德解得即可。

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

template <typename T> T extgcd(T a, T b, T& x, T& y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    T p = b / a;
    T g = extgcd(b - p * a, a, y, x);
    x -= p * y;
    return g;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL a, b;
    cin >> a >> b;
    auto ok = [](LL a, LL b) {
        LL x, y;
        LL d = extgcd(b, a, x, y);
        if (2 % d != 0) {
            return false;
        }
        cout << x * 2 / d << ' ' << y * 2 / d << '\n';
        return true;
    };
    if (!ok(-a, b) && !ok(a, -b))
        cout << "-1\n";

    return 0;
}



G - Leaf Color (abc340 G)

题目大意

给定一棵树,点有颜色。

问子树的数量,其叶子颜色相同。

解题思路

<++>

神奇的代码



热门相关:庶子风流   奈何老公太宠我   锦桐   资本大唐   盛宠之嫡女医妃