训练赛2题解

牛客题解较乱，写了一篇个人题解供参考
题解按照题目序号排列
希望大家多思考，不要用AI写做题,对自己并没有帮助

A题

知识点:排序，模拟
由于一次只能找n-1个数进行排序
可以发现能在三次之内完成整个数组排序
可以很容易想到当最大值在首位，最小值在末尾时此时是唯一需要三次排序才能排完的
当最大值或最小值已经在对应位置上时，此时只需1次排序
其他都需要2次
注意：需要特判，若数组本身就是有序的，此时为0

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    int mx = *max_element(f.begin() + 1, f.end()), mn = *min_element(f.begin() + 1, f.end());
    int l = 0, r = 0;
    bool x = true;
    for (int i = 1; i <= n; i++) {
        if (f[i] < f[i - 1]) {
            x = false;
        }
        if (f[i] == mx) {
            r = i;
        } else if (f[i] == mn) {
            l = i;
        }
    }
    if (x) {
        cout << 0 << '\n';
        return 0;
    }
    if (l == 1 || r == n) {
        cout << 1 << '\n';
    } else if (l == n && r == 1) {
        cout << 3 << '\n';
    } else {
        cout << 2 << '\n';
    }
    return 0;
}

B题

知识点:数学
先考虑打表，先不考虑x形，打表若为n条直线，最多可切割多少平面
由于切割平面并不好思考，可以发现，若本条线与其他线交点为k个时，会产生k+1个平面
故当对n个直线最大的情形时，最多可以与直线交n-1个交点，故可以得到递推公式
$f(n)=f(n-1)+n$ 其中首项为 $1$ ，得到通项公式为 $\frac{n*(n+1)}{2}+1$
由于是x形，故n取偶数即可，即 $2n^2+n+1$

C题

知识点：模拟
模拟题，只需要暴力存入所有情况，并暴力即可
注意输入时，中间间隔一列"."\

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
void solve() {
    vector<vector<string>> num(10, vector<string>(7));
    num[0] = {"*****", "*...*", "*...*", "*...*", "*...*", "*...*", "*****"};
    num[1] = {"....*", "....*", "....*", "....*", "....*", "....*", "....*"};
    num[2] = {"*****", "....*", "....*", "*****", "*....", "*....", "*****"};
    num[3] = {"*****", "....*", "....*", "*****", "....*", "....*", "*****"};
    num[4] = {"*...*", "*...*", "*...*", "*****", "....*", "....*", "....*"};
    num[5] = {"*****", "*....", "*....", "*****", "....*", "....*", "*****"};
    num[6] = {"*****", "*....", "*....", "*****", "*...*", "*...*", "*****"};
    num[7] = {"*****", "....*", "....*", "....*", "....*", "....*", "....*"};
    num[8] = {"*****", "*...*", "*...*", "*****", "*...*", "*...*", "*****"};
    num[9] = {"*****", "*...*", "*...*", "*****", "....*", "....*", "*****"};
    vector<string> s1(7), s2(7);
    string s;
    for (int i = 0; i < 7; i++) {
        cin >> s;
        s1[i] = s.substr(0, 5);
        s2[i] = s.substr(6);
    }
    auto check = [&](int x, vector<string> s) -> bool {
        for (int i = 0; i < 7; i++) {
            if (s[i] != num[x][i]) {
                return 0;
            }
        }
        return 1;
    };
    int a, b;
    for (int i = 0; i < 10; i++) {
        if (check(i, s1)) {
            a = i;
        }
        if (check(i, s2)) {
            b = i;
        }
    }
    int c = a + b;
    for (int i = 0; i < 7; i++) {
        if (c >= 10) {
            cout << num[1][i] << '.';
        }
        cout << num[c % 10][i] << '\n';
    }
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D题

知识点：递推,数学
本题，由于数据范围较大，使用递归记忆化会超时，能拿到 $85.71%$ 的分
考虑递推,将原式拆开进行合并
需要注意: 当减至相同时，只取一次，例如 $f(4)=f(3)+f(1)+2*f(2)=5$
而不是 $f(4)=f(3)+f(1)+2*(f(2)+f(2))=7$
通过递推可以发现递推公式 $f(n)=f(n-1)+\sum_{i = (n-1)/2+1}^{n-1}f(i)$
区间范围使用前缀和优化

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<i64> f(n + 1), pre(n + 1);
    f[1] = f[2] = 1;
    pre[1] = 1, pre[2] = 2;
    for (int i = 2; i < n; i++) {
        pre[i] = (pre[i - 1] + f[i]) % MOD;
        f[i + 1] = (f[i] + pre[i] - pre[i / 2] + MOD) % MOD;
    }
    cout << f[n];
    return 0;
}

