• 欢迎光临~

2022牛客暑期多校训练营6 个人题解

开发技术 开发技术 2022-08-06 次浏览

(A):Array

思路

构造题,可以考虑寻找小于等于每个数的最大的2的次幂作为该数的周期。将最大的周期定为 (m) 。然后从小到大排序,依次将每个下标按周期填入。剩余的空白位置可以随意填一些1到n的数。

code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e6 + 10;
const int M = 2e5 + 10;

ll n, m, a[N];
struct node {
    ll t; int x;
    bool operator<(const node &b) const {
        return t < b.t;
    }
}f[M];

void slove() {
    cin >> n;
    m = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x; a[i] = x;
        ll cnt = 0, base = 2;
        while (base <= x) {
            cnt++; base <<= 1;
        }
        f[i].t = (1 << cnt);
        if (f[i].t > m) m = f[i].t;
        f[i].x = i;
    } 
    sort(f + 1, f + 1 + n);
    m = f[n].t;
    cout << m << endl;
    vector<int>ans(m, 0);
    for (int i = 1, st = 0; i <= n; i++) {
        while (st < m && ans[st]) st++;
        assert(st != m);
        int l = f[i].t;
        for (int j = st; j < m; j += l) ans[j] = f[i].x;
    }
    for (int i = 0; i < m; i++) {
        if (ans[i] == 0) ans[i] = 1;
    }
    for (int i = 0; i < m; i++) cout << ans[i] << " n"[i == m - 1];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    slove();
    return (0^0);
}

(B):Eezie and Pie

