牛客春招刷题训练营-2025.5.8题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 墙壁划线

手玩一下可以知道答案和 没有关系。
对于单独的一条对角线，和格点的交点为 个。
如果 为偶数或 为偶数，两条对角线会相交于格点，答案要减去 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll a, b, x, y;
    cin >> a >> b >> x >> y;
    ll ans = 2 * (a + b + 1 - gcd(a, b));
    if ((a % 2 == 0) || (b % 2 == 0))
        ans--;
    cout << ans << '\n';
    return 0;
}

中等题 小红的排列构造

除了 以外，所有的偶数都不是质数，所以要尽量偶数方向构造。
当 时， 一定为偶数。
时，无法构造。
否则可以先在前 个位置放 ，第 个位置之后全部放 ，本题结束。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n <= 2)cout << -1;
    else {
        cout << "3 2 1 ";
        for (int i = 4; i <= n; i++)cout << i << ' ';
    }
    return 0;
}

困难题 串

需要用到的模板：取模运算类

动态规划，或者是递推。

表示未出现 的字符串个数。
表示出现 且 后面未出现 的字符串个数。
表示出现 且出现 的字符串个数。
初值为 ，表示空串， 和 初值都为 。

转移：
可以是出现过 的字符串添加了任意一个字符，或是只出现 的字符串添加了 。
。

可以是出现过 的字符串添加了任意一个不是 的字符，或是未出现 的字符串添加了字符 。
。

可以是未出现 的字符串添加了任意一个不是 的字符。
。

每一步都将答案加上 。
时间复杂度 。

using Z = ModInt<1000000007>;

int main() {
    int n;
    cin >> n;
    Z ans(0);
    array<Z, 3> dp = {Z(1), Z(0), Z(0)};
    for (int i = 1; i <= n; i++) {
        dp[2] = dp[1] + 26 * dp[2];
        dp[1] = dp[0] + 25 * dp[1];
        dp[0] = 25 * dp[0];
        ans += dp[2];
    }
    cout << ans << '\n';
    return 0;
}