E题

知识点：数学
前置知识:
算术基本定理：任何一个大于 $1$ 的自然数 $N$ ,如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积 $N=P_1^{a_1}P_2^{a_2}P_3^{a_3}......P_n^{a_n}$ ，这里 $P_1<P_2<P_3......<P_n$ 均为质数，其中指数 $a_i$ 是正整数。这样的分解称为 $N$ 的标准分解式。
此时，N的因数个数为 $\amalg_i^n (a_i+1)$
回到题目，进行化简，先同时乘n
$\frac{n}{x}+\frac{n}{y}=1 \rightarrow nx+ny=xy$
由 $(x-n)(y-n)=xy-nx-ny+n^2$ 可以将式子化为 $(x-n)(y-n)=n^2$
将 $(x-n)$ 和 $(y-n)$ 看作两个变量乘积为 $n^2$ ，即寻找 $n^2$ 因子个数，乘积等于 $n^2$ 的种类数即为答案
由于 $1<=n<=1e9$ ,讨论因子时在小于等于 $\sqrt(n)$ 范围即可，遍历后剩下的数若非质数，一定会被 $\sqrt(1e9)$ 内被除掉，遍历完成后若仍 $n>1$ ,此时 $n$ 一定为质数
由于进行了平方，则上式因子个数变为 $\amalg_i^n (2*a_i+1)$
此时对于一个因数，需要与另一个因数且仅一个进行匹配,由于 $2*a_i+1$ 总为奇数，最后cnt结果也为奇数，故总匹配数为 $\lfloor{\frac{cnt}{2}}\rfloor +1$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 4e5;
vector<int> pri;
bool not_prime[N + 1];

void pre(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            pri.push_back(i);
        }
        for (int pri_j : pri) {
            if (i * pri_j > n)
                break;
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
                break;
            }
        }
    }
}

