蓝桥杯 第三场 小白入门赛

召唤神坤

• 有意思🤔（ikun）。
• 虽然是第一题但也要配得上神坤的身份。

思路1

• 枚举分母，选择一个数据结构来选出分母两侧最大的两个数做分子。
• 2s常数大些也无碍。
• 我选择好写的ST表

思路2

• 写两个 $dp$ 分别表示 $1$ 到 $i$ 的最大值，$i$ 到 $n$ 的最大值。再枚举。
• 这个不放码了看的别人的思路。

signed main() {int T = 1;
//    T = read();while (T--) {int n = read();vector<int> a(n + 1), logn(n + 1);vector<vector<int>> f(n + 1, vector<int>(30));for (int i = 1; i <= n; ++i) f[i][0] = a[i] = read();logn[0] = -1;for (int i = 1; i <= n; ++i) logn[i] = logn[i >> 1] + 1;for (int j = 1; j <= logn[n]; ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}int ans = 0;for (int i = 2; i < n; ++i) {int l = 1, r = i - 1, s = logn[r - l + 1];int wi = max(f[l][s], f[r - (1 << s) + 1][s]);l = i + 1, r = n, s = logn[r - l + 1];int wk = max(f[l][s], f[r - (1 << s) + 1][s]);ans = max(ans, (wi + wk) / a[i]);}write(ans);}return 0;
}

聪明的交换策略

分析

• 依据题意就是要么 $0$ 左 $1$ 右，要么 $1$ 左 $0$ 右。
• 考虑 $0$ 左还是 $0$ 右即可。考虑 $1$ 也行一样的。

signed main() {int T = 1;
//    T = read();while (T--) {int n = read();string s; cin >> s;vector<int> pos;for (int i = 0; i < s.size(); ++i) {if (s[i] ^ '1') pos.push_back(i);}int ans = 1e17, tmp1 = 0, tmp2 = 0;for (int i = 0; i < pos.size(); ++i) tmp1 += pos[i] - i;ans = min(ans, tmp1);for (int i = pos.size() - 1, j = n - 1; i >= 0; --i, --j) tmp2 += j - pos[i];ans = min(ans, tmp2);write(ans);}return 0;
}

怪兽突击

ps：总觉得codeforces做过。。

思路

• 枚举每个 $i$ （当然要小于等于 $k$ ）。

signed main() {int T = 1;
//    T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= n; ++i) b[i] = read();priority_queue<int, vector<int>, greater<int>> pq;int ans = 1e17, cnt = 0;for (int i = 1; i <= n && i <= k; ++i) {cnt += a[i];pq.push(a[i] + b[i]);ans = min(ans, cnt + (k - i) * pq.top());}write(ans);}return 0;
}

蓝桥快打

思路

• 根据 $A,C$ 可以得出攻击次数的范围，$B\le n\cdot x$ 。

signed main() {int T = 1;T = read();while (T--) {int a = read(), b = read(), c = read();int r = a / c + (a % c > 0);writeln(b / r + (b % r > 0));}return 0;
}

奇怪的段

思路

• $dp$
• 方程： $d{p}_i=max(d{p}_{i-1,j},d{p}_{i-1,j-1})+a_i\cdot p_j$ 。
• 注意有负数

signed main() {int T = 1;
//    T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), p(k + 1);vector<vector<int>> dp(n + 1, vector<int>(201, -1e15));dp[0][0] = 0;for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= k; ++i) p[i] = read();for (int i = 1; i <= n; ++i) {for (int j = 1; j <= k; ++j) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i] * p[j];}}write(dp[n][k]);}return 0;
}

小蓝的反击

ps：是个区间求解问题，涉及基础数论。

思路

• 枚举每一个 $i$ ，找到最小位置 $j$ 满足 $A|{\prod }_{k=i}^{j_1}{a}_k,B|{\prod }_{k=i}^{j_2}{a}_k$ 。
• 如果 $j_1$ 不存在那么往后再也不能整除 $A$ 了。如果 $j_2$ 不存在，那么从 $j_1$ 到 $n$ 都能整出 $A$ 。都存在只有 $j_2>j_1$ 才对答案有贡献。
• 对 $A,B$ 质因数分解记录因子和各因子数量。
• 对 $A,B$ 每一个因子做前缀和。
• 二分枚举区间询问是否存在（该有的因子和数量都要满足）。

ps：前缀和那儿显然是个二维的，试想质因数分解有可能出现因数很大的情况，第二维是因数大小会 $MEL$ ，所以第二维应该为数量，而数量最多是10（前十个质数相乘已经 $>10^9$ ）。看题解有个 $dp$ 的，巨，我不会。

signed main() {auto getFactor = [&] (int v) {vector<pii> vec;for (int i = 2; i <= v / i; ++i) {if (!(v % i)) {vec.push_back({i, 0});while (!(v % i)) v /= i, ++vec.back().second;}}if (v ^ 1) vec.push_back({v, 1});return vec;};int T = 1;
//    T = read();while (T--) {int n = read(), a = read(), b = read();auto vec1 = getFactor(a), vec2 = getFactor(b);vector<vector<int>> prefa(n + 1, vector<int>(10)), prefb(n + 1, vector<int>(10));for (int i = 1; i <= n; ++i) {int u = read();for (int j = 0; j < vec1.size(); ++j) {int tmp = u, v = vec1[j].first;while (!(tmp % v)) {++prefa[i][j];tmp /= v;}prefa[i][j] += prefa[i - 1][j];}for (int j = 0; j < vec2.size(); ++j) {int tmp = u, v = vec2[j].first;while (!(tmp % v)) {++prefb[i][j];tmp /= v;}prefb[i][j] += prefb[i - 1][j];}}auto find = [&] (int i, int j, int cnt, int op) {int l = i, r = n, tmp = op? prefb[i - 1][j]: prefa[i - 1][j];int ans = -1;while (l <= r) {int mid = (l + r) >> 1, v = op? prefb[mid][j]: prefa[mid][j];if (v - tmp >= cnt) ans = mid, r = mid - 1;else l = mid + 1;}return ans;};long long int ans = 0;for (int i = 1; i <= n; ++i) {int pos1 = i;for (int j = 0; j < vec1.size(); ++j) {int pos = find(i, j, vec1[j].second, 0);if (pos ^ -1) pos1 = max(pos1, pos);else {pos1 = -1;break;}}if (pos1 == -1) break;int pos2 = i;for (int j = 0; j < vec2.size(); ++j) {int pos = find(i, j, vec2[j].second, 1);if (pos ^ -1) pos2 = max(pos2, pos);else {pos2 = -1;break;}}if (pos2 == -1) ans += (n - pos1 + 1) * 1ll;else if (pos2 > pos1) ans += (pos2 - pos1) * 1ll;}// write(ans);cout << ans;}return 0;
}