队友写的,还没看(

(G): Icon Design

思路

傻逼模拟题,就是按照要求画出对应长度的logo,暴力for循环

代码

#include <bits/stdc++.h>
using namespace std;
int n;
void slove() {
    cin >> n;
    for (int i = 1; i <= 13 * n + 19; i++) cout << '*'; cout << endl;
    for (int j = 1; j <= n; j++) {
        cout << '*';
        for (int i = 2; i < 13 * n + 19; i++) cout << '.';
        cout << "*n";
    }
    for (int j = 1; j <= 2 * n + 3; j++) {
        cout << '*';
        for (int i = 1; i <= n + 1; i++) cout << '.';
        cout << '@';
        for (int i = 2; i <= 2 * n + 2; i++) {
            if (i == j) cout << '@'; else cout << '.';
        }
        cout << '@';
        for (int i = 1; i <= n + 1; i++) cout << '.';
        cout << '@';
        if (j == 1 || j == n + 2)
            for (int i = 1; i <= 2 * n + 2; i++) cout << '@';
        else 
            for (int i = 1; i <= 2 * n + 2; i++) cout << '.';
        for (int i = 1; i <= n + 1; i++) cout << '.';
        cout << '@';
        if (j == 2 * n + 3)
            for (int i = 1; i <= 2 * n + 2; i++) cout << '@';
        else 
            for (int i = 1; i <= 2 * n + 2; i++) cout << '.';
        for (int i = 1; i <= n + 1; i++) cout << '.';
        if (j == 1 || j == n + 2 || j == 2 * n + 3) {
            for (int i = 1; i <= 2 * n + 3; i++) cout << '@';
        } else if (j <= n + 1) {
            cout << '@';
            for (int i = 1; i <= 2 * n + 2; i++) cout << '.';
        } else {
            for (int i = 1; i <= 2 * n + 2; i++) cout << '.';
            cout << '@';
        }
        for (int i = 1; i <= n + 1; i++) cout << '.';
        cout << "*n";
    }
    for (int j = 1; j <= n; j++) {
        cout << '*';
        for (int i = 2; i < 13 * n + 19; i++) cout << '.';
        cout << "*n";
    }
    for (int i = 1; i <= 13 * n + 19; i++) cout << '*'; cout << endl;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    slove();
    return 0;
}

(I):Line

待补。。。

(J):Number Game

思路

推柿子。首先判断 x == c 是否成立。如果不成立,则需要考虑前面的因素。
可以发现存在两种情况。
一是先执行 B-C 再执行 A-B,然后进行循环。可以得到两个方程通式。

[(2n - 1)B - (n - 1)A - C = x\ nA - 2nB + C = x ]

二是先执行 A-B 再执行 B-C,然后进行循环。可以得到两个方程通式。

[nA - (2n - 1)B - C = x\ 2nB - nA + C = x ]

分别判断以上这四种情况下 (n) 的值是否为大于零的整数,如果不是则无法构成相关的 (x)

code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slove() {
    ll a, b, c, t;
    cin >> a >> b >> c >> t;
    if (t == c) return cout << "Yesn", void();
    ll x[4], y[4];
    x[0] = b * 2 - a; x[1] = -x[0]; x[2] = x[0]; x[3] = -x[0];
    y[0] = t - a + b + c;  y[1] = t - c; y[2] = t - c; y[3] = t - b + c;
    for (int i = 0; i < 4; i++) {
        if (x[i] == 0) { // x[i] = 0的情况要特判
            if (y[i] == 0)
                return cout << "Yesn", void();
            else continue;
        }
        if (y[i] % x[i] == 0) {
            ll k = y[i] / x[i];
            if (k >= 1) return cout << "Yesn", void();
        }
    }
    cout << "Non";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int _; cin >> _;
    while (_--) {
        slove();
    }
    return (0^0);
}

(M):Z-Game on grid

思路

考虑从后往前dp, (dp_{i, j, 0/1/2}) 分别为到达 ((i, j)) 点时是否一定会赢,平局或输这三种情况,当 (dp_{i, j, 0/1/2} = 1) 则可以,否则不行。状态转移的时候分别考虑Alice和Bob的选择,如果Alice希望最终达到赢的情况,则Bob始终希望往相反的方向考虑。则有状态转移方程如下

[dp_{i, j, k} = begin{cases} dp_{i + 1, j, k} | dp_{i, j + 1, k}, & text{if }i + jtext{ is even} \ dp_{i + 1, j, k} & dp_{i, j + 1, k}, & text{if }i + jtext{ is odd} end{cases} ]

需要特殊注意边界条件。

code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 510;
int n, m;
string s[N];
int dp[N][N][3];

inline void print(int x) {
    if (x == 1) cout << "yes ";
    else cout << "no ";
}
void slove() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k < 3; k++) dp[i][j][k] = 0;
    char c = s[n - 1][m - 1];
    if (c == 'A') dp[n - 1][m - 1][0] = 1;
    if (c == '.') dp[n - 1][m - 1][1] = 1;
    if (c == 'B') dp[n - 1][m - 1][2] = 1;
    for (int i = n - 1; i >= 0; i--) 
        for (int j = m - 1; j >= 0; j--) {
            if (i == n - 1 and j == m - 1) continue;
            if (s[i][j] == 'A') dp[i][j][0] = 1;
            else if (s[i][j] == 'B') dp[i][j][2] = 1;
            else {
                if (i == n - 1) 
                    for (int k = 0; k < 3; k++) 
                        dp[i][j][k] = dp[i][j + 1][k];
                else if (j == m - 1) 
                    for (int k = 0; k < 3; k++) 
                        dp[i][j][k] = dp[i + 1][j][k];
                else 
                    for (int k = 0; k < 3; k++) 
                        if ((i + j) % 2 == 0) 
                            dp[i][j][k] = (dp[i + 1][j][k] | dp[i][j + 1][k]);
                        else 
                            dp[i][j][k] = (dp[i + 1][j][k] & dp[i][j + 1][k]);
            }
        }
    for (int k = 0; k < 3; k++) print(dp[0][0][k]);
    cout << 'n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int _; cin >> _;
    while (_--) {
        slove();
    }
    return (0^0);
}
程序员灯塔
转载请注明原文链接:2022牛客暑期多校训练营6 个人题解
喜欢 (0)