Solution from problem setter.
简单算法场
A. Amiable Parameter
背景
福师大第20届校赛 E 题 改编。
题意
给定 \(f(x) = |x - a_1| + |x - a_2| + \ldots + |x - a_n| + b_1 + b_2 + \ldots + b_n\)，找出最小的 \(x\)，使 \(f(x)\) 最小。
思路
计算中位数。
我们可以用点到数轴上的距离来形象化式子的左半部分。
如果数轴上有 \(n\) 个点，要找到一个点 \(p\)，使 \(p\) 和这些点的距离之和最小，显然我们取这些数的中位数。
你可以发现，如果中位数有两个，一定是取最小的那个中位数，因为两个中位数的答案是一样的。
那么，我们将 \(a_i\) 读入到数组中 并 升序排序，并统计 \(b_i\) 的总和 \(sum_b\)，然后我们对中位数算一下答案即可。
最后，别忘了加上右半部分式子的结果 \(sum_b\)。
注意，本题无法使用复杂度为 \(O(n ^ 2)\) 的排序算法通过。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n);
int sum_b = 0;
for(int i=0;i<n;i++){
int A, B;
cin >> A >> B;
a[i] = A, sum_b += B;
}
sort(a.begin(), a.end());
vector<int> mid = {a[n / 2]};
if(n % 2 == 0) mid.push_back(a[n / 2 - 1]);
int at = -1, ans = inf;
for(auto x : mid){
int cur = 0;
for(int i=0;i<n;i++) cur += abs(a[i] - x);
if(cur < ans) ans = cur, at = x;
else if(cur == ans) at = min(at, x);
}
cout << at << ' ' << ans + sum_b << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}bonus: 原题的修改是在线的，需要使用对顶堆维护
B. Breaking Dawn
题意
给定 \(n\) 张牌，输出是否存在一种方案，满足：
从中取出若干张牌，伤害总和 \(\geq X\)；
剩余的牌伤害总和 \(\geq Y\)。
思路
背包问题。
首先，乱贪心是完全错误的，无论怎么排序，你都不能保证最后一定是最优解。
我们不妨这么考虑：设 \(sum\) 为所有牌的伤害总和，那么如果存在一种方案，满足伤害总和恰好为 \(p\)，且满足 \(p \geq X, sum - p \geq Y\)，那么这个方案就是我们想要的。
这里，我们需要使用 \(01\) 背包 来解决这个问题 （动态规划）。
这是一个经典的 \(01\) 背包，我们将伤害总和想象为一个背包的容量，将一张牌的伤害想象为这张牌所占用的体积。
那么，我们定义 \(dp[i]\) 为容积为 \(i\) 的背包是否能装满。
你可以用二维空间的 \(01\) 背包解决问题（需要滚动数组），但显然一维空间会更优。
我们可以从前往后枚举所有牌，并从大到小枚举背包的容量。
如果某个牌的体积是 \(a_i\)，那么如果 \(dp[c - a_i]\) 为真，也就是容量为 \(c - a_i\) 的背包可以装满，放入这个牌之后，容量为 \(c\) 的背包也就可以装满了。
从而有状态转移方程：$dp[c] = dp[c] | dp[c - a_i] $。（取或）
最后，我们检查是否存在一个满足上面条件的 \(p\)，有 \(dp[p] = true\) 即可。
当然，\(dp[0] = true\)。
时间复杂度：\(O(nx)\)
对应AC代码1
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, x, y;
cin >> n >> x >> y;
vector<int> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
vector<int> dp(100010); //干脆开大一点，省事（
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int v = x; v >= a[i]; v--) {
dp[v] |= dp[v - a[i]];
}
}
for (int i = x; i <= sum && sum - i >= y; i++) {
if (dp[i]) {
cout << "Breaking Dawn!" << '\n';
return;
}
}
cout << "Adventure!" << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}本题也可以用 \(\mathtt{bitset}\) 优化复杂度，这也是很经典的。但好心的出题人并没有想要卡掉上面的做法。
时间复杂度：\(O(nx / 64)\)
对应AC代码2
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int N, X, Y, s = 0, a;
cin >> N >> X >> Y;
bitset<100007> bit;
bit[0] = 1;
for (int i = 1; i <= N; i++) {
cin >> a;
s += a;
bit |= bit << a;
}
for (int i = X; i <= s && s - i >= Y; i++) {
if (bit[i]) {
cout << "Breaking Dawn!\n";
return;
}
}
cout << "Adventure!\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}背包专题在 oj 里有
C. Calculate my Ptt, please!
题意
给定 \(n\) 个两位小数，令 \(ptt = (\) 最大的 \(10\) 个数之和 \(+\) 最大的 \(30\) 个数之和 \() / 40\)，将 \(ptt\) 保留两位小数，并去掉多余的小数位，而不是四舍五入。
输出 \(ptt\)。
思路
坑人签到题。
本题有三个坑点：
不要使用 \(O(n ^ 2)\) 的排序算法；你可以使用自带的 \(sort\) 函数（\(c\) 语言下是 \(qsort\)）；
避免对 \(double\) 进行累加求和；本题中，你可以把数字全都乘 \(100\) 并转为 \(long\ long\)，来规避这个问题；
注意审题，不要四舍五入；本题中，你可以在上面的操作基础上，向下取整，接着除 \(100\)，最后保留两位小数输出即可。
避开这三个坑点，这题就是签到题，模拟一下过程即可。
基本上挂的人都是挂在累加 \(double\)，然后乘 \(100\)，向下取整，然后除 \(100\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++) {
double cur;
cin >> cur;
a[i] = (int) (cur * 100); //全都乘个100，方便算
}
sort(a.rbegin(), a.rend()); //自带函数复杂度 O(n log n)
double ptt = 0;
for(int i = 0; i < 30; i ++){
ptt += (i < 10 ? 2.0 : 1.0) * a[i];
}
ptt /= 40;
cout << fixed << setprecision(2) << ((int) ptt) / 100.0 << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}其实样例就是我的 ptt（（
D. Dozens of Move
题意
给定一个包含 . 和 # 的字符串，指定一开始的位置。
有一个机器人在上面移动，一开始机器人向右移动，若遇到 #，机器人会将其改为 .，并更改移动方向；如果遇到左右边界，也会更改移动方向。
输出机器人在移动了几次后，字符串里的所有 # 才能变为 .。
思路
双指针。
首先，最朴素的做法就是模拟移动，但这样的复杂度最坏可以达到 \(O(n ^ 2)\) 级别，显然是无法通过的。
我们可以发现，每次移动后，我们都在扩展我们的可移动区间，并且扩展之后，这些地方都会被重新走好几次。
我们记当前扩展得到的区间为 \([l, r]\)。
那么比如我们这一次需要向左扩展，我们就完全没必要从 \(r\) 再模拟走到 \(l\)，因为我们知道 \([l, r]\) 上面一定没有 #，而且需要走的步数是已知的 \(r - l\)，那么我们不妨将答案加上 \(r - l\)，然后直接跳到 \(l\)，并继续向左扩展。向右扩展的方法是类似的。
那么，我们可以发现，现在每个格子就只会被访问到一次了，从而将时间复杂度降为了最坏 \(O(n)\)。
时间复杂度：\(O(n)\)
对应AC代码 (Ocean)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, a;
cin >> n >> a;
string s;
cin >> s;
s = " " + s; //让下标从1开始
int cnt = 0;
for(auto &e : s){
if(e == '#') cnt ++;
}
int l = a, r = a;
int ans = 0;
int d = 1; //1 right, -1 left
while(cnt > 0){
ans += r - l;
if(d == 1) {
while(r <= n && s[r] == '.') r ++, ans ++;
if(r <= n) s[r] = '.', cnt --;
}else{
while(l >= 1 && s[l] == '.') l --, ans ++;
if(l >= 1) s[l] = '.', cnt --;
}
d = -d;
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}对应AC代码 (Std)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, A;
string S;
cin >> N >> A >> S;
int l = A-1, r = A-1, n = A-1, d = 1, cnt = 0;
for(int i=0; i<S.size(); i++){
if(S[i] == '#') cnt++;
}
long long ans = 0;
while(cnt > 0){
if(d == 1){
ans++, n++;
if(n < N) r = n;
if(n == N || S[n] == '#'){
if(n < N) cnt--;
d = -1;
if(cnt > 0) ans += n - l, n = l; // skip
}
}
else{
ans++, n--;
if(n >= 0) l = n;
if(n == -1 || S[n] == '#'){
if(n >= 0) cnt--;
d = 1;
if(cnt > 0) ans += r - n, n = r; // skip
}
}
}
cout << ans << endl;
return 0;
}严格来说也不是双指针算法，只是有两个指针罢了（
E. End with NO 0
背景
灵感来自暑假牛客集训营的某一题（有点忘了）。
题意
对于 \(1, 2, \ldots, n\)，删除尽可能少的数字，来让剩余数字的乘积不包含后缀 \(0\)。输出剩余数字的最大个数。
思路
简单思维题。
首先，既然要让乘积末尾出现 \(0\)，乘积中肯定要同时存在 \(2\) 的倍数和 \(5\) 的倍数。
那么很明显，我们只要让剩余数字中不包含 \(2\) 的倍数，或者不包含 \(5\) 的倍数就好了。
显然，从 \(1\) 开始的话，肯定是 \(5\) 的倍数更少，从而我们考虑删除 \(5\) 的倍数，剩下的数字个数就是我们要的答案。
好心的出题人没有把范围开到 \(10 ^ {18}\)，他怕你一顿操作爆 \(long\ long\) 了（x
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
cout << (n - n / 5) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}下一场要么来卡一下 \(long\ long\)？
F. Force Ripening
背景
题目来自 Codeforces CodeTON Round 4 (Div. 1 + Div. 2) B题，难度 \(800\)。
题意
对于 \(x\)，一开始 \(x = 1\)，定义操作为下面选项任选一：
\(x := 2x - 1\)；
\(x := 2x + 1\)。
现在，给定操作后的数，判断是否可以还原操作方案，不可以输出 \(-1\)，可以的话输出方案。
思路
思维题。
首先，很显然，操作后得到的数不可能是偶数，那么我们就可以进行特判。
在上面的基础上，我们可以发现，若操作后的数是 \(p\)，那么原来的数可以是 \(\frac{p - 1}{2}, \frac{p + 1}{2}\)。
显然，这两个数是一奇一偶的，而原来的数也不可能是偶数，从而原来的数是唯一确定的。
那么，我们可以倒推，只要能推到 \(1\)，就可以还原操作方案（当然，既然我们是倒推，记得反着输出）。
事实上，上面的操作可以将 \(1\) 变为任意正奇数。
时间复杂度：\(O(\log x)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
if(n % 2 == 0){
cout << -1 << '\n';
return;
}
vector<int> ans;
while(n > 1){
if((n - 1) / 2 % 2 == 0) n = (n + 1) / 2, ans.emplace_back(1); //≈push_back
else n = (n - 1) / 2, ans.emplace_back(2);
}
reverse(ans.begin(), ans.end()); //反转一下
cout << ans.size() << '\n';
for(auto each : ans) cout << each << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}逆向思维（
G. Genshin Impact, Start!
题意
给定一个灰度值矩阵，找出与 \(255\) 的差值不小于 \(k\) 的点的个数 \(cnt\)，如果 \(cnt\) 不超过 \(p\)，那么判定启动。
思路
简单签到题。
显然，我们将所有数全都读进来，然后根据题面模拟计算即可。
注意题面中的 "不小于"，"不超过"。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int k, p, n, m;
cin >> k >> p >> n >> m;
int cnt = 0;
for (int i = 0; i < n * m; i ++) {
int cur;
cin >> cur;
if (255 - cur >= k) cnt ++;
}
if (cnt <= p) cout << "zenmenile" << '\n';
else cout << "wande" << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}本来想出的更麻烦一点，但这种 ___ 题还是去 \(AtCoder\) 做吧
H. Homework of Math
题意
给定整数 \(n\)，输出 \((a + b) ^ n\) 的表达式，如果系数是 \(1\) 需要忽略，次方是 \(0\) 也需要忽略。
例如 \((a + b) ^ 2 = a ^ 2 + 2ab + b ^ 2\)。
思路
组合数问题。
显然，总共有 \(n + 1\) 项，第 \(i\) 项的系数是 \(C_n^{i - 1}\)。
对于系数，你可以暴力计算（只要不是太暴力），也可以使用杨辉三角递推。
出题人想要卡掉暴力计算和 \(long\ long\)，但是被好心的组题人和验题人拦下了（x
但，于是这题变成了可以打表的题（？
时间复杂度：\(O(n)\)
对应AC代码 (Ocean)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> p(n + 2);
p[0] = 1;
for (int i = 1; i <= n; i++) { //杨辉三角
for (int j = i; j >= 1; j --) p[j] += p[j - 1];
}
cout << "(a+b)^" << n << "=";
for(int i=0;i<=n;i++){
if(p[i] != 1) cout << p[i];
if(i != n) {
cout << "a";
if(i != n - 1) cout << '^' << (n - i);
}
if(i != 0) {
cout << "b";
if(i != 1) cout << '^' << i;
}
if(i != n) cout << "+";
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}对应AC代码 (Std)
#include <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; i++)
using namespace std;
unsigned long long f[71];
int n;
int main()
{
scanf("%d", &n); f[0] = 1;
FOR(i, 1, n) for(int j = i; j; j--) f[j] += f[j - 1];
printf("(a+b)^%d=", n);
FOR(i, 0, n)
{
if (i) putchar('+');
if (i && n - i) printf("%llu", f[i]);
if (n - i)
{
putchar('a');
if (n - i != 1) printf("^%d", n - i);
}
if (i)
{
putchar('b');
if (i != 1) printf("^%d", i);
}
}
puts("");
return 0;
}bonus: 如果 \(n \leq 67\) 呢？
I. I Super, Explosion
背景
2023 牛客寒假训练营 2 的 I 题 改编。
题意
给定 \(n\) 个音符，每个音符有对应偏移值 \(c\)，定义 \(m\) 个判定区间 \((- \infty,a_1), [a_1, a_2), \ldots, [a_{m - 1},+\infty)\)，\(c\) 落在第 \(i\) 个区间内可获得对应判定分 \(v_i\)。输出将所有的 \(c\) 加上或减去任意值后判定分总和的最大值。
思路
思维+排序。
首先，我们可以将所有音符的偏移值全都减去一个相同的且很大的值，来让所有音符都位于第一个判定区间。
然后，我们可以按照 每个音符 距离进入下一个判定区间 所需的偏移值更改量，从小到大进行偏移值的更改。
因为偏移值是整体移动的，所以如果按照上面的排序方式，当我们枚举到第三小的偏移值更改时，前面两个偏移值也一定进行了更改。
从而，我们只需在枚举的时候，累加每次更改偏移值后的分数变化，最后找出分数和最大的一种更改即可。
形象地来说，你可以将音符理解为数轴上的点，一开始所有点都在第一个判定区间，然后所有点向右整体移动，累加每次移动带来的分数变化，最后最大的分数和就是调整后判定分总和的最大值了。
时间复杂度：\(O(nm \log (nm))\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<int> c(n + 1), a(m), v(m + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
c[i] -= 2e9; //全部挪到第一判定区间
}
for (int i = 1; i < m; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> v[i];
vector<pair<int, int>> p;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) {
p.emplace_back(a[j] - c[i], v[j + 1] - v[j]); //设备偏移值，修改后分数的变化
}
}
sort(p.begin(), p.end());
int cur = v[1] * n, ans = cur;
for (auto &e: p) {
cur += e.second;
ans = max(ans, cur);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}听说有人想做牛客寒假的题（x
牛客的原题是可以二分的，这题不好说（x