【更新完毕】2024牛客寒假算法基础集训营6 题解 | JorbanS

暴力枚举三个数即可

int p[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};bool check(int x) {for (int i = 0; i < 9; i ++)for (int j = i + 1; j < 9; j ++)for (int k = j + 1; k < 9; k ++)if (p[i] * p[j] * p[k] == x) return true;return false;
}int solve() {int l, r; cin >> l >> r;for (int i = l; i <= r; i ++)if (check(i)) return i;return -1;
}

找到一对数 $(a_i,b_j)$ 使其差最小，对于每一个 $b_i$，二分查找其大于等于和小于它的第一个 $a_i$，最后输出保证 $a_i$ 在 $b_j$ 所在位置

void solve() {cin >> n;map<int, int> mp;for (int i = 0; i < n; i ++) cin >> a[i];for (int i = 0; i < n; i ++) cin >> b[i];sort(a, a + n);int pos = -1, Min = 1e9, num;for (int i = 0; i < n; i ++) {int t = lower_bound(a, a + n, b[i]) - a;if (abs(b[i] - a[t]) < Min) {Min = abs(b[i] - a[t]);pos = i;num = t;}if (t && abs(b[i] - a[t - 1]) < Min) {Min = abs(b[i] - a[t - 1]);pos = i;num = t - 1;}}vector<int> c;for (int i = 0; i < n; i ++)if (i != num) c.emplace_back(a[i]);for (int i = 0; i <= pos - 1; i ++) cout << c[i] << ' ';cout << a[num] << ' ';for (int i = pos; i < n - 1; i ++) cout << c[i] << ' ';cout << endl;
}

先求出 $0\sim 10^9$ 的斐波那契数列

法一：预处理出所有三个斐波那契数可能形成的数

int f[N];
map<int, int> p;void solve() {cin >> n;int t = p[n];if (t) {cout << a[t] << ' ' << b[t] << ' ' << c[t] << endl;} else cout << -1 << endl;
}signed main() {FastIOf[0] = 0, f[1] = 1;for (int i = 2; i <= 44; i ++) f[i] = f[i - 1] + f[i - 2];int idx = 0;for (int i = 0; i <= 44; i ++)for (int j = 0; j <= 44; j ++)for (int k = 0; k <= 44; k ++) {p[f[i] + f[j] + f[k]] = ++ idx;a[idx] = f[i];b[idx] = f[j];c[idx] = f[k];}Casessolve();return 0;
}

法二：由于每个数都可由至少另外两个数表示，所以贪心的，每次减去尽可能大的值

三次二分，每次减去二分出来的值

双方均有可能让二追三

void solve() {double res = 0, p; cin >> p;res += p * p * p * (1 - p) * (1 - p);res += p * p * (1 - p) * (1 - p) * (1 - p);printf("%.8lf\n", res);
}

模拟一下

void solve() {getchar();getchar();cin >> m >> s;n = s.size();int r = 0, p = 0;for (int i = 1; i <= n; i ++) {if (s[i - 1] == 'R') r ++;else p ++;if (r > m >> 1) {cout << R << endl << i << endl;return;}if (p > m >> 1) {cout << P << endl << i << endl;return;}}cout << "to be continued." << endl << n << endl;
}

先预处理每个数的全部质因数（$1$ 特殊处理）

并查集维护每个数是否需要处于同一组

int n, m, k;
int a[N], b[N], p[N];
vector<vector<int>> e(N);int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }void solve() {cin >> n;for (int i = 1; i <= n; i ++) p[i] = i;vector<int> q;for (int i = 1; i <= n; i ++) {cin >> a[i];for (auto j : e[a[i]])if (!b[j]) b[j] = i, q.emplace_back(j);else p[find(i)] = find(b[j]);}for (auto i : q) b[i] = 0;int cnt = 0;for (int i = 2; i <= n; i ++) cnt += find(1) != find(i);if (!cnt) {cout << "-1 -1" << endl;return;}cout << n - cnt << ' ' << cnt << endl;for (int i = 1; i <= n; i ++) if (p[1] == p[i]) cout << a[i] << ' ';cout << endl;for (int i = 1; i <= n; i ++) if (p[1] != p[i]) cout << a[i] << ' ';cout << endl;
}signed main() {FastIOe[1].emplace_back(1);for (int i = 2; i <= 1e6; i ++)if (e[i].empty())for (int j = i; j <= 1e6; j += i)e[j].emplace_back(i);Casessolve();return 0;
}

