AtCoder Beginner Contest 461

by JiuQiin AtCoder, 题解on Posted on
首页 » 题解 » AtCoder » AtCoder Beginner Contest 461
Contents hide
1 A – Armor
1.1 题意
1.2 思路
1.3 代码
2 B – The Honest Woodcutters
2.1 题意
2.2 思路
2.3 代码
3 C – Variety
3.1 题意
3.2 思路
3.3 代码
4 D – Count Subgrid Sum = K
4.1 题意
4.2 思路
4.3 代码
5 E – E-liter
5.1 题意
5.2 思路
5.3 代码
6 F – Total Product is N
6.1 题意
6.2 思路
6.3 代码
6.4 错误代码
6.5 别人代码（DFS）

A – Armor

题意

给出 AA DD，若 A≤DA \leq D，则输出 YesYes，否则为 NoNo

思路

按题意模拟

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int x, y;
    cin >> x >> y;
    if (x <= y) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B – The Honest Woodcutters

题意

给出两个数组 a，ba， b，第 ii 个樵夫说它拥有第 aia_i 把斧头，仙女知道第 ii 把斧头是樵夫 bib_i 的，问是否每个樵夫说的都是实话

思路

与（i,ai）（i, a_i）相对应的是 (bi,i)(b_i, i)，i=bi,ai=ii = b_i, a_i = i

樵夫123…n
斧头a1a_1a2a_2a3a_3…ana_n
斧头123…n
樵夫b1b_1b2b_2b3b_3…bnb_n

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n +1), b(n +1);

    set<pair<int, int>> st;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st.insert({a[i], i});
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        if (!st.count({i, b[i]})) {
            cout << "No" << endl;
            return ;
        }
    }
    cout << "Yes" << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C – Variety

题意

有 NN 颗宝石。第 ii 颗宝石的颜色（用整数表示）是 CiC _ i ，它的价值是 ViV _ i 。

从这些 NN 颗宝石中选择 KK 颗宝石。这里，所选的宝石必须至少有 MM 种不同的颜色。

求所选宝石的最大可能总值。

思路

将宝石根据价值从大到小排序。两次遍历，第一次，只要碰见新的颜色，则加入到答案中。第二次遍历，只要碰见之前没选的就加入到答案中。整个过程保证选取个数小于等于 KK

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

struct Node {
    LL c, v;
    bool operator<(const Node &t) const {
        if (v != t.v) return v > t.v;
        return c < t.c;
    }
};

void solve() {
    LL n, k, m;
    cin >> n >> k >> m;

    vector<Node> node;

    vector<LL> vis(n +1, 0);
    for (LL i = 1; i <= n; ++i) {
        LL c, v;
        cin >> c >> v;
        node.push_back({c, v});
    }

    sort(node.begin(), node.end());

    LL cnt =0, sm = 0;
    set<LL> st;
    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < m && !st.count(c)) {
            st.insert(c);
            vis[i] = 1;
            sm += v;
            ++cnt;
        }
    }

    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < k && !vis[i]) {
            sm += v;
            ++cnt;
        }
    }

    cout << sm << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D – Count Subgrid Sum = K

题意

有一个 H×WH×W 网格，每个单元格都包含一个整数 0 或 1 。给一个整数 kk

求，满足矩形中 11 的个数刚好等于 kk 的矩形个数

思路

二维前缀和，双指针{\color{yellow}二维前缀和，双指针}

