2023牛客寒假算法集训营4

A. 清楚姐姐学信息论（数学）

题意：

给定两个非负整数 $x$ ， $y$ $(2\le x,y\le 10^9)$ ，表示 $x$ 进制和 $y$ 进制，比较哪种进制的信息表示效率更高。

当且仅当，$x$ 进制和 $y$ 进制分别使用 $x\cdot y$ 个数时， $x$ 进制能够表示的数字数目大于 $y$ 进制，则称 $x$ 进制的信息表示效率大于 $y$ 进制。

思路一：

比较 $x^y$ 和 $y^x$​ 的大小就行。

但是你这样写会发现，炸了，数据太大了，所以需要优化一下：

改成比较 $y\cdot lo{g}_x$ 和 $x\cdot lo{g}_y$​ 就行了。

特别注意：优化后要用浮点数去比较，存在精度问题，如果用整数比较会有部分测试点过不了。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;int main()
{ll x, y;cin >> x >> y;if (x == y) cout << x << endl;else {double xx = y * log(x);double yy = x * log(y);if (xx > yy) cout << x << endl;else if (xx < yy) cout << y << endl;else cout << min(x, y) << endl;}return 0;
}

思路二：

思路二就比较神奇，用的是数学的方法。

结论：$e$ 进制是效率最高的进制。

因此越靠近 $e$ 进制效率越高，$e\approx 2.7$ ，所以在比较 $(2,3)$ 时，$3$ 进制效率更高，其他情况都是小的进制更优。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;int main()
{ll x, y;cin >> x >> y;if (x == 2 || y == 3) cout << 3 << endl;else cout << min(x, y) << endl;return 0;
}

---

B. 清楚姐姐学构造（数学 + 构造）

题意：

给定一个长度为 $N$ 的数组 $c$ 和一个质数 $m$，请你构造另外两个 同余等式 数组 $a,b$ 满足：

$\{\begin{array}{c}{a}_i\equiv a_{N-1-i}(\mathrm{mod}m)\\ b_i\equiv -b_{N-1-i}(\mathrm{mod}m)\\ c_i\equiv a_i+b_i(\mathrm{mod}m)\end{array}$

数组 $a,b,c$ 的下标均从 $0$ 开始计算。

如果可以构造出数组 $a,b$，则首先输出 $Yes$，然后输出任意一种解，否则只需输出一行一个字符串 $No$ 。

$\equiv$ 为同余符号，它表示两个整数对 $m$ 取余数的结果相同，对于负数取余数，若结果仍为负数，则需要加上 $m$ 。

思路：

一个重要结论：任何一个函数都可以表示成奇函数和偶函数的和。

$a$ 数组就是两边的数关于中心对称轴相等，而 $b$​​ 数组则是关于中心对称轴相反。

要求 $c_i=a_i+b_i$​ ，即要求构造一个奇函数和一个偶函数来表示任意一个函数。

出题人题解

任取一个数列 $c$，设 $c[i]\equiv a[i]+b[i]$ ，设 $a[i]$ 数列关于 $N/2$ 对称， $b[i]$ 数列关于 $N/2$ 对称相反。

则 $c[N-i-1]\equiv a[N-i-1]+b[N-i-1]$ .

两式相加可得 $c[i]+c[N-i-1]\equiv a[i]+b[i]+a[N-i-1]+b[N-i-1]$ ，根据题意， $b[i]$ 数列对称相反消掉， $a[i]$ 数列关于 $N/2$ 对称则 $a[i]\equiv a[N-i-1]$ 。化简得

$c[i]+c[N-i-1]\equiv 2\cdot a[i]$ 即 $a[i]\equiv (c[i]+c[N-i-1])\cdot inv(2)$ 。注意当 $m=2$ 无逆元需要特殊处理。

相似的，两式相减得 $b[i]\equiv (c[i]-c[N-i-1])\cdot inv(2)$ 。和之前一样， $m=2$ 时无逆特殊处理即可。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;ll n, m;
ll a[N], b[N], c[N];ll qmi(ll a, ll b)  //快速幂求逆元
{ll res = 1;a = (a % m + m) % m;while (b){if (b & 1) res = res * a % m;a = a * a % m;b >>= 1;}return res;
}bool check()
{for (int i = 1; i <= n; i++)if (c[i] != c[n - i + 1])return false;return true;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){cin >> c[i];}if (m == 2){if (check()){cout << "Yes" << endl;for (int i = 1; i <= n; i++)cout << c[i] << ' ';cout << endl;for (int i = 1; i <= n; i++)cout << 0 << ' ';cout << endl;}else cout << "No" << endl;}else {ll inv2 = qmi(2, m - 2);  //对2特判处理for (int i = 1; i <= n; i++){a[i] = (c[i] + c[n - i + 1]) * inv2 % m;b[i] = (c[i] + m - c[n - i + 1]) * inv2 % m;}cout << "Yes" << endl;for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << endl;for (int i = 1; i <= n; i++)cout << b[i] << ' ';cout << endl;}return 0;
}

---

C. 清楚姐姐学01背包(Easy Version)（01背包）

题意：

有 $n$ 个物品，每个物品的体积为 $w$ ，价值为 $v$ ，背包的容量为 $m$ 。

可以从 $n$​ 个物品中任选若干个放入背包，要保证总体积不能超过背包容量。

现定义背包中所放物品价值总和的最大值为 $V$ ，从这 $n$ 个物品中去掉某一个物品后，从剩余 $n-1$ 个物品中任选若干个放入背包，后来所放物品价值总和的最大值为 $V^{\prime }$ 。

若 $V^{\prime }<V$​ ，则称这个物品为必选物品。

求出对于每一个物品，它的价值再加上多少，能称为一个必选物品。

思路：

比普通的 01 背包题多了一个条件。

枚举每个物品，除了这个物品外，计算其他物品的01背包，再判断该物品是否必须取，它还需加上的价值就是 V - V' 。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 110;int n, m;
ll w[N], v[N];int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){cin >> w[i] >> v[i];}for (int i = 1; i <= n; i++){vector<ll> dp(m + 1);for (int j = 1; j <= n; j++){if (i != j){for (int k = m; k >= w[j]; k--){dp[k] = max(dp[k], dp[k - w[j]] + v[j]);}}}ll res = dp[m] - (dp[m - w[i]] + v[i]) + 1;if (res < 0) cout << 0 << endl;else cout << res << endl;}return 0;
}

