20220708 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

二分答案，整除分块，dp + 推结论，曼哈顿转切比雪夫 + 4 维区间 dp

# A. 棍子 sticks

~~sticks 写成了 stick ，遗憾爆零 /kk~~

签到题，就是一道二分答案板子。

不知道是什么原因，大样例卡精度死循环，于是直接 check 了 $2e6$ 次，喜提最劣解。

不得不佩服 $\text{lj}$ 神机，全场就 $fls$ 一个人有分 orz

	#include <bits/stdc++.h>
	#define eps 1e-9
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 60;
	int n, m, k;
	double a[N], mx;

	inline bool check(double mid){
	int cnt = 0, tot = 0;
	for(int i = 1; i <= n; ++i){
	if(tot == m) {cnt += (a[i] >= mid); continue;}
	int tmp = floor(a[i] / mid);
	if(tmp - 1 + tot >= m) cnt += (m - tot) + 1, tot = m;
	else if(tmp > 0) cnt += tmp, tot += (tmp - 1);
	}
	return cnt >= k && tot <= m;
	}

	signed main(){
	// freopen("sticks.in", "r", stdin);
	// freopen("sticks.out", "w", stdout);
	n = read(), m = read(), k = read();
	for(int i = 1; i <= n; ++i) scanf("%lf", &a[i]), mx = max(mx, a[i]);
	double l = 0, r = mx, res = 0;
	for(int i = 1; i <= 2e6; ++i){
	double mid = (l + r) / 2;
	// cout << l << " " << r << " " << mid << " " << r - l << " " << check(mid) << endl;
	if(check(mid)) res = mid, l = mid;
	else r = mid;
	}
	printf("%.12lf\n", res);
	return 0;
	}

# B. 数组 count

看题 $\text{10min}$ 后就想到了整除分块，结果还是想假了，把 $C_{min}$ 和 $C_{max}$ 放到一块计算了，不知道当时脑子是怎么想的。

关键样例还都过了？我直接缓缓打出一个？

还有 $\text{subtask}$ ，最后自然是喜提一个 0 分。

思路比较简单，差分的思想，算 $C_{max}$ 的答案减去 $C_{min} - 1$ 的答案。对 $A$ 整除分块，算出 $\frac CA$ ，跟 $B$ 的范围取个交即可。

	#include <bits/stdc++.h>
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	int A1, A2, B1, B2, C1, C2;
	int ans;

	inline void solve_1(){
	for(int i = A1; i <= A2; ++i){
	int t1 = ceil(1.0 * C1 / i), t2 = C2 / i;
	cout << t1 << " " << t2 << endl;
	ans += max(0ll, min(t2, B2) - max(t1, B1) + 1);
	}
	}

	inline int solve(int n){
	int res = 0;
	if(!n) return 0;
	for(int l = A1, r = 0; l <= A2; l = r + 1){
	if(n / l <= 0) break;
	r = min(A2, n / (n / l));
	int t = n / l;
	if(t >= B1) res += (min(B2, t) - B1 + 1) * (r - l + 1);
	}
	return res;
	}

	signed main(){
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%lld%lld%lld%lld%lld%lld", &A1, &A2, &B1, &B2, &C1, &C2);
	write(solve(C2) - solve(C1 - 1)), puts("");
	return 0;
	}

# C. 十一 eleven

~~next_permutation 谁不会啊，喜提 20 分。~~

观察到部分分：每个数字位数相同。

考场上实在是想不出来这玩意有啥用 /kk

~~稍微模拟一下可知~~：

对于偶数位数的数：数字 $x$ 经过这个数之后形成的数一定是 $(x + ?) \bmod 11$ 这样形式的。
对于奇数位数的数：数字 $x$ 经过之后一定是 $(x - ?) \bmod 11$ 这样子的。

先考虑部分分。

如果所有数都是偶数位数的，那么最终的数为：

$(((0 + a) \bmod 11 + b) \bmod 11)\cdots$

所以我们只需要确定一下所有数的和是否能整除 11 即可，答案就是 $n!$ 。

对于奇数位数，表达式为：

$(c - (b - (0 + a)))$

展开之后为：

$- 0 + a - b + c$

不难发现这东西正负号是交替的，所以设 $f_{i, j, k}$ 表示 $i$ 个正， $j$ 个负，这些数的和 $\bmod 11$ 的值为 $k$ 时的方案数。

转移的时候对于新加进来的数放到正数位置还是负数位置分别考虑：

有转移方程：

$f_{i + 1, j, k + nxt_p} += f_{i, j, k} \\ f_{i, j + 1, k - nxt_p} += f_{i, j, k}$

但是一个奇数位数的数展开之后的正负号个数是固定的，分别为 $cnt_z, cnt_f$ （自己推一下吧）

部分分就做完了。

再来看满分如何做。

我们对偶数位数的数也进行一次上述 $\text{dp}$ ，设为 $g_{i, j, k}$ 。然后思考如何将两个 $\text{dp}$ 数组合并。

我们考虑把偶数位数的数插入到奇数位数的数中间，所以有些偶数位数的数对答案的贡献是正，有些是负的。

枚举有多少个是正的，多少个是负的。

$\text{dp}$ 值贡献为 $f_{cnt_z, cnt_f, 11 - k} \times g_{i, cnt - i, k}$ ，但是偶数位数的数还有很多种放法。

