04-28 22:15 已编辑湖南科技大学计算机类

关注

牛客小白月赛92出题人题解

A 获得木头

$1$ 个原木= $4$ 个木板， $2$ 个木板= $4$ 根木棍，所以 $1$ 个原木= $8$ 根木棍。

现在有 $x$ 个原木，一共可以得到 $8x$ 根木棍，输出 $8x$ 即可。

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x;
	cin >> x;
	cout << x * 8;
	return 0;
}

B 采矿时间到！

只能垂直于矿道挖掘， $5*n$ 的矩阵

所以我们考虑现挖 $2$ 和 $4$ 层，也就是说如果 $g[2/4][j]$ 为 $*$ 的话，那么消耗 $1$ 点体力挖掉。

然后再考虑挖 $1$ 和 $5$ 层，如果 $g[1/5][j]$ 为 $*$ 且 $g[2/4][j]$ 被挖掉了，那么消耗 $1$ 点体力挖掉。

如果 $g[1/5][j]$ 为 $*$ 且 $g[2/4][j]$ 没有被挖掉，那么消耗 $2$ 点体力挖掉。

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

string g[5];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, h;
	cin >> n >> h;
	for (int i = 0 ; i < 5 ; i++) {
		cin >> g[i];
	}
	int ans = 0;
	for (int i = 0 ; i < n ; i++) {
		if (g[1][i] == '*' && h) {
			g[1][i] = '.';
			h--;
			ans++;
		}
		if (g[3][i] == '*' && h) {
			g[3][i] = '.';
			h--;
			ans++;
		}
	}
	for (int i = 0 ; i < n ; i++) {
		if (g[0][i] == '*' && g[1][i] == '.' && h) {
			g[0][i] = '.';
			h--;
			ans++;
		}
		if (g[4][i] == '*' && g[3][i] == '.' && h) {
			g[4][i] = '.';
			h--;
			ans++;
		}
	}
	for (int i = 0 ; i < n ; i++) {
		if (g[0][i] == '*' && g[1][i] == '#' && h > 1) {
			g[0][i] = '.';
			h -= 2;
			ans++;
		}
		if (g[4][i] == '*' && g[3][i] == '#' && h > 1) {
			g[4][i] = '.';
			h -= 2;
			ans++;
		}
	}
	cout << ans;
	return 0;
}

C 耕种时间到！

容易知道 $3^{30}>10^9$ ，所以收割 $30$ 次以后所有小麦种子的等级都会为 $1$ 。

因为 $x\geq2$ ，所以不需要考虑等级为 $1$ 的种子，因为等级为 $1$ 的会无限产生自己。

那么我们暴力枚举收割轮数，时间复杂度 $O(30n)$ 。

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

using i64 = long long;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1 ; i <= n ; i++) {
		cin >> a[i];
	}
	int x;
	cin >> x;
	i64 ans = 0;
	for (int i = 0 ; i <= 30 ; i++) {
		i64 res = 0;
		for (int j = 1 ; j <= n ; j++) {
			if (a[j] == x) {
				res += 1LL << i;
			}
			a[j] = (a[j] + 2) / 3;
		}
		ans = max(ans, res);
	}
	cout << ans << "\n";
	return 0;
}

D 探索的时光

危险度之和为 $\sum_{i=1}^nf(i)=\sum_{i=1}^n{(x-i)}^2*a_i=x^2*\sum_{i=1}^na_i-2x*\sum_{i=1}^ni*a_i\text{+}\sum_{i=1}^ni^2*a_i$

已知 $\sum_{i=1}^na_i$ ， $\sum_{i=1}^ni*a_i$ ， $\sum_{i=1}^ni^2*a_i$ 可以通过 $O(n)$ 的时间内求出。

然后再通过 $O(n)$ 的时间枚举 $x$ 的值，对结果取 $\min$ 即可求出答案，总时间复杂度为 $O(n)$

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

using i64 = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	i64 A = 0, B = 0, C = 0;
	for (int i = 1 ; i <= n ; i++) {
		cin >> a[i];
		A += a[i];
		B += 1LL * i * a[i];
		C += 1LL * i * i * a[i];
	}
	i64 ans = 0x7fffffffffffffff;
	for (int i = 1 ; i <= n ; i++) {
		i64 x = i;
		i64 res = x * x * A - 2LL * x * B + C;
		ans = min(ans, res);
	}
	cout << ans << "\n";
	return 0;
}