先特判当 $2k+1>n$ 时必然不成立

贪心地，让 $212$ 作为三元组，则当 $k\ne 0$ 时若 $m<n+k+1$ 时必然不成立

若 $k=0$，让除了第一个位置的所有数填 $1$，第一个位置填剩余的数即可

当 $k>0$ 时，

构造 $xyx$，使得 $x$ 尽可能大，剩下的先全部放 $1$，设剩下的为 $m,m<k+1$

若正好铺满，即 $2k+1=n$ 时，若 $x=y+1$，则不成立，否则将 $m$ 个谷位置 $+1$

若未正好铺满，则让 $a[2k+1]:=m$

void solve() {cin >> n >> m >> k;if (k * 2 + 1 > n || k && m < n + k + 1) {cout << -1 << endl;return;}for (int i = 0; i < n; i ++) a[i] = 1, m --;if (k) {for (int i = 0; i <= k << 1; i += 2) a[i] += m / (k + 1);m %= k + 1;if (k * 2 + 1 == n) {if (a[0] == a[1] + 1 && m) {cout << -1 << endl;return;}for (int i = 1; i <= m * 2 - 1; i += 2) a[i] ++;} else a[k * 2 + 1] += m;} else a[0] += m;for (int i = 0; i < n; i ++) cout << a[i] << " \n"[i == n - 1];
}

${\sum }_{i=1}^n{\sum }_{j=1}^m{a}_i\times b_j={\sum }_{i=1}^n{a}_i\times {\sum }_{j=1}^m{b}_j$

转化为 $a,b$ 连续子序列和的最大乘积

ll cal() {ll t = 0, A = -1e18, B = -1e18;for (int i = 0; i < n; i ++) {if (a[i] >= -t) t += a[i];else t = 0;A = max(A, t);}t = 0;for (int i = 0; i < m; i ++) {if (b[i] >= -t) t += b[i];else t = 0;B = max(B, t);}return A * B;
}ll solve() {cin >> n >> m;int MaxA = -1e9, MaxB = -1e9;int MinA = 1e9, MinB = 1e9;for (int i = 0; i < n; i ++) {cin >> a[i];MaxA = max(MaxA, a[i]);MinA = min(MinA, a[i]);}for (int i = 0; i < m; i ++) {cin >> b[i];MaxB = max(MaxB, b[i]);MinB = min(MinB, b[i]);}ll res = max(MaxA * MinB, MinA * MaxB);if (MinA >= 0 && MaxB <= 0 || MaxA <= 0 && MinB >= 0) return res;res = max(res, cal());for (int i = 0; i < n; i ++) a[i] *= -1;for (int i = 0; i < m; i ++) b[i] *= -1;res = max(res, cal());return res;
}

因为对于红节点的子树和已为 $3$ 的倍数，则对于某一个红节点来说，无需考虑该红节点子树中的子红节点子树，将未涂色的节点和该红节点构造和为 $3$ 的倍数即可

int n, f[N], a[N];
string s;
vector<vector<int>> e(N), E(N);
vector<int> R;void dfs(int u = 1, int fa = 0) {if (s[u] == 'W') f[u] = f[fa];for (auto v : e[u]) if (v != fa) dfs(v, u);
}void solve() {cin >> n >> s;s = " " + s;for (int i = 2; i <= n; i ++) {int x; cin >> x;e[x].emplace_back(i);}for (int i = 1; i <= n; i ++) f[i] = i, a[i] = 1;dfs();for (int i = 1; i <= n; i ++) {if (f[i] == i) R.emplace_back(i);E[f[i]].emplace_back(i);}for (auto u : R) {if (E[u].size() == 1) {cout << -1 << endl;return;}if (E[u].size() & 1) {for (int i = 0; i < 3; i ++) a[E[u][i]] = 1;for (int i = 3; i < E[u].size(); i ++) a[E[u][i]] = (i & 1) + 1;} else {for (int i = 0; i < E[u].size(); i ++) a[E[u][i]] = (i & 1) + 1;}}for (int i = 1; i <= n; i ++) cout << a[i];cout << endl;
}