最近怎么一直打比赛啊，都没有练习的。

要论比赛体验，这场无疑是糟糕透顶，听说是一个小时临时拼凑的，题目没有一道是正常的，前面三道出锅，最后一道搬前天 cf 原题。

但其实题目质量还是不错的，可做性也挺高——但还是做不出来。

A

有点意思的结论题，但结论还是比较容易发现的。

一个全 $0$ 矩阵，每次用这样形状的其中一块全部异或上 $1$, 能否全部变成 $1$。

证明也挺简单：首先若两个一起用，那么就是角上四个，肯定可以把长宽都是 $4$ 的倍数的铺满而其它铺不了。若不是两个一起用，那么一定会留下缺口且无法修补，所以判断是否都是 $4$ 的倍数就可以了。

B

给定一个矩阵，从左上到右下的路径组成的序列中!有多少个长度为 $k$ 的上升子序列。

开始想的是 $f[i][j][k][x]$ 表示到 $(i, j)$, 长度为 $k$, 以 $x$ 结尾的答案，然后觉得这样难以转移，于是就把它前缀和掉，变成表示以小于等于 $x$ 结尾的。后来发现这样更难转移。

本想着每个两种情况就行了，霹雳扒拉写出代码，然后样例都没有过。

两种情况中就是把当前选上和不把当前选上，这里犯了两个很傻的错误：

1. 根本没有判断 $x$ 是不是大于等于 $a[i][j]$，也就是这一位能不能选上去。
2. $k=1$ 的转移漏了一种把当前选上的。

第一个问题判断一下很好解决，但对于第二个问题，需要思考一下了，当前选上到底会产生几种方案？是 $1$ 种，$2$ 种还是能从几个地方转移过来就几种？

其实都不是，因为只取这一个，所以从头到这里的每一条路径都可以产生一个贡献，得先 dp 预处理出有几条路径到这里。

最后是比赛后又调了很久才过的，其实原来的状态写起来会简单的很多，特别是避开了 $k=1$ 且当前选上的那个大坑。

不过最终还是要怪自己没有考虑清楚。轻敌了。无论什么样的题目都要确保考虑清楚了一个算法再去写啊！

代码。

#include <cstdio>
#include <cstring>
#define int long long
const int N = 55, p = 1000000007;
int n, m, a[N][N], f[N][N][N][N], k, C[N][N];
void dfs(int i, int j, int k, int x) {
	if(f[i][j][k][x] != -1) return;
	f[i][j][k][x] = 0;
	if(k == 1) {
		if(i == 1 && j == 1) f[i][j][k][x] = (x >= a[i][j]);
		if(i-1 >= 1) {
			dfs(i-1, j, k, x), f[i][j][k][x] += f[i-1][j][k][x], f[i][j][k][x] %= p;
			if(x >= a[i][j]) f[i][j][k][x] += C[i-1][j], f[i][j][k][x] %= p;
		}
		if(j-1 >= 1) {
			dfs(i, j-1, k, x), f[i][j][k][x] += f[i][j-1][k][x], f[i][j][k][x] %= p;
			if(x >= a[i][j]) f[i][j][k][x] += C[i][j-1], f[i][j][k][x] %= p;
		}
		return;
	}
	if(i-1 >= 1) {
		if(x >= a[i][j]) dfs(i-1, j, k-1, a[i][j]-1), f[i][j][k][x] = (f[i][j][k][x] + f[i-1][j][k-1][a[i][j]-1]) % p;
		dfs(i-1, j, k, x);
		f[i][j][k][x] = (f[i][j][k][x] + f[i-1][j][k][x]) % p;
	}
	if(j-1 >= 1) {
		if(x >= a[i][j]) dfs(i, j-1, k-1, a[i][j]-1), f[i][j][k][x] = (f[i][j][k][x] + f[i][j-1][k-1][a[i][j]-1]) % p;
		dfs(i, j-1, k, x);
		f[i][j][k][x] = (f[i][j][k][x] + f[i][j-1][k][x]) % p;
	}
}
signed main() {
	scanf("%lld%lld%lld", &n, &m, &k);
	memset(f, -1, sizeof f);
	for(int i = 1; i <= n; i++)	
		for(int j = 1; j <= m; j++) scanf("%lld", &a[i][j]);
	C[0][1] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			C[i][j] = (C[i][j-1] + C[i-1][j]) % p;
	dfs(n, m, k, 50);
	printf("%lld", f[n][m][k][50]);
	return 0;
}

C

题目经过一些比较显然的转换大概是这样：

$n\times m$ 的矩阵选定一个起始点选定 $l$ 和 $r$, 求在 $l$ 和 $r$ 列之间每一行的最大值的和减去 $pos_r -pos_l$ 的最大值。

转换过程比较简单，但还是花了一会儿才想到，感觉旁边坐着个人比赛效率就直线下降。

暴力 $\mathcal O(n^2m)$ 能获得 $80$ 分。

然后就没辙了，想着那个 $m$ 怎么消得掉，于是想着去掉 $n$, 半天未果，这端点显然没有单调性，去不掉。

其实就是要去掉 $m$, 还是一个比较套路的处理最大值和的方式：考虑每一个贡献的区间。

其实想到这个就挺简单的了，用单调栈可以处理出这样的一个区间，然后令 $sum[i][j]$ 表示 $i$ 列和 $j$ 列间的最大值的和，统计每个 $a[i][j]$ 的贡献就可以了。

这种矩阵中一块加上而又可以离线一次性处理完的使用二维差分就再合适不过了，树状数组都不用。

代码。

#include <stack>
#include <cstdio>
#include <algorithm>
#define int long long
const int N = 5005, M = 305;
int n, m, pos[N], a[M][N], L[M][N], R[M][N], sum[N][N], ans;
signed main() {
	freopen("demon.in", "r", stdin);
	freopen("demon.out", "w", stdout);

	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &pos[i]);
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++) scanf("%lld", &a[i][j]);
	for(int i = 1; i <= m; i++) {
		std::stack<int> st;
		for(int j = 1; j <= n; j++) {
			while(!st.empty() && a[i][st.top()] < a[i][j]) st.pop();
			if(!st.empty()) L[i][j] = st.top()+1; else L[i][j] = 1;
			st.push(j); 
		}
		while(!st.empty()) st.pop();
		for(int j = n; j >= 1; j--) {
			while(!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
			if(!st.empty()) R[i][j] = st.top()-1; else R[i][j] = n;
			st.push(j);
		}
	}
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++) 
			sum[L[i][j]][j] += a[i][j], sum[j+1][R[i][j]+1] += a[i][j],
			sum[L[i][j]][R[i][j]+1] -= a[i][j], sum[j+1][j] -= a[i][j];
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= n; j++)
			sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
	for(int l = 1; l <= n; l++)
		for(int r = 1; r <= n; r++)
		 	ans = std::max(sum[l][r] - pos[r] + pos[l], ans);
	printf("%lld", ans);
	return 0;
}

D

放两天前的原题过分了。当我们不打 cf ?

其实这场比赛带给我的提升还是挺大的，搬题人临时受命导致比赛质量低下也可以理解。

赛后订正的时候还是太浮躁了。穿着校服坐在这，仿佛谢兔兔的 “主要是静得下心来” “学思学研” “错的地方自己查（察）” 的教诲又回响在耳畔了。xhf 和 w策 不在安静了很多，但我还是够吵的。