void solve() {
    i64 n;
    cin >> n;
    i64 cnt = 1;
    i64 t = n;
    for (int i = 0; 1LL * pri[i] * pri[i] <= n && t > 1; i++) {
        if (t % pri[i] == 0) {
            int s = 0;
            while (t % pri[i] == 0) {
                s++;
                t /= pri[i];
            }
            cnt *= (2LL * s + 1);
        }
    }
    if (t > 1) {
        cnt *= 3;
    }
    i64 res = cnt / 2 + 1;
    cout << res << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    pre(N);
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F题

知识点：数学，二分 若我们按照题意，证明b是否满足要求，去找是否存在a满足题意，无论是复杂度还是难度都不太允许
故考虑由 $a$ 推出合法 $b$ 将 $2*a*(a+1)^2=b^2 \rightarrow \sqrt{2a}*(a+1)=b$
其中 $(a+1)$ 和 $b$ 为正整数,故当 $2a$ 为平方数时，此时对应一个 $b$
由于 $n$ 范围较大， $\sqrt{1e19}$ 并不能在 $1s$ 内通过，故不能遍历出所有 $b$ 再找答案
考虑上方式子，可以等效为 $\sqrt{2a}*(a+1)>=n(2a为平方数)$ 求出其最小值
很明显左式是一个单调递增函数，考虑二分
由于数值较大，我二分的是 $\sqrt{2a}$ ,其范围大致在 $1e7$ 内满足要求
注意：1.本题数据量较大，读入的n就已经超过long long,至少需要unsigned long long才能存下
2.在我这种二分的方法下，由于 $2a$ 一定是偶数，故二分传入的mid也必须是偶数才有效，需要讨论
3.数据范围较大，运算过程中甚至会爆unsigned long long,需要考虑使用更大的数据类型储存，例如int128

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
void solve() {
    u64 n;
    cin >> n;
    auto check = [&](i128 mid) -> i128 { return mid * (mid * mid / 2 + 1); };
    i128 l = 0, r = 1e7;
    i128 res = 0;
    while (l <= r) {
        i128 mid = (l + r) / 2;
        if (mid & 1) {
            if (check(mid - 1) >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {
            if (check(mid) >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    }
    cout << (u64)check(l) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

G题

知识点：数位dp
题意对于每一个 $A_i$ (满足 $0<=A_i<=R_i$ )找到有多少种序列满足 $A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]$
根据或运算性质，若二进制位上同为 $1$ 时，加***造成进位导致不相等，即 $n$ 个数需要在二进制位上不同位置上并且在给定 $R[i]$ 范围内置 $1$ ，求其种类数，由于数据范围较大，考虑进行数位 $dp$
$dp[i][j]$ 表示到第 $i$ 位，各 $j$ 个数上是否为上限， $0$ 说明为上限， $1$ 说明非上限
依照上述要求进行记忆化搜索，详细看注释

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 MOD = 1e9 + 9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<i64> r(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    vector<vector<i64>> dp(64, vector<i64>(1 << (n + 1), -1));
    auto dfs = [&](auto dfs, int len, int limit) -> i64 {
        if (len < 0) {//若已经到超过最后一位返回
            return 1;
        }
        if (dp[len][limit] != -1) {//记忆化搜索，返回已经赋值的情况
            return dp[len][limit];
        }
        i64 res = 0;//用于储存n个上界Ri二进制位上第len位的情况
        for (int i = 1; i <= n; i++) {
            if ((1LL << len) & r[i]) {
                res |= (1LL << i);
            }
        }
        i64 ans = dfs(dfs, len - 1, res | limit);//直接置0
        for (int i = 1; i <= n; i++) {
            if ((1LL << i) & limit) {//若第i个数已经非上限，填1
                ans = (ans + dfs(dfs, len - 1, res | limit)) % MOD;
            } else if ((1LL << i) & res) {//若第i个数limit仍在上限，但当前R[i]可以填1，需要将第i为反置
                ans = (ans + dfs(dfs, len - 1, (res ^ (1LL << i)) | limit)) % MOD;
            }
        }
        return dp[len][limit] = ans;
    };
    cout << dfs(dfs, 63, 0);
    return 0;
}

H题

知识点:字符串，队列
题意：即寻找连续子字符串包含 $'L','O','V','E'$ 的种类数
题目已说明只会出现大写字母，先考虑若我们选到了 $'L','O','V','E'$ 四个字母的最短序列后，如何求有多少子字符串包含这四个字母呢，显而易见种类数为 $(左侧字母数+1)*(右侧字母数+1)$ ，但很明显字符串中，并不会四个字母只出现一次，所以按照这种方式遍历，一定会出现重复并且复杂度过高不能接受。
观察样例 $LOVELOVE$ ,发现第一个 $LOVE$ 产生的答案，在遍历至第二个字母开始即子字符串OVEL时，若收纳左侧字母，会导致重复，故我们对需要第一个出现LOVE四个字母时乘上 $左侧字母+1$ ，其他情况左侧皆乘 $1$ 即可
如何遍历呢，考虑使用类似滑动窗口的解法，当收纳的已经满足 $LOVE$ 皆在则记录答案并将左侧弹出，依次向右移动逐渐压入字符即可

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
void solve() {
    string s;
    cin >> s;
    vector<char> f(27);
    int n = s.size();
    int res = 0;
    queue<char> que;
    for (int i = 0; i < n; i++) {
        que.push(s[i]);
        f[s[i] - 'A']++;
        while (f[4] && f[11] && f[14] && f[21]) {
            f[que.front() - 'A']--;
            que.pop();
            res += n - i;
        }
    }
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

题解 | #训练赛2#

训练赛2题解

A题

B题

C题

D题

E题

F题

G题

H题