AtCoder Beginner Contest 465

by JiuQiin AtCoder, 题解on Posted on

反思

又是这样，永远最后一个小时卡在 D，之前做过一道很类似的，给出一个数 x ，每次乘个 k 乘回去，乘一次，下限是 x⋅kx \cdot k ，上限是 x⋅k+(k−1)=(x+1)⋅kx \cdot k + (k – 1) = (x + 1) \cdot k ；乘两次，下限是 x⋅k2x \cdot k^2 ，上限是 [x⋅k+(k−1)]⋅k+(k−1)=(x+1)⋅k2[x \cdot k + (k – 1)] \cdot k + (k – 1) = (x +1) \cdot k^2，以此类推，乘以 m 次，下限是 x⋅kmx \cdot k^m ，上限是 (x+1)⋅km(x +1)\cdot k^m，最后看 m 等于多少时，给出的 y 在此范围内。当时我就想这个 D 与其很类似，我先除，一连串的除之后，再跟着一连串的乘，我每次除完，都试着往上去乘，看最后 y 是否在这个范围内。结果，T 六个，WA 两个，首先超时我能接受，时间复杂度是 O(n(lgn)2)≈7.2e8O(n(lgn)^2) \approx 7.2e8，但 wa 我是真不理解

Contents hide
1 A – Supermajority
1.1 题意
1.2 思路
1.3 代码
2 B – Parking 2
2.1 题意
2.2 思路
2.3 代码
3 C – Reverse Permutation
3.1 题意
3.2 思路
3.3 代码
4 D – X to Y
4.1 题意
4.2 思路
4.3 代码
5 E – Digit Circus
5.1 题意
5.2 思路
5.3 代码
6 F – Sjeltzer?
6.1 题意
6.2 思路
6.3 代码
6.4 优化代码

A – Supermajority

题意

给你正整数 A 和 B 。

如果 A≥B×32A \geq B \times \frac{3}{2} ，则输出 YESYES，否则，输出 NONO

思路

如果 2⋅A≥3⋅B2 \cdot A \geq 3 \cdot B，则输出 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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

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

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

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

B – Parking 2

题意

给定 LL, RR，在此期间每小时收费 XX 元，其余时间收费 YY 元，不跨过午夜，问一天收费多少

思路

去枚举一天 24 小时，看当前时间段是否在 [L,R][L, R] 区间，有一点要注意，左闭右开{\color{Yellow} 左闭右开}，什么意思呢？举个例子，如果 L=3，R=5 L= 3， R = 5，从 11 开始数，t=1t = 1 时加 yy， t=2t = 2 时加 yy ，t=3t = 3 时加 xx ，因为 3≤t=3<53 \leq t=3 <5 ，t=4t = 4 时加 xx，因为 3≤t=4<53\leq t = 4 < 5，t=5t = 5 时加 yy，因为 3≤t=5≮53 \leq t = 5 \nless 5，这是因为我们枚举的是时间点，而每个时间点管的是当前时间点以及后面一个小时这个时间段，所以 t=5t = 5 其实代表的是 55 到 66 这个时间段，而 R=5R = 5，他到 55 点就已经结束了

代码

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL x, y, l, r, a, b;
    cin >> x >> y >> l >> r >> a >> b;
    LL ans = 0;
    for (LL i = a; i < b; ++i) {
        if (i >= l && i < r) {
            ans += x;
        }
        else {
            ans += y;
        }
    }
    cout << ans << endl;
}

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

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

C – Reverse Permutation

题意

给出一个整数 n 和一个长度为 n 的由 o 和 x 组成的字符串 s，定义数组 a = 1, 2, 3 … n

若 sis_i = o，则将数组 a 的前 i 项倒置，具体来说，就是变成 ai,ai−1,ai−2...a2,a1,ai+1,ai+2...ana_i, a_{i-1}, a_{i-2}…a_2, a_1, a_{i+1}, a_{i+2}…a_n

若 sis_i = x，则不做任何变化

问最后数组 a 的模样

思路

