• 欢迎光临~

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

### (A):Array

#### 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);
}
``````

### (G): Icon Design

#### 代码

``````#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;
}
``````

### (J):Number Game

#### 思路

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

[nA - (2n - 1)B - C = x\ 2nB - nA + C = 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_{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);
}
``````