模拟赛的题

SFlyer / 2023-08-08 / 原文

这里，模拟赛的题分 \(3\) 类：

\(1\)，我赛时 AC，但是认为有价值的。
\(2\)，我赛后独立 AC，认为有价值的。平常，是我脑子比赛时或多或少出了问题的。
\(3\)，我赛后看题解 AC，认为有价值的。

loj 3513

类别：\(2\)。

重新定义一下「平衡的」子集。设你选了 \(A_1,\cdots ,A_k\) 行，每行选 \(l_{A_i}\sim r_{A_i}\) 列（满足 \(3\)）。

都有草。
\(A_i\) 连续，满足 \([l_{A_{i}},r_{A_i}]∩[l_{A_{i-1}},r_{A_i-1}]\neq \emptyset\)。
\(l\) 先减后增，\(r\) 反之。

设 \(dp_{l,r,a,b}\) 表示这行选了 \([l,r]\)，\(l,r\) 现在是增还是减。

转移可以用（二维）前缀和优化。

点击查看代码

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 155;
const ll mod = 1e9+7;

int n;
char c[N][N];
int pf[N][N];
ll dp[N][N][2][2],sum[N][N][2][2];

ll s(int fa,int fb,int x1,int x2,int y1,int y2){
	return (mod+sum[x2][y2][fa][fb]-sum[x2][y1-1][fa][fb]-sum[x1-1][y2][fa][fb]+sum[x1-1][y1-1][fa][fb])%mod;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			cin>>c[i][j];
			pf[i][j]=pf[i][j-1]+(c[i][j]=='G');
		}
	}
	ll ans=0;
	for (int i=1; i<=n; i++){
		memset(sum,0,sizeof sum);
		for (int l=1; l<=n; l++){
			for (int r=1; r<=n; r++){
				for (int fa=0; fa<2; fa++){
					for (int fb=0; fb<2; fb++){
						sum[l][r][fa][fb]=sum[l-1][r][fa][fb]+sum[l][r-1][fa][fb]-sum[l-1][r-1][fa][fb]+dp[l][r][fa][fb];
						sum[l][r][fa][fb]%=mod;
						(sum[l][r][fa][fb]+=mod)%=mod;
					}
				}
			}
		}
		memset(dp,0,sizeof dp);
		for (int l=1; l<=n; l++){
			for (int r=l; r<=n; r++){
				if (pf[i][r]-pf[i][l-1]!=r-l+1){
					continue;
				}
				(dp[l][r][0][0]+=1)%=mod;
				(dp[l][r][0][0]+=s(0,0,l,r,l,r))%=mod;
				(dp[l][r][0][1]+=s(0,0,l,r,r+1,n))%=mod;
				(dp[l][r][0][1]+=s(0,1,l,r,r,n))%=mod;
				(dp[l][r][1][0]+=s(0,0,1,l-1,l,r))%=mod;
				(dp[l][r][1][0]+=s(1,0,1,l,l,r))%=mod;
				(dp[l][r][1][1]+=s(0,1,1,l-1,r,n))%=mod;
				(dp[l][r][1][1]+=s(1,0,1,l,r+1,n))%=mod;
				(dp[l][r][1][1]+=s(1,1,1,l,r,n))%=mod;
				(dp[l][r][1][1]+=s(0,0,1,l-1,r+1,n))%=mod;
				(ans+=dp[l][r][0][0]+dp[l][r][0][1]+dp[l][r][1][0]+dp[l][r][1][1])%=mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

// don't waste time!!!

待更！！！