AtCoder Beginner Contest 332

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

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;
}



热门相关:现代隐士高手   唐枭   隐身侍卫   在遗忘的时光里重逢   都市最强小村医