E 来硬的

解法一

先考虑不使用魔法的做法，就是一个普通的01背包， $dp[i][j]$ 表示前 $i$ 个煤炭，烧 $j$ 个矿石所需要的最小时间。 $dp[i][j+x[i]]=max(dp[i][j+x[i]],dp[i-1][j]+y[i])$

然后答案就是 $dp[n][m]$ 。

此时使用魔法，因为只能使用一次，所以我们可以枚举这一次，假设第 $k$ 个煤炭变成了暗物质，那么煤炭分为了两个区间 $[1,k-1]$ 内的煤炭和区间 $[k+1,n]$ 内的煤炭，此时我们需要这两个区间烧 $m-2*x[k]$ 个矿石。我们可以枚举左边区间烧 $L$ 个矿石，右边区间则就烧了 $m-2*x[k]-L$ 个矿石。因为 $\max(m)\leq10^5$ ，所以时间复杂度是 $O(n*m)$ ，以至于两边区间的求法，可以考虑前缀后缀01背包，即 $dpL[i][j]$ 表示前 $i$ 个煤炭，烧 $j$ 个矿石所需要的最小时间。 $dpR[i][j]$ 表示后 $i$ 个煤炭，烧 $j$ 个矿石所需要的最小时间。

则答案为 $\min(\frac{y[k]}{2}+\min(dpL[k-1][L]+dpR[k+1][m-2*x[k]-L]))$

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

const int N = 1000005;
int x[N + 5], y[N + 5];
using i64 = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector dpL(n + 5, vector(m + 5, (i64) 1e14));
	vector dpR(n + 5, vector(m + 5, (i64) 1e14));
	for (int i = 1 ; i <= n ; i++) {
		cin >> x[i] >> y[i];
	}
	dpL[0][0] = 0;
	for (int i = 1 ; i <= n ; i++) {
		for (int j = 0 ; j <= m ; j++) {
			dpL[i][j] = dpL[i - 1][j];
		}
		for (int j = 0 ; j <= m ; j++) {
			dpL[i][min(m, j + x[i])] = min(dpL[i][min(m, j + x[i])], dpL[i - 1][j] + y[i]);
		}
		for (int j = m - 1 ; j >= 0 ; j--) {
			dpL[i][j] = min(dpL[i][j], dpL[i][j + 1]);
		}
	}
	dpR[n + 1][0] = 0;
	for (int i = n ; i >= 1 ; i--) {
		for (int j = 0 ; j <= m ; j++) {
			dpR[i][j] = dpR[i + 1][j];
		}
		for (int j = 0 ; j <= m ; j++) {
			dpR[i][min(m, j + x[i])] = min(dpR[i][min(m, j + x[i])], dpR[i + 1][j] + y[i]);
		}
		for (int j = m - 1 ; j >= 0 ; j--) {
			dpR[i][j] = min(dpR[i][j], dpR[i][j + 1]);
		}
	}
	i64 ans = 0x7fffffffffffffff;
	for (int i = 1 ; i <= n ; i++) {
		int sum = max(0, m - 2 * x[i]);
		for (int L = 0 ; L <= sum ; L++) {
			i64 res = y[i] / 2 + dpL[i - 1][L] + dpR[i + 1][sum - L];
			ans = min(ans, res);
		}
	}
	cout << ans;
	return 0;
}

解法二

直接背包， $dp[i][j][k]$ 表示前 $i$ 个煤炭烧炼 $j$ 单位矿石，使用了 $k$ 次魔法的最短时间。

F 快快乐乐剪羊毛

先把草皮整体往右移 $\infty$ ，这样保证所有羊都在最左边一块草皮的左侧，此时价值和为 $0$ 。

然后向右移动草皮，每当一只羊到一块草皮的左端点时，更新价值加上新草皮与旧草皮的差。

这样可以保证所有羊在所有可能情况下的价值和都被计算过一遍，最大更新次数为 $n*m$ 直接用 set 存下即可。

怎么保证向右移动草皮的时间复杂度？

设 $x$ 为一只羊所在的横坐标， $L$ 为草皮的左端点。那么对于第 $i$ 块草皮，该羊的偏移量为 $L-x$ 。

