首页 > 其他分享 >AtCoder Beginner Contest 332

AtCoder Beginner Contest 332

时间：2023-12-16 14:44:21浏览次数：37  
标签：AtCoder Beginner int mo cin long 332 root dp

坐地铁时口糊了6题，回来写时结果爆long long，0没有逆元，卡了好久

A - Online Shopping (abc332 A)

题目大意

线上购物，买了\(n\)种物品，分别给出它们的单价和数量。

若总价少于\(s\)元，则需要支付 \(k\)元邮费，否则包邮。

问总价多少。

解题思路

求个和判断下是否加邮费即可。

神奇的代码 
#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, s, k;
    cin >> n >> s >> k;
    int tot = 0;
    while (n--) {
        int p, q;
        cin >> p >> q;
        tot += p * q;
    }
    if (tot < s)
        tot += k;
    cout << tot << '\n';

    return 0;
}

B - Glass and Mug (abc332 B)

题目大意

一个容量为\(G\)的玻璃杯和一个容量为 \(K\)的马克杯。依次进行以下操作 \(k\)次：

  • 若玻璃杯水满了，则把水倒掉
  • 否则，若马克杯空的，则马克杯装满水
  • 否则，将马克杯的水导入玻璃杯，直到马克杯没水了或玻璃杯满了

问最后玻璃杯和马克杯的水的容量。

解题思路

\(k\)只有 \(100\)，按照上述操作模拟即可。

神奇的代码 
#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 k, g, m;
    cin >> k >> g >> m;
    int l = 0, r = 0;
    while (k--) {
        if (l == g)
            l = 0;
        else if (r == 0)
            r = m;
        else {
            int d = min(r, g - l);
            l += d;
            r -= d;
        }
    }
    cout << l << ' ' << r << '\n';

    return 0;
}

C - T-shirts (abc332 C)

题目大意

有a衬衫和b衬衫。初始有\(m\)件a衬衫。

给定 \(n\)天，每天要么洗衣服，要么吃饭，要么打比赛。

  • 吃饭的话，可以选择穿一件a衬衫或一件b衬衫。
  • 打比赛的话，只能穿一件b衬衫。
  • 洗衣服的话，之前穿过的衬衫在之后都可以再穿。

问最少需要多少件\(b\)衬衫才能满足要求。

解题思路

对于吃饭，我们肯定是能穿a衬衫就穿a衬衫。

因此记录已经穿了的a衬衫和b衬衫件数，每到洗衣服天就重置使用过的 a衬衫和b衬衫。

这期间b衬衫的最大值即为答案。

神奇的代码 
#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;
    string s;
    cin >> n >> m >> s;
    int cnt = 0, ans = 0;
    int plain = m;
    for (auto& i : s) {
        if (i == '0') {
            plain = m;
            cnt = 0;
        } else if (i == '1') {
            if (plain > 0)
                --plain;
            else {
                ++cnt;
                ans = max(ans, cnt);
            }
        } else if (i == '2') {
            ++cnt;
            ans = max(ans, cnt);
        }
    }
    cout << ans << '\n';

    return 0;
}

D - Swapping Puzzle (abc332 D)

题目大意

给定两个矩阵\(a,b\)。

对矩阵\(a\)操作，问最小的操作次数变成 \(b\)。

每次操作，交换相邻两行或者交换相邻两列。

解题思路

注意到矩阵大小只有\(5 \times 5\)，因此最终的情况数只有 \(5! \times 5! = 1e4\)，因此直接\(BFS\)搜索即可。