---

D. 清楚姐姐学01背包(Hard Version)（01背包）

题意：

与 C 题一样，不同的是数据范围变大。 $(1\le n,m\le 5000)$

思路：

歪门邪道法：

类似于上题，既然琺暴力，那就分组求背包，以 75 个为一组，分成 75 个背包，第 $i$ 个背包中不含第 $i$ 组的物品。

其中对于第 $j$ 个物品，找到其所在组数，把这组除了 $j$ 以外的物品装入背包，再使用 C 题的方法判断即可。

再放上正经的解法：出题人题解

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 5010;int n, m;
ll w[N], v[N];int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;vector dp(76, vector<ll>(m + 1));for (int i = 1; i <= n; i++){cin >> w[i] >> v[i];int t = i / 75;for (int k = 0; k < 75; k++){if (k != t){for (int j = m; j >= w[i]; j--){dp[k][j] = max(dp[k][j], dp[k][j - w[i]] + v[i]);}}}}for (int i = 1; i <= n; i++){int t = i / 75;auto f = dp[t];for (int j = 1; j <= n; j++){if (i != j && t == j / 75){for (int k = m; k >= w[j]; k--){f[k] = max(f[k], f[k - w[j]] + v[j]);}}}ll ans = f[m] - f[m - w[i]] - v[i] + 1;if (ans < 0) cout << 0 << endl;else cout << ans << endl;}return 0;
}

---

E. 清楚姐姐打怪升级（数学 or 二分）

题意：

打怪游戏，有 $n$ 只怪物，每只怪物的生命上限为 $h$ ，生命每时刻恢复 $v$ 点。

每次攻击的间隔为 $t$ ，攻击力为 $a$ 。

在每个时刻初，若怪物的生命值不满，则恢复 $v$ 点生命值，但是不能超过生命值上限 $h$ 。

每次攻击可以选择一只怪物造成 $a$ 点伤害，若此时怪物生命值小于等于 $0$ ，则怪物死亡。

现在问至少在第几个时刻末可以杀死所有怪物，若永远无法杀死所有怪物则输出 $-1$ 。

思路：

