2024牛客暑期多校训练营8

难度梯度 KEA DJ GI FC BH

A Haitang and Game

题意

dXqwq 和 Haitang 在轮流进行一些操作。

有一个集合 \(S\)，中有 \(n\) 个数。

dXqwq 先手。

每次操作：选择一对 \((x,y)\) 满足 \(x,y\in S\) 和 \(\gcd(x,y)\notin S\)，然后把 \(\gcd(x,y)\) 插入到集合 \(S\) 中。

最先不能操作的人输掉比赛。

假如两个人都足够聪明，问谁赢得了比赛。

\(1\le n,x,y\le10^5\)

解题思路

可以发现，值域只有 \(10^5\)。

如果存在 \((x,y)\) 使 \(\gcd(x,y)=g\)，那么一定 \(x,y\) 一定是 \(g\) 的倍数，且 \(\gcd(\frac{x}{g},\frac{y}{g})=1\)。

也就是说所有包含因子 \(g\) 的数的 \(\gcd=1\)。

我们定义一个数组 \(vis\)，\(vis_i\) 表示 \(S\) 中存在 \(i\)。

我们从大到小枚举 \(\gcd=x\)，然后对 \(x\) 的倍数，进行 \(\gcd\)，如果最终结果等于 \(x\)，那么说明可以找到一对这样的数，\(\gcd=x\)。

计数，且标记 \(vis_x=true\) 即可。

如果数量为偶数，说明回合数为偶数，则 Haitang 获胜，否则 dXqwq 获胜。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int g[100005], vis[100005];
void solve() {
    for (int i = 1 ; i <= 100000 ; i++) {
        g[i] = 0;
        vis[i] = false;
    }
    auto work = [&](int x) {
        int b = 0;
        for (int i = 2 * x ; i <= 100000 ; i += x) {
            b = __gcd(b, g[i]);
        }
        return b;
    };
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        g[x] = x;
        vis[x] = true;
    }
    int ans = 0;
    for (int i = 100000 ; i >= 1 ; i--) {
        auto y = work(i);
        if (y == i) {
            if (!vis[i]) {
                ans++;
                g[i] = i;
                vis[i] = true;
            }
        }
    }
    cout << (ans & 1 ? "dXqwq" : "Haitang") << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D Haitang and Uma Musume

题意

类似于赛马娘游戏的一系列操作。

解题思路