神奇的代码 
#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 h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w, 0)), b(h, vector<int>(w, 0));
    for (auto& i : a)
        for (auto& j : i)
            cin >> j;
    for (auto& i : b)
        for (auto& j : i)
            cin >> j;
    queue<pair<int, vector<vector<int>>>> team;
    set<vector<vector<int>>> dis;
    team.push({0, a});
    dis.insert(a);
    int ans = -1;
    while (!team.empty()) {
        auto [c, u] = team.front();
        if (u == b) {
            ans = c;
            break;
        }
        team.pop();
        for (int i = 0; i < h - 1; ++i) {
            auto v = u;
            v[i].swap(v[i + 1]);
            if (dis.find(v) == dis.end()) {
                team.push({c + 1, v});
                dis.insert(v);
            }
        }
        for (int i = 0; i < w - 1; ++i) {
            auto v = u;
            for (int j = 0; j < h; ++j)
                swap(v[j][i], v[j][i + 1]);
            if (dis.find(v) == dis.end()) {
                team.push({c + 1, v});
                dis.insert(v);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

E - Lucky bag (abc332 E)

题目大意

给定\(n\)个商品的价值\(w_i\)，分成 \(d\)个袋子里，使得 \(\frac{\sum_{i=1}^{d}(x_i-\bar{x})^2}{d}\)最小，其中 \(x_i\)表示第 \(i\)个袋子的价值和。允许有空袋子。

解题思路

注意到\(\bar{x}\)和\(d\)都是固定的，实际上问题就是确定每个袋子的 \(x_i\)。

注意到\(n\)只有 \(15\)，可以设最朴素的 \(dp[i][j]\)表示将 \(i\)——二进制表示的商品分成 \(j\)个袋子的\(\sum_{i=1}^{d}(x_i-\bar{x})^2\)的最小值。

转移则枚举\(i\)的子集作为一个新袋子，计算该袋子的代价来转移。时间复杂度是 \(O(n3^n)\)，这个时间比较紧 ，预处理每个商品表示\(i\)的价值和，时间复杂度是\(O(n2^n + 3^n)\)

枚举子集的方法和复杂度可参见oi-wiki

这做法貌似就是2023CCPC秦皇岛的签到题J题

神奇的代码 
#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, d;
    cin >> n >> d;
    vector<int> w(n);
    for (auto& i : w)
        cin >> i;
    int tot = accumulate(w.begin(), w.end(), 0);
    double ave = 1. * tot / d;
    int up = (1 << n);
    double inf = numeric_limits<double>::max();
    vector<double> cost(up, 0);
    for (int i = 0; i < up; ++i) {
        for (int l = 0; l < n; ++l) {
            cost[i] += (w[l] * ((i >> l) & 1));
        }
        cost[i] = (cost[i] - ave) * (cost[i] - ave);
    }
    vector<double> dp(up, inf);
    dp[0] = 0;
    for (int j = 1; j <= d; ++j) {
        vector<double> dp2(up, inf);
        for (int i = 0; i < up; ++i) {
            for (int k = i; 1; k = ((k - 1) & i)) {
                if (dp[i ^ k] != inf) {
                    dp2[i] = min(dp2[i], dp[i ^ k] + cost[k]);
                }
                if (k == 0)
                    break;
            }
        }
        dp.swap(dp2);
    }
    cout << fixed << setprecision(10) << dp.back() / d << '\n';

    return 0;
}

注意到\(\bar{x}\)可以通分，使得 \(dp\)的计算不涉及浮点数，但注意此时 \(dp\)值会爆 long long值（可达\(1e20\)）。

神奇的代码 
#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, d;
    cin >> n >> d;
    vector<int> w(n);
    for (auto& i : w)
        cin >> i;
    int tot = accumulate(w.begin(), w.end(), 0);
    int up = (1 << n);
    __int128 inf = numeric_limits<__int128>::max();
    vector<int> sum(up, 0);
    for (int i = 1; i < up; ++i) {
        for (int l = 0; l < n; ++l) {
            sum[i] += (w[l] * ((i >> l) & 1));
        }
    }
    vector<__int128> dp(up, inf);
    dp[0] = 0;
    for (int j = 1; j <= d; ++j) {
        vector<__int128> dp2(up, inf);
        for (int i = 0; i < up; ++i) {
            for (int k = i; 1; k = (k - 1) & i) {
                if (dp[i ^ k] != inf) {
                    __int128 cost = sum[k];
                    __int128 w = (1ll * d * cost - 1ll * tot) *
                                 (1ll * d * cost - 1ll * tot);
                    dp2[i] = min(dp2[i], dp[i ^ k] + w);
                }
                if (k == 0)
                    break;
            }
        }
        dp.swap(dp2);
    }
    cout << fixed << setprecision(10) << dp.back() * 1. / (d * d * d) << '\n';

    return 0;
}

F - Random Update Query (abc332 F)

题目大意

给定一个数组\(a\)，以及 \(m\)次操作。

每次操作，给定 \(l,r,x\)，随机对 \(a[l..r]\)中的一个元素改成 \(x\)。

问每个 \(x\)的期望值。

解题思路

考虑一个操作对其中一个数的影响，如果原来数的期望值是\(a\)，则进行这次操作后，设 \(len = r - l + 1, p = \frac{1}{len}, q = 1 - p\)，则 \(a = a * q + x * p\)。

这是一个区间乘+区间加的操作，用线段树维护即可。

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

const int N = 2e5 + 8;
const int mo = 998244353;

class segment {
#define lson root << 1
#define rson root << 1 | 1

  public:
    LL k[N << 2];
    LL b[N << 2];
    LL lazyk[N << 2];
    LL lazyb[N << 2];

    void build(int root, int l, int r) {
        if (l == r) {
            k[root] = 1;
            b[root] = 0;
            lazyk[root] = 1;
            lazyb[root] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        k[root] = 1;
        b[root] = 0;
        lazyk[root] = 1;
        lazyb[root] = 0;
    }

    void pushdown(int root) {
        if (lazyk[root] != 1 || lazyb[root] != 0) {
            k[lson] = k[lson] * lazyk[root] % mo;
            lazyk[lson] = lazyk[lson] * lazyk[root] % mo;
            b[lson] = (b[lson] * lazyk[root] % mo + lazyb[root]) % mo;
            lazyb[lson] = (lazyb[lson] * lazyk[root] % mo + lazyb[root]) % mo;
            k[rson] = k[rson] * lazyk[root] % mo;
            lazyk[rson] = lazyk[rson] * lazyk[root] % mo;
            b[rson] = (b[rson] * lazyk[root] % mo + lazyb[root]) % mo;
            lazyb[rson] = (lazyb[rson] * lazyk[root] % mo + lazyb[root]) % mo;
            lazyk[root] = 1;
            lazyb[root] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, int vk, int vb) {
        if (L <= l && r <= R) {
            k[root] = k[root] * vk % mo;
            b[root] = (b[root] * vk % mo + vb) % mo;
            lazyk[root] = lazyk[root] * vk % mo;
            lazyb[root] = (lazyb[root] * vk % mo + vb) % mo;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update(lson, l, mid, L, R, vk, vb);
        if (R > mid)
            update(rson, mid + 1, r, L, R, vk, vb);
    }

    array<LL, 2> get(int root, int l, int r, int pos) {
        if (l == r) {
            return {k[root], b[root]};
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return get(lson, l, mid, pos);
        else
            return get(rson, mid + 1, r, pos);
    }

} seg;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<LL> a(n);
    for (auto& i : a)
        cin >> i;
    seg.build(1, 1, n);
    for (int i = 0; i < m; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        int len = (r - l + 1);
        int p = inv(len);
        int q = 1 - p;
        if (q < 0)
            q += mo;
        seg.update(1, 1, n, l, r, q, 1ll * p * x % mo);
    }

    for (int i = 0; i < n; ++i) {
        auto [p, q] = seg.get(1, 1, n, i + 1);
        int ans = a[i] * p % mo + q;
        if (ans >= mo)
            ans -= mo;
        cout << ans << " \n"[i == n - 1];
    }

    return 0;
}

也可以依次考虑每个位置，所有操作对这个位置的影响。从左到右考虑每个位置时，会有一些操作有影响，有一些操作没有影响。

对于当前位置\(i\)，第 \(j\)个操作对其的贡献为， \(x_j \times p_j\) \times q_{tot}\(,\)p,q$就是上述提到的成功概率（修改该数）和失败概率（修改了其他数）。而这个 \(q\)就是该操作之后的所有操作的失败概率的乘积。

换句话说，当第\(j\)个操作有影响时，它对前面的操作的贡献都会乘以 \(q_j\)，当它没影响时，则乘以\(q_j\)的逆元。 这需要一个区间乘的操作，但有个问题， 当\(q_j\)为 \(0\)（即 \(len=1\)）时，其是没有逆元的。 因此可能无法消除影响。

为了避免逆元，我们将这类影响体现在合并上：对于每个操作，维护两个值\(b = xp, k = q\)，即成功的期望值和失败概率。两个操作合并时，成功期望值的和与失败概率则变为 \(b = b_l \times k_r + b_r, k = k_l \times k_r\)。最后答案就是\(a_i \times k_1 + b_1\)。消除该操作影响，则令 \(b=0, k=1\)即可。这就需要单点修改和区间查询。

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

const int N = 2e5 + 8;
const int mo = 998244353;

class segment {
#define lson root << 1
#define rson root << 1 | 1

  public:
    LL k[N << 2];
    LL b[N << 2];

    void build(int root, int l, int r) {
        if (l == r) {
            k[root] = 1;
            b[root] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        k[root] = 1;
        b[root] = 0;
    }

    void modify(int root, int l, int r, int pos, int vk, int vb) {
        if (l == r) {
            k[root] = vk;
            b[root] = vb;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            modify(lson, l, mid, pos, vk, vb);
        else
            modify(rson, mid + 1, r, pos, vk, vb);
        k[root] = k[lson] * k[rson] % mo;
        b[root] = b[lson] * k[rson] % mo + b[rson];
        if (b[root] >= mo)
            b[root] -= mo;
    }

} seg;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<LL> a(n);
    for (auto& i : a)
        cin >> i;
    vector<array<int, 3>> op(m);
    for (auto& i : op) {
        cin >> i[0] >> i[1] >> i[2];
        --i[0];
        --i[1];
    }
    vector<int> add(m), mine(m);
    iota(add.begin(), add.end(), 0);
    iota(mine.begin(), mine.end(), 0);
    ranges::sort(add, [&](int a, int b) { return op[a][0] < op[b][0]; });
    ranges::sort(mine, [&](int a, int b) { return op[a][1] < op[b][1]; });

    seg.build(1, 1, m);
    auto l = add.begin(), r = mine.begin();
    for (int i = 0; i < n; ++i) {
        while (l != add.end() && op[*l][0] <= i) {
            int len = op[*l][1] - op[*l][0] + 1;
            LL p = inv(len);
            LL q = (1 - p);
            if (q < 0)
                q += mo;
            seg.modify(1, 1, m, *l + 1, q, p * op[*l][2] % mo);
            l = next(l);
        }
        while (r != mine.end() && op[*r][1] < i) {
            seg.modify(1, 1, m, *r + 1, 1, 0);
            r = next(r);
        }
        LL ans = a[i] * seg.k[1] % mo + seg.b[1];
        if (ans >= mo)
            ans -= mo;
        cout << ans << " \n"[i == n - 1];
    }

    return 0;
}

G - Not Too Many Balls (abc332 G)

题目大意

给定\(n\)个颜色球的数量\(a_i\)和 \(m\)个盒子的容量\(b_i\)，以及一个附加条件：第 \(j\)个盒子最多能放的第 \(i\)种颜色的球的数量为 \(i \times j\)。

问最多能放多少个球。

解题思路

一类感觉一个决策会牵着到很多条件的决策问题，容易想到使用网络流解决。

  • 源点\(S \to\)颜色\(i\)，容量为 \(a_i\)
  • 颜色\(i \to\)盒子\(j\)，容量为 \(i \times j\)
  • 盒子\(i \to\)汇点\(t\)，容量为 \(b_i\)

跑个最大流即为答案。

但边数有\(5e2 \times 5e5 = 2e8\)，寄。

考虑到最大流等于最小割，我们需要割去最小代价的边集，使得\(S \to T\)无法到达。

注意到上述边分了三类，且第一类的边数量很少，只有 \(500\)。

假定我们选择割去若干条第一类边，即对应的颜色被割去了，而与源点相连的点（颜色）集合为 \(X\)。 考虑盒子点\(j\)，此时仍有\(S \to X \to j \to T\)这样的路径，对与该盒子点来说，就两种决策：

  • 决策1:把 \(j \to T\)这条边割掉，代价是 \(b_j\)
  • 决策2:把 \(X \to j\)这些边割掉，代价是 \(j \times \sum_{i \in X} i\)

很显然我们贪心地选择代价小的割掉，且各个盒子点的决策都是独立的。因此问题就剩下如何决定割去的颜色，这会影响到\(\sum_{i \in X}\)的值。

注意到 \(\sum_{i \in X}\)的大小只有 \(O(n^2)\)，可以枚举这个和\(x\)，当这个和固定后，问题就是我选择编号和为 \(x\) 的最小\(a_i\) 和是多少，这是一个简单的\(0/1\)背包问题 ，设\(dp[i]\)表示割去颜色标号和为 \(i\) 的最小\(a_i\)和，转移则考虑每个颜色是否割去两种情况。

得到 \(dp[i]\)后，如果枚举 标号和再依次判断每个盒子点的决策，复杂度是 \(O(n^2m)\)，这还是过不了。

注意到 判断决策的条件是\(l \times j - b_j < 0\)，即\(l < \frac{b_j}{j}\)。当从小到大枚举割去的颜色标号和\(i\)时， 未被割去的颜色标号和\(l = \sum_{k=1}^{n} k - i\)是递减的。因此会有越来越多的盒子点决策从决策2变成决策1。

因此事先对盒子点根据\(\frac{b_i}{i}\)降序排列，然后类似双指针的方式维护决策2和决策1的边界。最终的时间复杂度是 \(O(n^3 + n + m)\)

神奇的代码 
#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<LL> a(n), b(m);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    int up = 0;
    for (int i = 1; i <= n; ++i)
        up += i;
    constexpr LL inf = 1e18;
    LL totb = accumulate(b.begin(), b.end(), 0ll);
    vector<LL> dp(up + 1, inf);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        LL cost = a[i - 1];
        for (int j = up; j >= i; --j) {
            dp[j] = min(dp[j], dp[j - i] + cost);
        }
    }
    LL ans = inf;
    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    ranges::sort(id,
                 [&](int x, int y) { return b[x] * (y + 1) > b[y] * (x + 1); });
    auto pos = id.begin();
    LL cost2 = 0;
    LL cost3 = totb;
    for (int i = 0; i <= up; ++i) {
        LL cost1 = dp[i];
        LL l = up - i;
        while (pos != id.end() && l * (*pos + 1) <= b[*pos]) {
            cost2 += *pos + 1;
            cost3 -= b[*pos];
            pos = next(pos);
        }
        ans = min(ans, cost1 + l * cost2 + cost3);
    }
    cout << ans << '\n';

    return 0;
}

标签：AtCoder,Beginner,int,mo,cin,long,332,root,dp
From： https://www.cnblogs.com/Lanly/p/17904823.html

相关文章

  • ABC332G Not Too Many Balls 题解
    第\(i\)种球有\(a_i\)个，共\(n\)种。第\(i\)种箱子最多共装\(b_i\)个球。共\(m\)种。第\(i\)种球在第\(j\)种箱子里至多放\(ij\)个。问所有箱子放的球数最多是多少。\(1\leqn\leq500,1\leqm\leq5e5,0\leqa_i,b_i\leq1e12\)。很容易建出网络流模型。......
  • AtCoder Beginner Contest 332 题解
    A-OnlineShopping题目链接AtcoderLuogu简要题意共有\(n\)件商品，第\(i\)件商品的价格为\(p_i\)日元，数量为\(q_i\)件。除了购买商品所需的的钱数，还要支付运费：如果所买商品的总价小于\(s\)日元，那么要支付运费\(k\)日元。问所需要的钱数是多少。简要思路模拟......
  • AtCoder Beginner Contest 332
    AtCoderBeginnerContest332A-OnlineShopping代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+10;typedefpair<ll,ll>pii;voidsolve(){intn,s,k;cin>>n>>s>>......
  • AtCoder Grand Contest 001
    比赛链接A-BBQEasy从小到大排序以后，答案就是所有奇数位置之和。B-MysteriousLight发现去掉前两次反射以后，剩下的是一个在平行四边形内反射的过程，且形式类似于辗转相除。具体地，\[F(n,x)=\begin{cases} -n&x=0\\ 2x\lfloor\frac{n}{x}\rfloor+F(x,n\bmodx)&x>0\e......
  • AtCoder Regular Contest 169
    A-PleaseSign某个\(A_i\)对\(A_1\)的贡献是\(\binom{10^{100}}{\mathrm{dep}_i}\)，所以深度为\(d\)的节点的\(A_i\)之和只要不为\(0\)，其贡献就一定远大于深度\(<d\)的所有点的贡献之和。从大到小找到第一个和非零的深度即可。B-SubsegmentswithSmallSums直......
  • ABC332G
    题面有\(n\)种颜色的球，第\(i\)种颜色的球有\(a_i\)个，有\(m\)个盒子，第\(i\)个盒子能装\(b_i\)个球，第\(i\)个颜色的球在第\(j\)个盒子中最多装\(ij\)个，求最多能装多少个球。\(n\le500,m\le5\times10^5a_i,b_i\le10^{13}\)。题解要注意到这是个网络流模......
  • AtCoder Beginner Contest 332 (D)
    题目链接思路：这就是一个二维的全排列问题代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;#defineLNF0x3f3f3f3f3f3f3f3f#defineINF0x3f3f3f3f#defineIOSios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);#definepllp......
  • ATCoder 332 A-D
    A: OnlineShopping(读懂题即可)packageAtCoder.begin332;importjava.util.Scanner;publicclassA{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt(),s=sc.nextInt(),k=sc.nextInt(......
  • 【题解】AtCoder abc322_f Random Update Query
    传送门：https://atcoder.jp/contests/abc332/tasks/abc332_f容易发现，对于一个位置$i$，$A_i$的最终值是由对$i$的最后一次赋值操作决定的；因此，将所有操作按时间顺序倒过来考虑，则由第$j$次操作决定$A_i$最终值的概率为"在第$(j+1)$~$m$次操作中没有修改过$i$的概率"与"第......
  • AtCoder Regular Contest 169 (ARC169)
    怎么有人ARCA卡了半天的？A.PleaseSign考虑\(i\)位置上的数，下次它被加到\(P_i\)，再下次被加到\(P_{P_i}\)，因为这个序列有性质\(P_i<i\)，这样加若干轮一定会到达\(1\)。令所有的\(i\)向\(P_i\)连边，则这是一棵以\(1\)为根的树。设\(f_i=\sum\limits_{j=1}^n[dep_......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99