通过从小到大枚举偏移量，即可确认羊走到某块草皮的左端点。

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

using i64 = long long;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<i64> w(n + 1);
	vector<int> v(n + 2);
	for (int i = 1 ; i <= n ; i++) {
		int x;
		cin >> x;
		w[i] = w[i - 1] + x;
	}
	for (int i = 1 ; i <= n ; i++) {
		cin >> v[i];
	}
	i64 res = 0;
	map<i64, vector<int>> e;
	for (int i = 0 ; i < m ; i++) {
		i64 x;
		cin >> x;
		for (int j = 1 ; j <= n + 1 ; j++) {
			e[w[j - 1] - x].push_back(v[j] - v[j - 1]);
		}
	}
	set<i64> ans;
	ans.insert(res);
	for (auto &[_, vec] : e) {
		for (auto &x : vec) {
			res += x;
		}
		ans.insert(res);
	}
	cout << ans.size() << "\n";
	return 0;
}

G 不速之客

idea 由 thisislike_fan 提供。

解法一

容易知道当 $x$ 的位数固定时， $f(x)=f(x_\text{合法排列})$

由 $|x-f(x)|\leq k$ 可得，当 $f(x)$ 确定时， $f(x)-k\leq x\leq f(x)+k$

所以如果我们知道 $f(x)$ ，那么我们可以检验这个区间内的数是否符合条件即可。

暴力检验整个区间肯定是超时的，我们可以考虑求 $1\leq x\leq f(x)+k$ 减去 $1\leq x\leq f(x)-k-1$

如何求在 $1\leq x\leq R$ 中排列的个数？考虑到贪心找到 $\leq R$ 的最大的 $x$ 的排列，然后它的排位就是我们要求的个数。

接下来考虑枚举 $f(x)$

对于位数为 $m$ 的整数 $x$ ， $f(x)$ 有 $C_{10+m-1}^{m-1}$ 种取值。

相当于有 $10$ 个不同的箱子， $m$ 个相同的小球，每个箱子可以为空，问有多少种方案。

通过插板法知道 $f(x)$ 的取值种数不多，所以我们可以爆搜枚举 $m$ 和 $f(x)$ 通过贪心和康托展开求出问题答案的数量。