模拟模拟。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int base[6][5][6] = {
    {{10, 0, 5, 0, 0, 2}, {0, 9, 0, 4, 0, 2}, {0, 5, 8, 0, 0, 2}, {4, 0, 4, 8, 0, 2}, {2, 0, 0, 0, 9, 4}},
    {{11, 0, 5, 0, 0, 2}, {0, 10, 0, 4, 0, 2}, {0, 5, 9, 0, 0, 2}, {4, 0, 4, 9, 0, 2}, {2, 0, 0, 0, 10, 4}},
    {{12, 0, 5, 0, 0, 2}, {0, 11, 0, 4, 0, 2}, {0, 6, 10, 0, 0, 2}, {4, 0, 4, 10, 0, 2}, {3, 0, 0, 0, 11, 4}},
    {{13, 0, 5, 0, 0, 2}, {0, 12, 0, 4, 0, 2}, {0, 6, 11, 0, 0, 2}, {4, 0, 4, 11, 0, 2}, {3, 0, 0, 0, 12, 4}},
    {{14, 0, 5, 0, 0, 2}, {0, 13, 0, 4, 0, 2}, {0, 7, 12, 0, 0, 2}, {5, 0, 5, 12, 0, 2}, {4, 0, 0, 0, 13, 4}}
};
array<int, 2> speed, sta, power, guts, wis;
array<int, 2> speed1[7], sta1[7], power1[7], guts1[7], wis1[7];
array<int, 7> frien, drive, train;
array<int, 2> arr[7];
struct Card {
    int friends, drive, train;
    int abilities_i[6];
} card[7];
int rlv[6], rcnt[6];
array<int, 6> abilities, rates;
int main() {
    for (int i = 0 ; i < 5 ; i++) {
        cin >> abilities[i];
    }
    abilities[5] = 120;
    for (int i = 0 ; i < 5 ; i++) {
        cin >> rates[i];
    }
    rates[5] = 0;
    for (int i = 1 ; i <= 6 ; i++) {
        cin >> card[i].friends >> card[i].drive >> card[i].train;
        for (int j = 0 ; j < 5 ; j++) {
            int x;
            cin >> x;
            abilities[j] += x;
        }
        for (int j = 0 ; j < 5 ; j++) {
            cin >> card[i].abilities_i[j];
        }
        card[i].abilities_i[5] = 0;
    }
    for (int i = 0 ; i < 5 ; i++) {
        abilities[i] = min(abilities[i], 1200);
    }
    int n;
    cin >> n;
    while (n--) {
        int summer, weight, drive, type, S;
        cin >> summer >> weight >> drive >> type >> S;
        vector<array<int, 2>> vec(S);
        for (auto &[x, y] : vec) {
            cin >> x >> y;
        }
        int lv = 4;
        if (summer != 1) {
            lv = rlv[type];
            if (rcnt[type]++ == 3) {
                rlv[type] = min(rlv[type] + 1, 4);
                rcnt[type] = 0;
            }
        }
        for (int i = 0 ; i < 6 ; i++) {
            if (weight == 1 && i == 0) continue;
            int strain = 0, sdrive = 0, sx = 0;
            __int128 friend_fz = 1, friend_fm = 1;
            for (auto &[x, y] : vec) {
                strain += card[x].train;
                sdrive += card[x].drive;
                sx += card[x].abilities_i[i];
                if (y == 1) {
                    friend_fz *= 100 + card[x].friends;
                    friend_fm *= 100;
                }
            }
            __int128 fz = (base[lv][type][i] + sx) * friend_fz * (100 + strain) * (10000 + (-20 + drive * 10) * (100 + sdrive)) * (100 + rates[i]) * (100 + 5 * S);;
            __int128 fm = friend_fm * 10000000000;
            abilities[i] += fz / fm;
            if (i < 5) {
                abilities[i] = min(abilities[i], 1200);
            }
        }
        for (int i = 0 ; i < 6 ; i++) {
            cout << abilities[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

E Haitang and Math

题意

给你一个数 \(n\)。

定义 \(S(n)\) 为数位和，比如 \(S(154)=1+5+4=10,S(147)=1+4+7\)。

现在问有多少个正整数 \(m\) 满足 \(m\le n\) 且 \(n\mod m=S(m)\)。

\(1\le n\le10^{12}\)。

解题思路

可以发现 \(n\) 最多有十二位数，所以 \(S(m)\) 最多为 \(108\)。

我们通过枚举 \(S(m)\)，然后把式子转换为 \((n-S(m))\mod m=0\)。

本质上这个式子 \(m\) 可能的取值是 \(n-S(m)\) 的因数。

对于每个 \(n\)，我们都只需要求区间 \([n-108,n-1]\) 的因数就好了。

使用区间筛将区间内的所有质数分别筛出来，在计算因数，最后枚举因数判断是否为答案即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
map<int, int> s;
int S(i64 x) {
    if (x >= 1000000) {
        return S(x / 1000000) + S(x % 1000000);
    }
    if (s.count(x)) {
        return s[x];
    }
    int res = 0;
    while (x) {
        res += x % 10;
        x /= 10;
    }
    return s[x] = res;
}
vector<int> prime;
void solve() {
    i64 n;
    cin >> n;
    i64 L = max<i64>(1, n - 108), R = n;
    vector<vector<array<i64, 2>>> p(R - L + 1);
    vector<i64> num(R - L + 1);
    iota(begin(num), end(num), L);
    for (auto &x : prime) {
        if (x > R) break;
        i64 z = L / x * x;
        if (z < L) z += x;
        while (z <= R) {
            int cnt = 0;
            while (num[z - L] % x == 0) {
                num[z - L] /= x;
                cnt++;
            }
            p[z - L].push_back({x, cnt});
            z += x;
        }
    }
    for (int i = 0 ; i < (int) num.size() ; i++) {
        if (num[i] > 1) {
            p[i].push_back({num[i], 1});
        }
    }
    set<i64> ans;
    for (int i = 0 ; i < (int) num.size() ; i++) {
        auto ps = p[i];
        int cnt = 1;
        for (auto &[p, t] : ps) {
            cnt *= t + 1;
        }
        vector<i64> res(cnt, 1);
        cnt = 1;
        for (auto &[p, t] : ps) {
            i64 pw = 1;
            for (int i = 1 ; i <= t ; i++) {
                pw *= p;
                for (int j = 0 ; j < cnt ; j++) {
                    res[cnt * i + j] = res[j] * pw;
                }
            }
            cnt *= t + 1;
        }
        for (auto &x : res) {
            if (n % x == S(x)) {
                ans.insert(x);
            }
        }
    }
    cout << ans.size() << "\n";
}
bool vis[1000005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2 ; i <= 1000000 ; i++) {
        if (vis[i]) continue;
        prime.push_back(i);
        for (int j = i ; j <= 1000000 ; j += i) {
            vis[j] = true;
        }
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G Haitang and Rock Paper Scissors

题意

有 \(n\) 个人和你玩石头剪刀布。

\(0\) 表示石头，\(1\) 表示布，\(2\) 表示剪刀。

现在给了你一个只包含 \(-1,0,1,2\) 的序列，表示每个人出拳的手势。

\(-1\) 表示 \(0,1,2\) 都有可能。

你不可以连续出相同的手势。

问你的出拳方案中，对于对方所有可能情况中最大得分的和。

\(1\le n\le2000\)

解题思路

首先考虑朴素dp，

定义 \(dp_{i,s1,s2,s3}\) 为前 \(i\) 个对手中，在第 \(i\) 个对手出石头/步/剪刀能得到的最大分数为 \(s1/s2/s3\) 的方案数。

那么我们最终的答案就是 \(\sum \max(s1,s2,s3)*dp_{n,s1,s2,s3}\)。

对于状态方程，当前为 \(i\)，然后前一个石头/布/剪刀能得到的最大分数为 \(s1/s2/s3\)。

对手出的石头，那么状态方程为 \(dp_{i,max(s2,s3),max(s1,s3)+1,-\infty}+=dp_{i-1,s1,s2,s3}\)。

对手出的布，那么状态方程为 \(dp_{i,-\infty,max(s1,s3),max(s1,s2)+1}+=dp_{i-1,s1,s2,s3}\)。

对手出的剪刀，那么状态方程为 \(dp_{i,max(s2,s3)+1,-\infty,max(s1,s2)}+=dp_{i-1,s1,s2,s3}\)。

当我们本轮出石头，那我们对前一轮的布和剪刀取 \(max\)，这样一定可以避免连续两轮出一样的手势。

这样的时间复杂度是 \(O(n^4)\) 的。

我们考虑如何优化，这里我们可以通过转移方程看到，一定有一维是 \(-\infty\)，那么我们可以用一个手势来代替这一维。

定义 \(dp_{i,s1,s2,k}\) 为前 \(i\) 个对手中，在第 \(i\) 个对手出 \((k+1)\%3/(k+2)\%3\) 能得到的最大分数为 \(s1/s2\) 的方案数。

那么答案还是同理 \(\sum\max(s1,s2)*dp_{n,s1,s2,k}\)。

对于状态方程，当前为 \(i\)，然后前一个 \((k+1)\%3/(k+2)\%3\) 能得到的最大分数为 \(s1/s2\)，

对手出的 \(j\)，那么我们需要考虑 \(j\) 和 \(k\) 的关系。

我们这一轮为 \(-\infty\) 的手势是 \((j+2)\%3\)，所以我们第四维一定是 \((j+2)\%3\)。

所以我们 \(dp_{i,?_1,?_2,(j+2)\%3}\) ， \(?_1\) 表示取\((j+1)\%3\) 和 \((j+2)\%3\) 得分的最大值，\(?_2\) 表示取 \(j\) 和 \((j+2)\%3\) 得分的最大值 \(+1\)。

定义 \(g=(j-k+3)\%3\)。

对于第 \(i-1\) 轮，\((k+1)\%3\) 的最大得分为 \(s1\)，\((k+2)\%3\) 的最大得分为 \(s2\)。

当 \(g=0\) 时，

此时 \(j=k\)。
\(?_1\) 表示取 \((k+1)\%3\) 和 \((k+2)\%3\) 得分的最大值，这里为 \(\max(s1,s2)\)。
\(?_2\) 表示取 \(k\) 和 \((k+2)\%3\) 得分的最大值 \(+1\)，这里为 \(s2+1\)，因为 \(k\) 是 \(-\infty\)。
所以状态转移方程为 \(dp_{i,max(s1,s2),s2+1,(j+2)\%3}+=dp_{i-1,s1,s2,k}\)。

当 \(g=1\) 时，

此时 \(j=(k+1)\%3\)。
\(?_1\) 表示取 \((k+2)\%3\) 和 \(k\) 得分的最大值，这里为 \(s2\)，因为 \(k\) 是 \(-\infty\)。
\(?_2\) 表示取 \((k+1)\%3\) 和 \(k\) 得分的最大值 \(+1\)，这里为 \(s1+1\)，因为 \(k\) 是 \(-\infty\)。
所以状态转移方程为 \(dp_{i,s2,s1+1,(j+2)\%3}+=dp_{i-1,s1,s2,k}\) 。

当 \(g=2\) 时，

此时 \(j=(k+2)\%3\)。
\(?_1\) 表示取 \(k\) 和 \((k+1)\%3\) 得分的最大值，这里为 \(s1\)，因为 \(k\) 是 \(-\infty\)。
\(?_2\) 表示取 \((k+2)\%3\) 和 \((k+1)\%3\) 得分的最大值 \(+1\)，这里为 \(max(s1,s2)+1\)。
所以状态转移方程为 \(dp_{i,s1,max(s1,s2)+1,(j+2)\%3}+=dp_{i-1,s1,s2,k}\)。

到这里时间复杂度优化为 \(O(n^3)\)。

我们还需要优化时间复杂度。

这里我们可以想到我们无论如何都不可能失败，总可以做到要么赢，要么平局。

那么从这一点，我们的 \(max(s1,s2)\) 是一定不会减少的。

所以一但 \(max(s1,s2)\) 增加，我们之后的所有方案都不会减少了，而且一但增加，只会增加 \(1\)，

那么从这一步开始有多少方案，我们就贡献了 \(1\) 乘上方案个数。

对于某一段的方案数，假设这一段的 \(-1\) 的数量为 \(cnt\)，那么这一段的方案数为 \(3^{cnt}\)。

所以我们需要维护一个 \(-1\) 数量的前缀和。

定义 \(cnt_i\) 表示第 \(1\) 个到第 \(i\) 个之间有多少个 \(-1\)。

既然只需要 \(max(s1,s2)\)，我们可以直接维护 \(s2-s1\)，这样 \(max(s1,s2)\) 也可以同时维护。

定义 \(dp_{i,s,k}\) 为前 \(i\) 个对手中，在第 \(i\) 个对手出 \((k+2)\%3\) 能得到的最大分数减去 \((k+1)\%3\) 能得到的最大分数为 \(s\) 的方案数。

对手出的 \(j\)，我们还是要考虑 \(j\) 和 \(k\) 的关系。

我们这一轮为 \(-\infty\) 的手势是 \((j+2)\%3\)，所以我们第三维一定是 \((j+2)\%3\)。

所以我们 \(dp_{i,?_2-?_1,(j+2)\%3}\) ， \(?_1\) 表示取\((j+1)\%3\) 和 \((j+2)\%3\) 得分的最大值，\(?_2\) 表示取 \(j\) 和 \((j+2)\%3\) 得分的最大值 \(+1\)。

定义 \(g=(j-k+3)\%3\)。

对于第 \(i-1\) 轮，\((k+1)\%3\) 的最大得分为 \(s1\)，\((k+2)\%3\) 的最大得分为 \(s2\)，\(s2-s1=s\)。

当 \(g=0\) 时，

此时 \(j=k\)。
\(?_1\) 表示取 \((k+1)\%3\) 和 \((k+2)\%3\) 得分的最大值，这里为 \(\max(s1,s2)\)。
\(?_2\) 表示取 \(k\) 和 \((k+2)\%3\) 得分的最大值 \(+1\)，这里为 \(s2+1\)，因为 \(k\) 是 \(-\infty\)。
那么 \(?_2-?_1=s2+1-\max(s1,s2)\)，
这个式子我们可以轻易的看出当 \(s\ge0\) 即 \(s_2\ge s1\)，得到 \(?_2-?_1=1\)。
否则得到 \(?_2-?_1=s2-s1+1=s+1\)。
所以状态转移方程为
\(\begin{align} dp_{i,1,(j+2)\%3}+=dp_{i-1,s,k}&&s\ge0\\ dp_{i,s+1,(j+2)\%3}+=dp_{i-1,s,k}&&else \end{align}\)
然后 \(\max(?_1,?_2)=\max(\max(s1,s2),s2+1)\)，
此时当 \(s2+1> s1\) 最大值才会变化，也就是说 \(s2-s1>-1\)，
这个式子等价于 \(s\ge0\)。
所以当 \(s\ge0\) 的时候，我们对答案的贡献为 \(dp_{i-1,s,k}*3^{cnt_n-cnt_i}\)。

当 \(g=1\) 时，

此时 \(j=(k+1)\%3\)。
\(?_1\) 表示取 \((k+2)\%3\) 和 \(k\) 得分的最大值，这里为 \(s2\)，因为 \(k\) 是 \(-\infty\)。
\(?_2\) 表示取 \((k+1)\%3\) 和 \(k\) 得分的最大值 \(+1\)，这里为 \(s1+1\)，因为 \(k\) 是 \(-\infty\)。
那么 \(?_2-?_1=s1+1-s2=1-s\)，
所以状态转移方程为
\(dp_{i,1-s,(j+2)\%3}+=dp_{i-1,s,k}\)
然后 \(\max(?_1,?_2)=\max(s2,s1+1)\)
此时只有 \(s1+1>s2\) 最大值才会变化，也就是说 \(s2-s1<1\)，
这个式子等价于 \(s\le0\)。
所以当 \(s\le0\) 的时候，我们对答案的贡献为 \(dp_{i,s,k}*3^{cnt_n-cnt_i}\)。

当 \(g=2\) 时，

此时 \(j=(k+2)\%3\)。
\(?_1\) 表示取 \(k\) 和 \((k+1)\%3\) 得分的最大值，这里为 \(s1\)，因为 \(k\) 是 \(-\infty\)。
\(?_2\) 表示取 \((k+2)\%3\) 和 \((k+1)\%3\) 得分的最大值 \(+1\)，这里为 \(max(s1,s2)+1\)。
那么 \(?_2-?_1=max(s1,s2)+1-s1\)，
此时当 \(s\ge0\) 即 \(s2\ge s1\)，得到 \(?_2-?_1=s2+1-s1=s+1\)，
否则得到 \(?_2-?-1=1\)。
所以状态转移方程为
\(\begin{align} dp_{i,s+1,(j+2)\%3}+=dp_{i-1,s,k}&&s\ge0\\ dp_{i,1,(j+2)\%3}+=dp_{i-1,s,k}&&else \end{align}\)
然后 \(\max(?_1,?_2)=\max(s1,max(s1,s2)+1)\)，
此时无论何时都会发现 \(\max\) 都会变大，
这个时候直接对答案贡献为 \(dp_{i,s,k}*3^{cnt_n-cnt_i}\) 。

最终时间复杂度为 \(O(n^2)\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const i64 P = 998244353;
// 石头 布 剪刀
int dp[2005][5005][3];
const int M = 2500;
int a[2005];
int cnt[2005];
i64 p3[2005];
int main() {
    int n;
    cin >> n;
    p3[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        if (a[i] == -1) {
            cnt[i]++;
        }
        cnt[i] += cnt[i - 1];
        p3[i] = p3[i - 1] * 3 % P;
    }
    dp[0][M][0] = 1;
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j <= 2 ; j++) {
            if (a[i] == -1 || a[i] == j) {
                for (int k = 0 ; k <= 2 ; k++) {
                    for (int ss = -i - 2 ; ss <= i + 2 ; ss++) {
                        int g = (j - k + 3) % 3;
                        if (g == 0) {
                            if (ss >= 0) {
                                dp[i][M + 1][(j + 2) % 3] = (dp[i][M + 1][(j + 2) % 3] + dp[i - 1][ss + M][k]) % P;
                                ans = (ans + dp[i - 1][ss + M][k] * p3[cnt[n] - cnt[i]]) % P;
                            } else {
                                dp[i][ss + M + 1][(j + 2) % 3] = (dp[i][ss + M + 1][(j + 2) % 3] + dp[i - 1][ss + M][k]) % P;
                            }
                        }
                        if (g == 1) {
                            if (ss <= 0) {
                                ans = (ans + dp[i - 1][ss + M][k] * p3[cnt[n] - cnt[i]]) % P;
                            }
                            dp[i][M - ss + 1][(j + 2) % 3] = (dp[i][M - ss + 1][(j + 2) % 3] + dp[i - 1][ss + M][k]) % P;
                        }
                        if (g == 2) {
                            ans = (ans + dp[i - 1][ss + M][k] * p3[cnt[n] - cnt[i]]) % P;
                            if (ss >= 0) {
                                dp[i][ss + M + 1][(j + 2) % 3] = (dp[i][ss + M + 1][(j + 2) % 3] + dp[i - 1][ss + M][k]) % P;
                            } else {
                                dp[i][M + 1][(j + 2) % 3] = (dp[i][M + 1][(j + 2) % 3] + dp[i - 1][ss + M][k]) % P;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

J Haitang and Triangle

题意

给你一个 \(n\) 排列，你可以随便交换位置。

问是否存在一种排列使得相邻的三个数恰好能构成 \(m\) 个三角形。

\(0\le m\le n-2\)

解题思路

首先，我们先想想 \(m=0\) 是如何构造的。

肯定是三个三个成等差，形式为 \(x,x+d,x+2d\)。

我们发现当 \(d=\frac{n}{3}\) 时， \(d,2d,3d,d-1,2d-1,3d-1,…,1,1+d,1+2d\) 刚好符合。

那么我们想想 \(m>0\) 的如何构造。

我们可以先用 \(n-m\) 个数构造 \(0\) 个三角形，然后剩余 \(m\) 个数，按顺序放在右边即可。

最右边两个是 \(1+d\) 和 \(1+2d\)，剩余的最小的数是 \(3d+1\)，所以剩余的 \(m\) 个数每个数都可以构成一个三角形。

这种情况只在 \((n-m)\mod 3=0\) 合法。

如果 \((n-m)\mod 3=1\) ，那么我们还有 \(n\) 这个数没有放，我们可以把 \(n\) 放在第一个，因为 \(d+2d<n\) 的，所以没有构造出三角形。

如果 \((n-m)\mod 3=2\)，那么我们会多两个数，我们可以把 \(2+3d\) 放在右边的第一个，然后把 \(1+3d\) 放在第一个，这样能保证这两个数没有构造出三角形。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
void solve() {
    int n, m;
    cin >> n >> m;
    if (m == n - 2) {
        cout << -1 << "\n";
        return;
    }
    int x = n - m;
    int d = x / 3;
    vector<int> ans;
    if (x % 3 == 0) {
        for (int i = 0 ; i < d ; i++) {
            ans.push_back(d - i);
            ans.push_back(2 * d - i);
            ans.push_back(3 * d - i);
        }
        for (int i = 1 ; i <= m ; i++) {
            ans.push_back(3 * d + i);
        }
    }
    if (x % 3 == 1) {
        ans.push_back(n);
        for (int i = 0 ; i < d ; i++) {
            ans.push_back(d - i);
            ans.push_back(2 * d - i);
            ans.push_back(3 * d - i);
        }
        for (int i = 1 ; i <= m ; i++) {
            ans.push_back(3 * d + i);
        }
    }
    if (x % 3 == 2) {
        ans.push_back(3 * d + 1);
        for (int i = 0 ; i < d ; i++) {
            ans.push_back(d - i);
            ans.push_back(2 * d - i);
            ans.push_back(3 * d - i);
        }
        ans.push_back(3 * d + 2);
        for (int i = 3 ; i <= m + 2 ; i++) {
            ans.push_back(3 * d + i);
        }
    }
    for (auto &x : ans) {
        cout << x << " ";
    }
    cout << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

K Haitang and Ava

题意

给你一个串 \(S\)，请你判断这个串是否是合法的。

合法的条件如下：

① 空串是合法的。

② 如果 \(S\) 是合法的串，那么 \(S+ava\) 和 \(ava+S\) 均是合法的串。

② 如果 \(S\) 是合法的串，那么 \(S+avava\) 和 \(avava+S\) 均是合法的串。

解题思路

可以发现 \(avava\) 肯定优于 \(ava\) 判断。

所以我们遍历一遍，判断是否每一段都是 \(avava\) 或 \(ava\) 即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<char> st;
void solve() {
    string str;
    cin >> str;
    int n = str.size();
    int L = 0;
    while (L < n) {
        if (str.substr(L, 5) == "avava") {
            L += 5;
            continue;
        }
        if (str.substr(L, 3) == "ava") {
            L += 3;
            continue;
        }
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}