标签：int max 蓝桥 read 2022 mul 竹子 main

C - 刷题统计

https://www.luogu.com.cn/problem/P8780

签到题，先大跨步对每周的题数取模，然后暴力计算最后一周需要做的题。

int main() {
	i64 a = read(), b = read(), n = read();
	i64 ans = n / (5 * a + 2 * b) * 7, rest = n % (5 * a + 2 * b);
	for (int i = 1; i <= 5; i++) {
		if (rest <= 0) break; rest -= a; ans++;
	}
	for (int j = 1; j <= 2; j++) {
		if (rest <= 0) break; rest -= b; ans++;
	}
	printf("%lld\n", ans);
	return 0;
}

D - 修建灌木

https://www.luogu.com.cn/problem/P8781

签到题，考虑每棵灌木需要等待的时间只有爱丽丝经过这棵灌木再从两边回来两种情况，取 \(max\) 即可。

int main() {
	int n = read();
	for (int i = 1; i <= n; i++) {
		printf("%d\n", 2 * std::max(i - 1, n - i));
	}
	return 0;
}

E - X 进制减法

https://www.luogu.com.cn/problem/P8782

进制决定了该位之后的数的系数，为了使最后的结果最小，那么每一位的进制就要尽量小。

const int mod = 1e9 + 7;

int main() {
	int M = read(), n1, n2;
	n1 = read(); int a[n1 + 1]; memset(a, 0, sizeof(a));
	for (int i = n1; i >= 1; i--) a[i] = read();
	n2 = read(); int b[n2 + 1]; memset(b, 0, sizeof(b));
	for (int i = n2; i >= 1; i--) b[i] = read();
	int n = std::max(n1, n2);
	i64 mul[n + 1]; mul[0] = 1;
	for (int i = 1; i <= n; i++) {
		if (i > n1) {
			mul[i] = mul[i - 1] * std::max(2, b[i] + 1) % mod; continue;
		}
		if (i > n2) {
			mul[i] = mul[i - 1] * std::max(2, a[i] + 1) % mod; continue;
		}
		mul[i] = mul[i - 1] * std::max(2, std::max(a[i] + 1, b[i] + 1)) % mod;
	}
	i64 A = 0, B = 0;
	for (int i = 1; i <= n1; i++) A = (mul[i - 1] * a[i] + A) % mod;
	for (int i = 1; i <= n2; i++) B = (mul[i - 1] * b[i] + B) % mod;
	printf("%lld", (A - B + mod) % mod);
	return 0;
}

F - 统计子矩阵

https://www.luogu.com.cn/problem/P8783

考虑暴力，枚举子矩阵的对角线，然后用前缀和优化计算，设 \(n\) 和 \(m\) 同级，复杂度 \(O(n^4)\)

如何优化？一维空间下我们可以通过双指针达到 \(O(n)\) 的复杂度，二维的话我们可以对某一维的端点进行枚举，确定之后即可对其降维，另一维使用双指针进行计算即可，复杂度 \(O(n^3)\)。

int main() {
	int n = read(), m = read(), k = read();
	i64 a[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) a[i][j] = read();
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] += a[i - 1][j];
		}
	}
	i64 ans = 0;
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			int now = 0, x = 1;
			for (int i = 1; i <= m; i++) {
				now += a[r][i] - a[l - 1][i];
				while (now > k) {
					now -= a[r][x] - a[l - 1][x]; x++;
				}
				ans += i - x + 1;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

G - 积木画

https://www.luogu.com.cn/problem/P8784

考虑每种状态只有可能是凸出一块，或者没有凸出，记 \(f_{i, 0}\) 为前 \(i\) 列填满的方案数，\(f_{i, k}\) 表示前 \(i - 1\) 列填满，第 \(i\) 列的第 \(k\) 行没填满的方案数，转移方程为

\[\begin{aligned} f_{i, 0} &= f_{i - 2, 0} + f_{i - 1, 1} + f_{i - 1, 2} + f_{i - 1, 0} \\ f_{i, 1} &= f_{i - 1, 2} + f_{i - 2, 0} \\ f_{i, 2} &= f_{i - 1, 1} + f_{i - 2, 0} \end{aligned} \]

int main() {
	int n = read(), f[n][3];
	memset(f, 0, sizeof(f));
	f[0][0] = f[1][0] = 1;
	for (int i = 2; i <= n; i++) {
		f[i][0] = (1ll * f[i - 2][0] + f[i - 1][1] + f[i - 1][2] + f[i - 1][0]) % mod;
		f[i][1] = (1ll * f[i - 1][2] + f[i - 2][0]) % mod;
		f[i][2] = (1ll * f[i - 1][1] + f[i - 2][0]) % mod;
	}
	printf("%d\n", f[n][0]);
	return 0;
}

I - 李白打酒加强版

https://www.luogu.com.cn/problem/P8786

记 \(f_{i, j, k}\) 表示李白经历了 \(i\) 个店，\(j\) 个花后剩 \(k\) 斗酒的方案数

\[f_{i, j, k} = f_{i - 1, j, k / 2} + f_{i, j - 1, k + 1} \]

若 \(k\) 为奇数则没有前一项。

const int mod = 1e9 + 7;

int main() {
	int n = read(), m = read(), f[n + 1][m + 1][2 * m + 1];
	memset(f, 0, sizeof(f));
	f[0][0][2] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= m; k++) {
				if (i && k % 2 == 0) f[i][j][k] += f[i - 1][j][k / 2], f[i][j][k] %= mod;
				if (j) f[i][j][k] += f[i][j - 1][k + 1], f[i][j][k] %= mod;
			}
		}
	}
	printf("%d\n", f[n][m - 1][1]);
	return 0;
}

J - 砍竹子

https://www.luogu.com.cn/problem/P8787

考虑每个竹子砍一次 \(\Big\lfloor\sqrt{\lfloor\frac{H}{2}\rfloor + 1}\Big\rfloor\leq \lfloor\frac{H}{2}\rfloor\)，于是一个竹子最多 \(\log_2 H\) 次就能被砍完，若不存在魔法暴力砍竹子也可以用 \(O(n \log_2 H)\) 复杂度计算次数。

考虑使用魔法的最优解，我们希望每次砍竹子，都能将连续的，长度相同的竹子一次性砍掉。

我们可以考虑维护相同高度且连续的竹子的区间，由于竹子不会长高，所以我们每次砍掉最高的竹子一定是最优的，砍掉当前最高的竹子后，判定其和旁边的竹子高度是否相同，若相同则合并这两个区间，我们可以用堆维护当前的竹子，并记录其区间信息。

为了能快速找到其相邻的区间，我们可以第二关键字设置为左端点或右端点，这样我们再次取堆顶即可判定是否合并。

int main() {
	int n = read(); i64 a[n + 1];
	for (int i = 1; i <= n; i++) a[i] = read();
	i64 ans = 0;
	while (1) {
		i64 max = 0; int l = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] > max) max = a[i], l = i;
		}
		if (max == 1) break; int r = l;
		while (r < n && a[r + 1] == a[l]) r++;
		ans++;
		for (int i = l; i <= r; i++) a[i] = sqrt(a[i] / 2 + 1);
	}
	printf("%lld", ans);
	return 0;
}

标签：int,max,蓝桥,read,2022,mul,竹子,main
From： https://www.cnblogs.com/zrzring/p/lanqiao-2022-provence-B.html

蓝桥杯 2022 省 B