最后通过费马小定理求逆元算出答对问题的概率。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int __OneWan_2024 = [](){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	return 0;
}();
int m;
i64 n, k;
array<i64, 12> pow10{}, fact{};
array<int, 10> cnt{};
array<i64, 10> p{};
const i64 mod = 998244353;
i64 work(i64 sum) {
	i64 R = min({n, max(pow10[m - 1] - 1, sum), pow10[m] - 1});
	vector<int> num(m);
	i64 temp = R;
	for (int i = 0 ; i < m ; i++) {
		num[i] = temp % 10;
		temp /= 10;
	}
	reverse(begin(num), end(num));
	array<int, 10> cur = cnt;
	i64 rk = 0;
	for (int i = 0 ; i < (int) num.size() ; i++) {
		i64 cur_ans = 1;
		for (int j = 0 ; j < 10 ; j++) {
			cur_ans *= fact[cur[j]];
		}
		for (int j = 0 ; j < num[i] ; j++) {
			if (cur[j] == 0) continue;
			cur_ans /= fact[cur[j]];
			cur_ans *= fact[cur[j] - 1];
			rk += fact[(int) num.size() - i - 1] / cur_ans;
			cur_ans *= fact[cur[j]];
			cur_ans /= fact[cur[j] - 1];
		}
		if (cur[num[i]] == 0) return rk % mod;
		cur[num[i]]--;
	}
	return (rk + 1) % mod;
}
i64 ans = 0;
void dfs(int len, int cur, i64 sum) {
	if (len == m) {
		ans = (ans + work(sum + k)) % mod;
		ans = (ans - work(sum - k - 1) + mod) % mod;
		return;
	}
	for (int i = cur ; i <= 9 ; i++) {
		cnt[i]++;
		dfs(len + 1, i, sum + p[i]);
		cnt[i]--;
	}
}
i64 qpow(i64 a, i64 b = mod - 2, i64 res = 1) {
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int main() {
	fact[0] = pow10[0] = 1;
	for (int i = 1 ; i <= 11 ; i++) {
		pow10[i] = pow10[i - 1] * 10;
		fact[i] = fact[i - 1] * i;
	}
	for (int i = 0 ; i <= 9 ; i++) {
		p[i] = 1;
	}
	cin >> n >> k;
	int mx = log10(n) + 1;
	for (int i = 1 ; i <= mx ; i++) {
		for (int j = 0 ; j <= 9 ; j++) {
			p[j] *= j;
		}
		m = i;
		dfs(0, 0, 0);
	}
	cout << ans * qpow(n % mod) % mod;
	return 0;
}

解法二

$|x-f(x)|\leq k$

我们可以选择对 $x$ 进行拆位，此时我们需要先枚举位数 $m$ 。

当 $m=4$ 的时候， $1234-f(1234)=(1200-f(12))+(34-f(34))$

令左半为 $a$ ，右半为 $b$ ，那么我们只需要找 $|a+b|\leq k$ 即可。这是一个经典的问题。

$a,b$ 怎么处理，因为合位之后需要有 $m$ 位，而且前半是不能含有前导0的，所以 $a$ 的位数固定了，那么 $b$ 的位数是不固定的，因为 $b$ 可以有前导0。暴力计算 $a,b$ 存进数组，对 $b$ 数组排序，二分找 $|a+b|\leq k$ 的个数就好了。

需要注意的是，当 $m$ 恰好等于 $\log_{10}(n)+1$ 的时候， $a$ 恰好是前缀，这个时候 $b$ 是不能选择大于后缀的，因为要保证 $a$ $b$ 拼起来 $\leq n$ 。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int __OneWan_2024 = [](){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	return 0;
}();
const i64 P = 998244353;
i64 p[11][12];
i64 qpow(i64 a, i64 b = P - 2, i64 res = 1) {
	while (b) {
		if (b & 1) res = res * a % P;
		a = a * a % P;
		b >>= 1;
	}
	return res;
}
int main() {
	for (int i = 0 ; i <= 10 ; i++) {
		p[i][0] = 1;
	}
	for (int i = 1 ; i <= 11 ; i++) {
		for (int j = 0 ; j <= 10 ; j++) {
			p[j][i] = p[j][i - 1] * j;
		}
	}
	i64 n, k;
	cin >> n >> k;
	int m = log10(n) + 1;
	i64 ans = min(n, 9LL);
	for (int i = 2 ; i <= m ; i++) { // 枚举位数
		int sqrL = (i + 1) / 2, sqrR = i - sqrL;
		vector a(2, vector<i64>());
		for (int L = p[10][sqrL - 1] ; L < p[10][sqrL] ; L++) { // 枚举左侧的数
			int temp = L;
			int cnt = 0;
			i64 res = L * p[10][sqrR];
			do {
				res -= p[temp % 10][i];
				temp /= 10;
				cnt++;
			} while (temp);
			if (i == m) {
				if (L > n / p[10][m - cnt]) continue;
				if (L == n / p[10][m - cnt]) a[0].push_back(res);
				else a[1].push_back(res);
			} else {
				a[1].push_back(res);
			}
		}
		vector b(2, vector<i64>());
		for (int R = 0 ; R < p[10][sqrR] ; R++) { // 枚举右侧的数
			int temp = R;
			int cnt = 0;
			i64 res = R;
			do {
				res -= p[temp % 10][i];
				temp /= 10;
				cnt++;
			} while (temp);
			if (i == m) {
				if (R <= n % p[10][m - cnt]) b[0].push_back(res);
				b[1].push_back(res);
			} else {
				b[1].push_back(res);
			}
		}
		for (int j = 0 ; j <= 1 ; j++) {
			sort(begin(b[j]), end(b[j]));
		}
		for (int j = 0 ; j <= 1 ; j++) {
			for (auto &x : a[j]) {
				int R = 0, L = 0;
				auto it1 = upper_bound(begin(b[j]), end(b[j]), k - x);
				if (it1 != begin(b[j])) {
					it1--;
					if (*it1 < (-k - x)) continue;
					R = it1 - begin(b[j]) + 1;
				}
				auto it2 = lower_bound(begin(b[j]), end(b[j]), (-k - x));
				if (it2 != begin(b[j])) {
					it2--;
					L = it2 - begin(b[j]) + 1;
				}
				ans = (ans + R - L) % P;
			}
		}
	}
	cout << ans * qpow(n % P) % P;
	return 0;
}