呃，怎么说呢，这道题我是猜的，我发现，从 1 慢慢增大，每个数放置的位置几乎都是左一个，右一个，再左一个，右一个……我本想从小到大走，但我们无法知道 1 的具体位置，所以就选择从大往小的走，我发现，只要是 sis_i = o，这一次如果是倒着放，下一次就会正着放，反之亦然，但如果 sis_i = x，则不会改变放的方向，这就很像双端队列，只不过一个是从内部添加，一个是从外部添加

为啥这么做？别问我，我也不知道

代码

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin  >> n;
    string s;
    cin >> s;
    s = " " + s;

    int l = 1, r = n, op = 0;

    vector<int> ans(n + 1, 0);
    auto move = [&](int idx) {
        if (op == 1) {
            ans[l] = idx;
            ++l;
        }
        else {
            ans[r] = idx;
            --r;
        }
    };

    for (int i = n; i >= 1; --i) {
        if (s[i] == 'o') {
            op ^= 1;
        }
        move(i);
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

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

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

D – X to Y 

题意

给出两个数 X ， Y 以及一个大于二的整数 k，X 可进行以下操作使得 X 变成 Y， 最初 x = X：

  • 令 y=⌊xk⌋y = \lfloor \frac{x}{k} \rfloor，然后 x=yx = y
  • 令 x=⌊yk⌋x = \lfloor \frac{y}{k} \rfloor，然后 x=yx = y

问最少的操作次数

思路

以 k = 3 为例，发现，上述两种操作互为逆运算，意思就是说，⌊43⌋=1\lfloor \frac{4}{3}\rfloor = 1 中 x=4,y=1x = 4, y = 1 ，但也可以是 y=4,x=1y = 4, x = 1，发现，单看乘的话，0 -> 1, 0 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 6, 2 -> 7, 2 -> 8, 3 -> 9, 3 -> 10, 3 -> 11, 4 -> 12 , 4 -> 13 …逆运算就是把箭头反向，这样就形成了一棵树：

我们想让 X 变成 Y，实际上是在走一条 X 到 Y 的最短路径，即找他们的最近公共祖先，但我们不可能真的去建这么一棵双向连边的树，只是需要用到这种思想，实现方式是每次去比较 X 和 Y，让较大数除以 K，直到最后两数相等，呃，这好像就是在模拟找最近公共祖先的过程

代码

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL x, y, k;
    cin >> x >> y >> k;
    LL cnt = 0;
    while (x != y) {
        if (x > y) {
            x /= k;
        }
        else {
            y /= k;
        }
        ++cnt;
    }
    cout << cnt << endl;
}

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

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

E – Digit Circus

题意

求在 998244353 的模中，有 1≤x≤N 的整数 x 满足下列三个条件中有且仅有一个条件的个数。

  • x 是 3 的倍数。
  • x 的十进制表示包含 3。
  • x 的十进制表示恰好使用了三个不同的数字。

在这里，整数的十进制表示不应有不必要的前导 “0”。

思路

数位dp{\color{Yellow}数位 dp}，dp[pos][mask][mod][ti]dp[pos][mask][mod][ti]

maskmask : 记录出现过的数字

modmod : 记录模 3 的余数

titi : 记录所枚举的前 pos 位的数是否小于前 pos 位的 s

在更新 mask 的时候要考虑前导零，如果之前一个数都没出现过，也就是前面全都是 0（mask = 0），若当前枚举的 x = 0，则此 0 扔归为到前导零当中 mask 不更新，其余情况 mask 都要更新

在更新 ti 的时候要考虑之前是否已经小于 s，若已经小于，则之后都会是小于，nti = ti，若之前都是等于，而当前枚举的 x < lim（lim = s[i] – ‘0’），则 nti 更新为 1，即小于，否则，仍是等于。若之前都是等于，为防止超出 x，则枚举当前 x 的上限为 lim，否则上限为 9

代码

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

