【持续更新】2024牛客寒假算法基础集训营3 题解 | JorbanS

A - 智乃与瞩目狸猫、幸运水母、月宫龙虾

string solve() {string a, b; cin >> a >> b;if (isupper(a[0])) a[0] += 'a' - 'A';if (isupper(b[0])) b[0] += 'a' - 'A';return a[0] == b[0] ? yes : no;
}

B - 智乃的数字手串

string solve() {cin >> n;int cnt = 0;for (int i = 1; i <= n; i ++) cin >> a[i], a[i] &= 1, cnt += a[i];if (n == 1) return yes;if (!cnt || n == cnt) return (n & 1) ? yes : no;a[0] = a[n];cnt = 0;for (int i = 1; i <= n; i ++)if (a[i] + a[i - 1] & 1 ^ 1) cnt ++;return (cnt & 1) ? yes : no;
}

D - chino’s bubble sort and maximum subarray sum(easy version)

int a[N], b[N];
string s;ll cal() {ll res = 0, t = 0;for (int i = 0; i < n; i ++) {if (b[i] >= 0) t += b[i];else {res = max(t, res);t = max(0ll, t + b[i]);}}res = max(t, res);return res;
}ll solve() {cin >> n >> m;int c1 = -2e9;for (int i = 0; i < n; i ++) {cin >> a[i], b[i] = a[i];c1 = max(c1, a[i]);}if (c1 <= 0) return c1;ll res = -1e18;if (m)for (int i = 1; i < n; i ++) {swap(b[i], b[i - 1]);res = max(res, cal());swap(b[i], b[i - 1]);}else res = cal();return res;
}

G - 智乃的比较函数(easy version)

string solve() {cin >> n;int x, y, z, x1, y1, z1;if (n == 1) {cin >> x >> y >> z;if (x == y && z) return no;return yes;}cin >> x >> y >> z;cin >> x1 >> y1 >> z1;if (x == x1 && y == y1 && z != z1) return no;if (x == y && z) return no;if (x1 == y1 && z1) return no;if (x == y1 && y == x1 && (z == z1 && z)) return no;return yes;
}

H - 智乃的比较函数(normal version)

int a[4][4][2];string solve() {cin >> n;for (int i = 1; i <= 3; i ++)for (int j = 1; j <= 3; j ++)for (int k = 0; k < 2; k ++) a[i][j][k] = 0;for (int i = 0; i < n; i ++) {int x, y, z; cin >> x >> y >> z;a[x][y][z] = 1;}for (int i = 1; i <= 3; i ++)if (a[i][i][1]) return no;for (int i = 1; i <= 3; i ++)for (int j = 1; j <= 3; j ++)if (a[i][j][1] && a[i][j][0]) return no;for (int i = 1; i <= 3; i ++)for (int j = i + 1; j <= 3; j ++)if (a[i][j][1] && a[j][i][1]) return no;int b[3] = {1, 2, 3};do {int x = b[0], y = b[1], z = b[2];if (a[x][y][1] && a[y][z][1] && a[z][x][1]) return no;if (a[x][y][1] && a[y][z][1] && a[x][z][0]) return no;if (a[x][y][0] && a[y][z][0] && a[x][z][1]) return no;} while (next_permutation(b, b + 3));return yes;
}

J - 智乃的相亲活动

void solve() {cin >> n >> m >> k;vector<int> a[n + 1], b[m + 1];while (k --) {int u, v; cin >> u >> v;a[u].push_back(v), b[v].push_back(u);}double na = 0, nb = 0;for (int i = 1; i <= n; i ++) {double t = 1;for (auto j : a[i]) t *= (1 - 1.0 / b[j].size());na += 1 - t;}for (int i = 1; i <= m; i ++) {double t = 1;for (auto j : b[i]) t *= (1 - 1.0 / a[j].size());nb += 1 - t;}printf("%.8lf %.8lf\n", na, nb);
}

K - 智乃的“黑红树”

int n, a, b;
int l[N], r[N];void solve() {cin >> a >> b;if (a & 1 ^ 1 || b & 1 || !a) {cout << no << endl;return;}n = a + b;for (int i = 1; i <= n; i ++) l[i] = r[i] = -1;vector<int> A, B;A.push_back(1);int idx = 1;a --;while ((A.size() && b || B.size() && a) {while (A.size() && b) {l[A[0]] = ++ idx;B.push_back(idx);r[A[0]] = ++ idx;B.push_back(idx);A.erase(A.begin());b -= 2;}while (B.size() && a) {l[B[0]] = ++ idx;A.push_back(idx);r[B[0]] = ++ idx;A.push_back(idx);B.erase(B.begin());a -= 2;}}if (a || b) {cout << no << endl;return;}cout << yes << endl;for (int i = 1; i <= n; i ++) cout << l[i] << ' ' << r[i] << endl;
}

L - 智乃的36倍数(easy version)

int solve() {cin >> n;for (int i = 0; i < n; i ++) cin >> a[i];int res = 0;for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {if (i == j) continue;if ((a[i] * (int)pow(10, to_string(a[j]).size()) + a[j]) % 36 == 0) res ++;}}return res;
}

M - 智乃的36倍数(normal version)

ll solve() {cin >> n;for (int i = 0; i < n; i ++) cin >> a[i];for (int i = 0; i < n; i ++) cnt[a[i] % 36] ++;ll res = 0;for (int i = 0; i < n; i ++) {int x = a[i] % 36;int len = to_string(a[i]).size();for (int j = 0; j < 36; j ++) {int t = j;for (int k = 0; k < len; k ++) (t *= 10) %= 36;if ((t + x) % 36 == 0) res += max(cnt[j] - (j == x), 0ll);}}return res;
}