已知 $n$ 只怪物的血量，回血速度，自身攻击力和攻击间隔，求打死所有怪物的时间。（注意，攻击是从时刻 $1$ 开始的）

如果不能一刀解决，那么该怪物必定会经过 掉血 + 回血 的循环。

因此先把最后一刀减去，然后计算剩下的血量何时能扣完。

假设砍一刀后血量为 $w=a-v$ ，如果 $w\le 0$ 则无解，否则计算总轮数 $s=\lceil \frac{h}{w}\rceil +1$ ，时间为 $(s-1)\cdot t+1$ 。

也可以二分计算：

二分恰好 $x$ 次打死怪物，那么 check 时，前面已经攻击了 $x-1$ 次，加上血量回复，再补上第 $x$ 次攻击，若怪物血量 $h\le 0$ ，则 check = true 。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;ll n, t, a;
ll h[N], v[N];bool check()
{for (int i = 1; i <= n; i++){if (a <= v[i] && a < h[i])return false;}return true;
}int main()
{cin >> n >> t >> a;for (int i = 1; i <= n; i++){cin >> h[i] >> v[i];v[i] *= t;}if (!check()){cout << -1 << endl;}else{ll res = 0;for (int i = 1; i <= n; i++){if (h[i] <= a) res++;else {ll w = a - v[i];res += (h[i] - a + w - 1) / w + 1;  //向上取整}}cout << (res - 1) * t + 1 << endl;}return 0;
}

---

F. 清楚姐姐学树状数组（二叉树 + DFS）

题意：

有一个尺寸大小为 $N=2^k$ 的树状数组，按照如下的规则构造出一个"树状数组二叉树"。

1. 编号为 $i$ 的节点的深度为 $log2(lowbit(N))-log2(lowbit(i))$ 。

2. 整棵二叉树的中序遍历节点编号顺序为 $1,2,\mathrm{3...}N-1,N$ 。

问对于树状数组生成的二叉树上编号为 $x$ 的节点，分别在前序、中序、后序遍历中是第几个被遍历到的节点？

思路：

给一个树状数组，建成一个二叉树，查询若干个节点的前中后序遍历。

树状数组中的两条重要路径为 $x\to x+lobit(x)$ 和 $x\to x-lobit(x)$

• 当一个节点是左孩子时，其父节点是 $x\to x+lobit(x)$ ​
• 当一个节点是右孩子时，其父节点是 $x\to x-lobit(x)$

因为长度大小为 $2^k$ 的树状数组除根节点外都是全满的，大小实际上就是 $2^m-1$ 可以直接计算，所以 DFS 模拟前序和后序的过程中跳过整颗的子树部分直接计算答案即可。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 2010;ll k, q;
ll n;ll lowbit(ll x)
{return x & -x;
}ll size(ll x)
{return (lowbit(x) << 1) - 1;
}bool is_lchild(ll x)
{return !(x & (lowbit(x) << 1));
}ll fa(ll x)
{if (is_lchild(x))return x + lowbit(x);return x - lowbit(x);
}ll lch(ll x)
{return x ^ lowbit(x) ^ (lowbit(x) >> 1);
}ll rch(ll x)
{return x ^ (lowbit(x) >> 1);
}ll L(ll x)
{ll root = n, ret = 1;while (root != x){ret++;if (x < root){root = lch(root);}else {ret += size(lch(root));root = rch(root);}}return ret;
}ll R(ll x)
{if (x == n) return n;ll root = x, ret = size(root);while (root != n){if (root == rch(fa(root))){ret += size(lch(fa(root)));}root = fa(root);}return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> k >> q;n = 1ll << k;while (q--){ll x;cin >> x;cout << L(x) << ' ' << x << ' ' << R(x) << endl;}return 0;
}

---

G. 清楚姐姐逛街(Easy Version)（BFS）

题意：

A，B 两人走地图，要求 B 在最短的时间内追上 A 。

地图可以视为是一个 $N\cdot M$ 的二维平面，左上角为坐标原点 $(0,0)$ ，向下为 $x$ 轴正方向，向右为 $y$ 轴正方向，入口位于点 $s(x_s,y_s)$ 。

地图行走规则如下:

‘L’ – 向左，‘R’ – 向右，‘U’ – 向上，‘D’ – 向下

‘.’ – 表示终止位置，当移动到这里后将永远停在该位置

‘#’ – 表示墙壁，任何人都不能移动到这里

B 追 A，且 B 可以随意移动或停在原地，不必遵守地图的规则。

B 从入口处出发，有 $Q$ 次询问，每次输入一个坐标表示 A 从该位置开始移动，问至少要多久才能追上 A ，若无论如何都追不上则输出 -1.

思路：

首先预处理 B 到达每个位置所花费的时间，因为 B 可以随便走，所以先用 BFS 遍历连通块，计算到达每个位置的时间。

然后对于每次询问，A 按照地图规则来走，直到 A到达某个位置的时间 ≥ B到达的时间，则 B 能追上 A 。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define PII pair<int, int>
using namespace std;
const int N = 810;int n, m, sx, sy, Q;
char mp[N][N];
int d[N][N];void bfs()
{queue<PII> q;q.push({sx, sy});d[sx][sy] = 0;while (!q.empty()){int x = q.front().first, y = q.front().second;q.pop();int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};for (int i = 0; i < 4; i++){int xx = x + dx[i], yy = y + dy[i];if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && d[x][y] + 1 < d[xx][yy] && mp[xx][yy] != '#'){d[xx][yy] = d[x][y] + 1;q.push({xx, yy});}}}
}int main()
{memset(d, 63, sizeof d);cin >> n >> m >> sx >> sy >> Q;sx++, sy++;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> mp[i][j];bfs();while (Q--){int x, y;cin >> x >> y;x++, y++;int f = 1, res = 1;while (1){int lax = x, lay = y;if (mp[x][y] == 'U' && mp[x - 1][y] != '#') x--;else if (mp[x][y] == 'D' && mp[x + 1][y] != '#') x++;else if (mp[x][y] == 'R' && mp[x][y + 1] != '#') y++;else if (mp[x][y] == 'L' && mp[x][y - 1] != '#') y--;if (lax == x && lay == y){if (d[x][y] >= 1e9){f = 0;break;}}if (d[x][y] <= res){res = max(d[x][y], res);break;}res++;}if (!f) cout << -1 << endl;else cout << res << endl;}return 0;
}

---

L. 清楚姐姐的三角形I（数学 + 推公式）

题意：

假设三角形的三条边的长度分别为 $a,b,c$ 。

定义三角形的三个顶点分别为 $A,B,C$，顶点 $A$ 连接 $b,c$ 两边；顶点 $B$ 连接 $a,c$ 两边；顶点 $C$ 连接 $a,b$ 两边。

定义三角形三个顶点的权值 $V_A=l_b+l_c,V_B=l_a+l_c,V_C=l_a+l_b$ 。

现在给定 $V_A,V_B,V_C$ ​的值，求 $a,b,c$ ​的值。

思路：

我们根据三角形已知条件推出三条边的表达式：

$a=(v_b+v_c-v_a)/2$
$b=(v_a+v_c-v_b)/2$
$c=(v_a+v_b-v_c)/2$

然后根据组成三角形的条件：任意两边之和大于第三边，任意两边之差小于第三边

判断这三条边能否组成三角形即可。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;void solve()
{ll va, vb, vc;cin >> va >> vb >> vc;ll s = (va + vb + vc) / 2;if (s < 3){cout << "NO" << endl;}else {ll a = (vb + vc - va) / 2;ll b = (va + vc - vb) / 2;ll c = (va + vb - vc) / 2;if (a + b > c && b + c > a && c + a > b&& abs(a - b) < c && abs(b - c) < a && abs(c - a) < b&& va == b + c && vb == a + c && vc == a + b){cout << "YES" << endl;cout << a << ' ' << b << ' ' << c << endl;}else {cout << "NO" << endl;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}

---

M. 清楚姐姐的三角形II（构造）

题意：

要求构造一个大小为 $n$ 的数组，满足数组中每相邻的三项均不能组成三角形，输出这个数组。

思路：

你以为是斐波那契？？？NoNoNo，请下载国家反诈APP.

题目只要求相邻三项无法构成三角形，条件很少，怎么样构造都可以。

我们任意选三个不能组成三角形的数循环就行了，这里用的是 1 1 2 。

代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;int a[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){if (i % 3) cout << 1 << ' ';else cout << 2 << ' ';}cout << endl;return 0;
}

---