int dp[505][1 << 10][3][2];

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    dp[0][0][0][0] = 1;
    for (int pos = 0; pos < n; ++pos) {
        int lim = s[pos] - '0';
        for (int mask = 0; mask < (1 << 10); ++mask) { // 枚举前 pos 位出现过的值
            for (int mod = 0; mod < 3; ++mod) {
                for (int ti = 0; ti <= 1; ++ti) { // 记录构造的前 pos 位的数是否小于前 pos 位的 s
                    if (!dp[pos][mask][mod][ti]) continue;
                    int up = ti ? 9 : lim; // 如果到目前为止仍是等于 ti = 0，为防止大于 s，则当前枚举的上限是 lim
                    for (int x = 0; x <= up; ++x) { // 枚举第 pos 位的值
                        int nmask;
                        if (mask == 0 && x == 0) {
                            nmask = 0; // 若到目前为止都是前导零，则当前的数值 x = 0 不计入出现过的数中
                        }
                        else {
                            nmask = mask | (1 << x);
                        }
                        int nmod = (mod + x) % 3;
                        int nti = ti; // 如果之前是小于，则之后一直都是小于
                        if (ti == 0 && x < lim) { // 如果之前都是等于，而第 pos 位枚举的 x < lim ，则之后都是小于
                            nti = 1;
                        }
                        dp[pos + 1][nmask][nmod][nti] += dp[pos][mask][mod][ti];
                        dp[pos + 1][nmask][nmod][nti] %= MOD;
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int mask = 1; mask < (1 << 10);++mask) {
        for (int mod = 0; mod < 3; ++mod) {
            for (int ti = 0; ti <= 1; ++ti) {
                int cond = 0;
                if (mod == 0) { // 是否是三的倍数
                    ++cond;
                }
                int p = __builtin_popcount(mask);
                if (p == 3) { // 是否使用了三种不同的数字
                    ++cond;
                }
                if (mask & (1 << 3)) { // 是否出现了 3
                    ++cond;
                }
                if (cond == 1) { // 有且仅有一种条件满足
                    ans += dp[n][mask][mod][ti];
                    ans %= MOD;
                }
            }
        }
    }

    cout << ans << endl;
}

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

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

F – Sjeltzer?

题意

给出 nn 个六位数字 sis_i 以及他们的权值 wiw_i ，保证每个数字都是不同的。给出 qq 次询问，每次给出六位数字的 x,yx, y，找出满足所有的 0≤i≤6，xi≤si≤yi0\leq i\leq 6 ，x_i \leq s_i \leq y_i 的权值之和

思路

前缀和，容斥{\color{Yellow}前缀和，容斥}

设前缀和数组为 s

先看一维，给出区间 [x, y] ，ans = s[y] – s[x – 1]

扩展到二维，给出区间 [x1,x2] ˜[y1,y2][x1, x2] \~\ [y1, y2]，这个的意思是，假设给出的数字都是两位，比如 x=21,y=45x = 21, y = 45，则 x1=2,x2=1,y1=4,y2=5，ans=s[y1][y2]−s[x1−1][y2]−s[y1][x2−]+s[x1−1][x2−1]x1 = 2, x2 = 1, y1 = 4, y2 = 5，ans = s[y1][y2] – s[x1 – 1][y2] – s[y1][x2 – ] + s[x1 – 1][x2 – 1]

三维同理，用容斥原理，ans=s[y1][y2][y3]−s[x1−1][y2][y3]−s[y1][x2−1][y3]−s[y1][y2][x3−1]+s[x1−1][x2−1][y3]+s[x1−1][y2][x3−1]+s[y1][x2−1][x3−1]−s[x1−1][x2−1][x3−1]ans = s[y1][y2][y3] – s[x1 – 1][y2][y3] – s[y1][x2 – 1][y3] – s[y1][y2][x3 – 1] + s[x1 – 1][x2 – 1][y3] + s[x1 – 1][y2][x3 – 1] + s[y1][x2 – 1][x3 – 1] – s[x1 – 1][x2 – 1][x3 – 1]

发现，有奇数个 (xi−1)(x_i – 1) 的形式，前面符号为减，否则，为加

对了，还有前缀和的初始化 :

一维： si=si−1+ais_i = s_{i – 1} + a_i

for (int i = 1; i <= n; ++i) {
    string x;
    int w;
    cin >> x >> w;
    int a = x[0] - '0';
    s[a] = w;
}

for (int a = 1; a < 10; ++a) {
    s[a] += s[a - 1];
}

二维：

for (int i = 1; i <= n; ++i) {
        string x;
        int w;
        cin >> x >> w;
        int a = x[0] - '0';
        int b = x[1] - '0';
        s[a][b] = w;
    }

    for (int a = 1; a < 10; ++a) {
        for (int b = 0; b < 100; ++b) {
            s[a][b] += s[a - 1][b];
        }
    }

    for (int a = 0; a < 10; ++a) {
        for (int b = 1; b < 10; ++b) {
            s[a][b] += s[a][b - 1];
        }
    }

……以此类推至六维

代码

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

LL s[10][10][10][10][10][10];

void solve() {
    LL n;
    cin >> n;
    for (LL i = 1; i <= n; ++i) {
        LL w;
        string x;
        cin >> x >> w;
        LL a = x[0] - '0';
        LL b = x[1] - '0';
        LL c = x[2] - '0';
        LL d = x[3] - '0';
        LL e = x[4] - '0';
        LL f = x[5] - '0';
        s[a][b][c][d][e][f] = w;
    }

    for (LL a = 1; a < 10; ++a) {
        for (LL b = 0; b < 10; ++b) {
            for (LL c = 0; c < 10; ++c) {
                for (LL d = 0; d < 10; ++d) {
                    for (LL e = 0; e < 10; ++e) {
                        for (LL f = 0; f < 10; ++f) {
                            s[a][b][c][d][e][f] += s[a - 1][b][c][d][e][f];
                        }
                    }
                }
            }
        }
    }

    for (LL a = 0; a < 10; ++a)
    {
        for (LL b = 1; b < 10; ++b)
        {
            for (LL c = 0; c < 10; ++c)
            {
                for (LL d = 0; d < 10; ++d)
                {
                    for (LL e = 0; e < 10; ++e)
                    {
                        for (LL f = 0; f < 10; ++f)
                        {
                            s[a][b][c][d][e][f] += s[a][b - 1][c][d][e][f];
                        }
                    }
                }
            }
        }
    }

    for (LL a = 0; a < 10; ++a)
    {
        for (LL b = 0; b < 10; ++b)
        {
            for (LL c = 1; c < 10; ++c)
            {
                for (LL d = 0; d < 10; ++d)
                {
                    for (LL e = 0; e < 10; ++e)
                    {
                        for (LL f = 0; f < 10; ++f)
                        {
                            s[a][b][c][d][e][f] += s[a][b][c - 1][d][e][f];
                        }
                    }
                }
            }
        }
    }

    for (LL a = 0; a < 10; ++a)
    {
        for (LL b = 0; b < 10; ++b)
        {
            for (LL c = 0; c < 10; ++c)
            {
                for (LL d = 1; d < 10; ++d)
                {
                    for (LL e = 0; e < 10; ++e)
                    {
                        for (LL f = 0; f < 10; ++f)
                        {
                            s[a][b][c][d][e][f] += s[a][b][c][d - 1][e][f];
                        }
                    }
                }
            }
        }
    }

    for (LL a = 0; a < 10; ++a)
    {
        for (LL b = 0; b < 10; ++b)
        {
            for (LL c = 0; c < 10; ++c)
            {
                for (LL d = 0; d < 10; ++d)
                {
                    for (LL e = 1; e < 10; ++e)
                    {
                        for (LL f = 0; f < 10; ++f)
                        {
                            s[a][b][c][d][e][f] += s[a][b][c][d][e - 1][f];
                        }
                    }
                }
            }
        }
    }

    for (LL a = 0; a < 10; ++a)
    {
        for (LL b = 0; b < 10; ++b)
        {
            for (LL c = 0; c < 10; ++c)
            {
                for (LL d = 0; d < 10; ++d)
                {
                    for (LL e = 0; e < 10; ++e)
                    {
                        for (LL f = 1; f < 10; ++f)
                        {
                            s[a][b][c][d][e][f] += s[a][b][c][d][e][f - 1];
                        }
                    }
                }
            }
        }
    }

    auto deal = [&](string x, string y)
    {
        LL ans = 0;
        for (LL i = 0; i < 6; ++i)
        {
            LL a = x[i] - '0';
            LL b = y[i] - '0';
            if (a > b)
            {
                return 0LL;
            }
        }

        for (LL mask = 0; mask < (1 << 6); ++mask)
        {
            LL ok = true;
            vector<LL> p(7, 0);
            for (LL i = 0; i < 6; ++i)
            {
                LL a = x[i] - '0';
                LL b = y[i] - '0';
                LL d = (mask >> i & 1);
                if (d)
                {
                    if (a == 0)
                    {
                        ok = false;
                        break;
                    }
                    p[i] = a - 1;
                }
                else
                {
                    p[i] = b;
                }
            }

            if (!ok)
            {
                continue;
            }

            LL sign = (__builtin_popcount(mask) & 1) ? -1 : 1;
            ans += sign * s[p[0]][p[1]][p[2]][p[3]][p[4]][p[5]];
        }

        return ans;
    };

    LL q;
    cin >> q;
    while (q--) {
        string x, y;
        cin >> x >> y;
        LL res = deal(x, y);
        cout << res << endl;
    }
}

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

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

优化代码

将六维压缩成一维

#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;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    LL n;
    cin >> n;
    vector<LL> s(1000000, 0);

    for (LL i = 1; i <= n; ++i)
    {
        LL x, w;
        cin >> x >> w;
        s[x] = w;
    }

    LL pw[] = {100000, 10000, 1000, 100, 10, 1};

    for (LL i = 0; i < 6; ++i)
    {
        for (LL mask = 0; mask < 1000000; ++mask)
        {
            LL p = mask / pw[i] % 10;
            if (p)
            {
                s[mask] += s[mask - pw[i]];
            }
        }
    }

    auto deal = [&](LL x, LL y)
    {
        LL ans = 0;
        for (LL i = 0; i < 6; ++i)
        {
            LL a = x / pw[i] % 10;
            LL b = y / pw[i] % 10;
            if (a > b)
            {
                return 0LL;
            }
        }

        for (LL mask = 0; mask < (1 << 6); ++mask)
        {
            // LL p, tmp = 0;
            // for (LL i = 0; i < 6; ++i)
            // {
            //     if (mask & (1 << i))
            //     {
            //         p = max(x / pw[i] % 10 - 1, 0); 只要有某一维是 -1，不代表这一维的答案是 0，而是整个答案都是 0 
            //     }
            //     else
            //     {
            //         p = y / pw[i] % 10;
            //     }
            //     tmp += (p * pw[i]);
            // }

            bool ok = true;
            LL tmp = 0;

            for (LL i = 0; i < 6; i++)
            {
                LL d;

                if (mask >> i & 1)
                {
                    d = x / pw[i] % 10;

                    if (d == 0)
                    {
                        ok = false;
                        break;
                    }

                    d--;
                }
                else
                {
                    d = y / pw[i] % 10;
                }

                tmp += d * pw[i];
            }

            if (!ok)
                continue;

            if (__builtin_popcount(mask) & 1)
            {
                ans -= s[tmp];
            }
            else
            {
                ans += s[tmp];
            }
        }
        return ans;
    };

    LL q;
    cin >> q;
    while (q--)
    {
        LL x, y;
        cin >> x >> y;
        LL res = deal(x, y);
        cout << res << endl;
    }
}

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

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}
“THE PROLOGUE. Experience, though none authority Were in this world, is right enough for me”
— Geoffrey Chaucer · The Canterbury Tales. The Wife of Bath's Tale.
Post authorWritten by

Leave a Comment

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