对于奇数位数中的正数：
有 $cnt_z!$ 种排列方式，然后新插入一个数，有 $cnt_z$ 个位置，对于插入的第二个数，有 $cnt_z + 1$ 个位置，以此类推。
所以总方案数为 $(cnt_z + i - 1)! \times cnt_z$
对于计数位数中的负数：
实际上是有 $cnt_f + 1$ 个位置的，因为还要加上 $-0$ 的位置，例子见上面。所以放第一个数时就有 $cnt_f + 1$ 个位置，第二个数有 $cnt_f + 2$ 个位置，以此类推。
总方案数为 $(cnt_f + cnt - i)!$

别的就没了，具体看代码吧。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 60;
	const int mod = 1e9 + 7;
	int n, c1, c2, cz, cf, cnt;
	char s[N];
	int nxt1[N], nxt2[N];
	int f[N][N][15], g[N][N][15];
	int fac[N], ifac[N];

	inline void add(int &x, int y) {x = (x + y >= mod) ? x + y - mod : x + y;}
	inline int add(int x) {return (x % 11 + 11) % 11;}
	inline int sub(int x) {return x < 0 ? x + 11 : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	inline int qpow(int a, int b){
	int res = 1;
	while(b){
	if(b & 1) res = 1ll * res * a % mod;
	a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
	}

	inline void init(){
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
	}

	inline int C(int n, int m){
	return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), init();
	for(int i = 1, len, x = 0; i <= n; ++i, x = 0){
	scanf("%s", s + 1), len = strlen(s + 1);
	for(int j = 1; j <= len; ++j) x = (x * 10 + s[j] - '0') % 11;
	if(len & 1) nxt1[++c1] = x;
	else nxt2[++c2] = x;
	}

	f[0][0][0] = 1;
	for(int p = 1; p <= c1; ++p)
	for(int i = 0; i < p; ++i){
	int j = p - i - 1;
	for(int k = 0; k < 11; ++k){
	add(f[i + 1][j][add(k + nxt1[p])], f[i][j][k]);
	add(f[i][j + 1][add(k - nxt1[p])], f[i][j][k]);
	}
	}

	g[0][0][0] = 1;
	for(int p = 1; p <= c2 + 1; ++p)
	for(int i = 0; i < p; ++i){
	int j = p - i - 1;
	for(int k = 0; k < 11; ++k){
	add(g[i + 1][j][add(k + nxt2[p])], g[i][j][k]);
	add(g[i][j + 1][add(k - nxt2[p])], g[i][j][k]);
	}
	}

	if(!c1){
	int x = 0;
	for(int i = 1; i <= n; ++i) x = add(x + nxt2[i]);
	if(!x) write(fac[n]), puts("");
	else puts("0");
	return 0;
	}

	cf = c1 / 2, cz = c1 - cf;
	int ans = 0;
	for(int i = 0; i <= c2; ++i)
	for(int j = 0; j < 11; ++j){
	int res = 1ll * f[cz][cf][add(11 - j)] * g[i][c2 - i][j] % mod;
	add(ans, mul(mul(res, fac[cf + c2 - i]), mul(fac[cz + i - 1], cz)));
	}
	write(ans), puts("");
	return 0;
	}

# D. 棋盘 chess

一道区间 $\text{dp}$ 板题，然而考场上并没有想到 /kk

首先曼哈顿距离转切比雪夫距离，坐标从 $(x, y)$ 变成了 $(x - y, x + y)$ 。

然后所求距离从 $|x_1 - x_2| + |y_1 - y_2|$ 变成了 $\max(x_1-x_2,y_1-y_2)$

设 $f_{l, r, d, u}$ 表示还剩这个矩形时，消掉这个矩形内所有点的最小代价。

使用记忆化搜索实现，每次转移的时候从四条边分别往里收缩一个单位即可。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 20;
	const int inf = 1e9;
	int n;
	char s[N][N];
	int a[N][N], f[N][N][N][N];

	inline int dfs(int l, int r, int d, int u){
	if(~f[l][r][d][u]) return f[l][r][d][u];
	if(l == r && d == u) return 0;
	int res = inf;
	if(d < u){
	int sd = 0, su = 0;
	for(int i = l; i <= r; ++i){
	if(a[i][u]) su += max(u - d, max(i - l, r - i));
	if(a[i][d]) sd += max(u - d, max(i - l, r - i));
	}
	res = min(res, min(sd + dfs(l, r, d + 1, u), su + dfs(l, r, d, u - 1)));
	}
	if(l < r){
	int sl = 0, sr = 0;
	for(int i = d; i <= u; ++i){
	if(a[l][i]) sl += max(r - l, max(i - d, u - i));
	if(a[r][i]) sr += max(r - l, max(i - d, u - i));
	}
	res = min(res, min(sl + dfs(l + 1, r, d, u), sr + dfs(l, r - 1, d, u)));
	}
	return f[l][r][d][u] = res;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = 8;
	for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= n; ++j)
	if(s[i][j] == '#') a[i + j - 1][i - j + n] = 1;
	memset(f, -1, sizeof(f));
	write(dfs(1, 15, 1, 15)), puts("");
	return 0;
	}

# A. 棍子 sticks

# B. 数组 count

# C. 十一 eleven

# D. 棋盘 chess

Siunaus 计数专题

20220722