题目链接

A - Find Multiple(签到题)

1. 题目描述

在[A,B]区间找到一个数是C的倍数

2. 思路

略。

3. 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1;
const int M = 1e9+7;



int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    int a,b,c;
    cin >> a >> b >> c;
    int res = -1;
    for (int i = a; i <= b; i++) {
        if (i%c == 0) {
            res = i;
            break;
        }
    }
    cout << res << endl;
    return 0;
}

• 时间复杂度: O(b-a)
• 空间复杂度: O(1)

B - Base K(签到题)

1. 题目描述

给你$KK$K进制的$A,BA,B$A,B两个数，求十进制的$A\times BA\; \backslash times\; B$A×B

2. 思路

$KK$K不超过10，所以好搞。注意爆int

3. 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5;
const int M = 1e9 + 7;

int k;
string a, b;

ll trans(string s, int k) {
    ll base = 1, res = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        res += base * (s[i] - '0');
        base *= k;
    }
    return res;
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> k >> a >> b;

    ll x = trans(a, k), y = trans(b, k);
    cout << x * y << endl;
    return 0;
}

• 时间复杂度: O(logA+logB)
• 空间复杂度: O(1)

C - Long Sequence(前缀和)

1. 题目描述

给你一个正数数组$A_1,....A_{n}A\_1,\; ....\; A\_n$A1​,....An​, 数组$BB$B是数组$AA$A重复$10^{100}10^\{100\}$10100遍，求$BB$B的前几项和超过$XX$X?

2. 思路

求A的前缀和，然后算出整个A相加几轮最接近且不超过X，然后剩余的部分再遍历前缀和，看哪一项能加到X以上。(可以二分查找，但是A的长度为$10^{5}10^5$105，直接暴力也够通过）

3. 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const int M = 1e9+7;

int n;
ll x, sum;
ll a[N], s[N];

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }

    cin >> x;
    ll res = x/s[n]*n, b = x%s[n];

    for (int i = 1; i <= n; i++) {
        if (s[i] > b) {
            res += i;
            break;
        }
    }

    cout << res << endl;
    return 0;
}

• 时间复杂度: O(n), 计算前缀和
• 空间复杂度: O(n) 前缀和数组

D - FG operation（dp）

1. 题目描述

给你一个0-9组成的字符串$A_1,....A_{n}A\_1,\; ....\; A\_n$A1​,....An​和两种操作：

• F操作：把最左面两个数x和y删除，换成$(x+y)\%10(x+y)\backslash \%10$(x+y)%10
• G操作：把最左面两个数x和y删除，换成$(x\ast y)\%10(x*y)\backslash \%10$(x∗y)%10

对数组做若干次F和G操作，直到把这个字符串的长度变成1，问有多少种方案，使得最后剩下的数字是$KK$K?

2. 思路

因为操作过程中，只跟前两个数有关系，所以想到动态规划。

令dp[i][j]表示字符串操作了i次，头部为j的方案数，则dp[i]可以用dp[i-1]推算而来：

dp[i][(j+a[i])%10]+=dp[i-1][j]

dp[i][(j*a[i])%10]+=dp[i-1][j]

初始化dp[1][a[1]] = 1，最终dp[n][k]即为答案

3. 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const int M = 998244353;

int n;
int a[N], dp[N][11];

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[1][a[1]] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            int f = (j+a[i]) % 10;
            int g = (j*a[i]) % 10;
            dp[i][f] = (dp[i][f] + dp[i-1][j]) % M;
            dp[i][g] = (dp[i][g] + dp[i-1][j]) % M;
        }
    }
    for (int i = 0; i <= 9; i++) cout << dp[n][i] << endl;
    return 0;
}

• 时间复杂度: $O\left(n\right)O(n)$O(n)，二维dp，其中一维是常数
• 空间复杂度: $O\left(n\right)O(n)$O(n)

E - Distance on Large Perfect Binary Tree（二叉树,统计，好题）

1. 题目描述

给你一个$NN$N层的满二叉树，问有多少(i,j)点对，使得距离为$KK$K

2. 思路

因为是满二叉树，所以同一层每个点都一样，看每一个点对答案的贡献就行了。

设f(u)表示距离为K且LCA为u的点对，则答案就是所有f(u)的和，接下来看每个点对f(u)的贡献：

• 如果i或j就是u，如果u点的深度d<=n-k, 则存在$2^{K}2^K$2K个点，否则不存在这种情况
• i和j分别在u的左右子树（不可能在一边子树），那么考虑i和j相对于u的深度，假设是左子树走x步，则右子树走k-x步，那么需满足d+x<=n, d+K-x<=n, 且1<=x<=K-1.

对每个合理的x，左边有$2^{x-1}2^\{x-1\}$2x−1种情况，右边有$2^{k-x-1}2^\{k-x-1\}$2k−x−1种情况，那么总共有$2^{k-2}2^\{k-2\}$2k−2种情况，根据上述不等式可以解出有多少个x，统计到f(u)的贡献中。

最后统计每一层的点个数，每一层的u都是一样的，统计f(u)对整体答案的贡献即可。

因为有各种2的幂，先预处理2e6范围内的$2^n\%M2^n\backslash \%M$2n%M

3. 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e6 + 5;
const int M = 998244353;

ll p[N];

int n, k;


int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;
    p[0] = 1;
    for (int i = 1; i < N; i++) p[i] = (p[i - 1] * 2) % M;

    ll res = 0;
    for (int i = 1; i <= n; i++) {
        // 第i层有p[i]个点
        // 每个点有2种情况
        ll temp = 0;

        if (i + k <= n) temp += p[k];

        if (k >= 2) {
            int l = max(1, i + k - n), r = min(k - 1, n - i);
            temp = (temp + p[k - 2] * max(0, r - l + 1)) % M;
        }

        res = (res + temp * p[i]) % M;
    }

    cout << res << endl;
    return 0;
}

• 时间复杂度: $O\left(n\right)O(n)$O(n)，一重循环
• 空间复杂度: $O\left(n\right)O(n)$O(n) 预处理