我最开始，朴素的想法自然是暴力，因为他的数量级真的很小，才 500，但是如果纯暴力的话，枚举左上角的点，然后枚举宽和高，时间复杂度是 O(n4)O(n^4)，过不了，但是可以优化到 O（n3）O（n^3），左上角的点是必须枚举的，然后枚举宽，发现一个单调性，由于 kk 是定值，宽越大，高就越小，所以，用双指针或者二分都可以，但我推荐用双指针，少一个 loglog 的复杂度

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

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

    vector<vector<int>> s(n +2, vector<int>(m +2));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            s[i][j] = c - '0';
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            s[i][j] += s[i - 1][j];
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i][j - 1];
        }
    }


    auto area = [&](int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    };

    int ans = 0;
    for (int x1 = 1; x1 <= n; ++x1) {
        for (int y1 = 1; y1 <= m; ++y1) {
            int y2 = m, pre = -1;
            for (int x2 = x1; x2 <= n; ++x2) {
                if (x2 > x1 && area(x2 - 1, y1, x2, y2) == 0 && pre !=-1) {
                    ans += pre;
                    continue;
                }
                while (y2 >= y1 && area(x1, y1, x2, y2) > k) {
                    --y2;
                }
                int yy2 = y2;
                while (yy2 >= y1 && area(x1, y1, x2, yy2) == k) {
                    ++ans;
                    --yy2;
                }
                pre = y2 - yy2;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E – E-liter

题意

给你一个 n×nn \times n 的网格，有 mm 次询问，若询问为 1 R1 \:\ R，则第 RR 行都涂成黑色，若询问为 2 C2 \;\ C，则第 CC 列都涂成白色，最开始所有格子都是白色。问，每次询问后，黑色格子的数量

思路

树状数组{\color{yellow}树状数组}

最开始的总量为零，去找当前询问与上一次的变化量，维护每一次的总量

若当前询问为 1 R1 \;\ R ，则增加的黑色格子数为上一次的 1 R1 \;\ R 与这一次的 1 R1 \;\ R 之间的 2 C2 \;\ C 的数量（去重），于是，问题就转换成了求满足条件的区间和，用树状数组维护即可

tr/tctr / tc : 维护在该询问前，该行列的修改最后一次出现的时间

bit_r/bit_cbit\_r / bit\_c : 维护每次询问的时间戳，将时间戳作为“键”。有多少行/列最后一次操作在这个时间

对于第 ii 次查询，

若询问为 1 R1 \;\ R，查询 [trR,i][tr_R, i] 之间有多少个 bit_cjbit\_c_j

若询问为 2 C2 \;\ C ，查询 [trC+1,i][tr_C + 1, i] 之间有多少个 bit_rjbit\_r_j

我靠，真的只有自己写了才知道，这里面还有恶心人的细节：

对于 1 R1 \;\ R，可以直接查询 [trR,i][tr_R, i]，但是对于 2 C2 \;\ C ，查询的范围是 [trC+1,i][tr_C + 1, i]，因为若 trC=0tr_C = 0，则会查询到若干个还没有变成黑色的行，能够减去的前提是之前一定先变成过黑色。第二个易错点是， [trC+1,i][tr_C +1,i] 查询出来的答案可能为负，若第一次的询问是 2 12 \;\ 1 ，则查询范围是 [1,1][1, 1]，sum(1)−sum(0)=−nsum(1) – sum(0) = -n，所以，需要与 00 取上界

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define lowbit(x) (x & (-x))

struct BIT {
    int n;
    vector<int> tr;

    void init(int n_) {
        n = n_;
        tr.assign(n + 1, 0);
    }

    void add(int x, int k) {
        ++x;
        for (; x <= n; x += lowbit(x)) {
            tr[x] += k;
        }
    }

    int sum(int x) {
        ++x;
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += tr[x];
        }
        return ans;
    }

    int query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    BIT bit_r, bit_c;
    bit_r.init(q + 10);
    bit_c.init(q + 10);

    vector<int> tr(n + 5, 0), tc(n + 5, 0);
    bit_r.add(0, n);
    bit_c.add(0, n);

    int cur = 0;
    for (int i = 1; i <= q; ++i) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            // int delta = n - bit_c.sum(tr[x] - 1);
            int delta = bit_c.query(tr[x], i);
            cur += delta;
            bit_r.add(tr[x], -1);
            tr[x] = i;
            bit_r.add(tr[x], 1);
        }
        else {
            // int delta = n - bit_r.sum(tc[x]);
            int delta = max(bit_r.query(tc[x] + 1, i), 0LL);
            cur -= delta;
            bit_c.add(tc[x], -1);
            tc[x] = i;
            bit_c.add(tc[x], 1);
        }
        cout << cur << endl;
    } 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F – Total Product is N

题意

给出一个数 nn，有一个非空的序列 aa 满足以下条件：

  • a1 ˙a2 ˙a3 ...am=na_1 \.\ a_2 \.\ a_3 \ … a_m = n
  • a1≠a2≠a3...≠ana_1 \neq a_2 \neq a_3 … \neq a_n

问，所有满足条件的序列之和

思路

动态规划{\color{yellow}动态规划}

先分解 nn ，找到 nn 的因数，构成 aa 的的元素只可能在 nn 的因数中出现，数量级就可以从 1e101e10 下降到 1e51e5。我们想要知道一种和对应的分解方案数，用方案数去乘以和即可。

由于位置的不同对答案也有影响，所以需要保存选取的个数，最后乘以个数的阶乘。由于要求序列和，所以要保存当前的和是多少，根据条件最后的乘积为 nn，所以得保留中途过程中选取的因数的乘积。状态就定义出来了 dp[k][j][sm]dp[k][j][sm] 表示讨论了前 ii 个因数，选取 kk 个，乘积为 aja_j ，和为 smsm 的方案数，但是，由于和是在太大，三个维度加起来没法存，所以分解一下 -> 把 smsm 单拎出来，cnt[k][j]cnt[k][j] 表示选取 kk 个，乘积为 aja_j 的方案数，sm[k][j]sm[k][j] 表示选取 kk 个，乘积为 aja_j 的方案之和（不考虑顺序）

将 nn 进行因数分解，从小到大讨论他的因数，当讨论到 xx 时：

若 aj≢0(mod x)a_j \not\equiv 0 \;(mod \;\ x) ，则跳过，否则，进行下面讨论

若要选取 xx: cnt[k][j]→cnt[k−1][p]cnt[k][j] \to cnt[k-1][p] (pp 是 ajx\frac{a_j}{x} 这个数的位置），sum[k][j]→sm[k−1][p]+cnt[k−1][p] ˙xsum[k][j] \to sm[k – 1][p] + cnt[k-1][p] \.\ x

若不选取 xx: 则直接继承上一次状态，不变

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int MOD = 998244353;

void solve()
{
    int N;
    cin >> N;

    vector<int> a;

    a.push_back(0);
    for (int i = 1; i * i <= N; ++i)
    {
        if (N % i == 0)
        {
            a.push_back(i);

            if (i * i != N)
            {
                a.push_back(N / i);
            }
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;

    const int K = 14;

    vector<int> fac(K + 1, 0);
    fac[0] = 1;
    for (int i = 1; i <= K; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }

    vector<vector<int>> cnt(K + 1, vector<int>(m + 1, 0));
    vector<vector<int>> sum(K + 1, vector<int>(m + 1, 0));

    cnt[0][1] = 1;

    int ans = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x = a[i];
        for (int k = K; k >= 1; --k)
        {
            for (int j = 1; j <= m; ++j)
            {
                if (a[j] % x != 0)
                    continue;
                int y = a[j] / x;
                y = lower_bound(a.begin() + 1, a.end(), y) - a.begin();

                cnt[k][j] = (cnt[k][j] + cnt[k - 1][y]) % MOD;

                sum[k][j] = ((sum[k - 1][y] + cnt[k - 1][y] * x) % MOD + sum[k][j]) % MOD;
            }
        }
    }

    for (int i = 1; i <= K; ++i)
    {
        ans = (ans + sum[i][m] * fac[i] % MOD) % MOD;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

错误代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MOD = 998244353;

int dp[15][15][200010]; // 选前 k 个，乘积为 a[j]，总和为 sm 的方案数

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

    vector<int> a(1);

    for (int i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            a.push_back(i);

            if (i * i != n)
                a.push_back(n / i);
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;
    int K = 14;

    dp[0][1][0] = 1;

    for (int i = 1; i <= m; ++i) {
        int x = a[i];
        for (int k = K; k >= 1; --k) {
            for (int j = 1; j <= m; ++j) {
                for (int sm = x; sm <= 2e5; ++sm)
                {
                    if (a[j] % x != 0)
                        continue;
                    int y = a[j] / x;
                    int p = lower_bound(a.begin() + 1, a.end(), y) - a.begin();
                    dp[k][j][sm] = (dp[k][j][sm] + dp[k - 1][p][sm - x]) % MOD;
                }
            }
        }
    }

    vector<int> fac(K + 1, 0);

    fac[0] = 1;
    for (int i = 1; i <= K; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }

    int ans = 0;
    for (int i = 1; i <= K; ++i)
    {
        for (int sm = 1; sm <= 2e5; ++sm)
        {
            ans = (ans + sm * dp[i][m][sm] % MOD * fac[i] % MOD) % MOD;
        }
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

别人代码（DFS）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 3e5 + 5;
const ll mod = 998244353;

ll fac[N], n, ans;

void dfs(ll now, ll la, ll len, ll sum)
{
    ans = (ans + fac[len] * (now + sum) % mod) % mod;
    for (ll i = la + 1; i * i < now; ++i)
    {
        if (now % i == 0)
        {
            dfs(now / i, i, len + 1, sum + i);
        }
    }
}

void solve()
{
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= N - 5; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    dfs(n, 0, 1, 0);
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
“啊，英雄岁月，地久天长……”
— 老猪 · 紫川

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注