专栏文章

P12650 [KOI 2024 Round 2] 双 v 字形涂色

__JF_殉情
P12650题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minxu80w
此快照首次捕获于
2025/12/02 10:07
3 个月前
此快照最后确认于
2025/12/02 10:07
3 个月前
查看原文
Link
压力！
好难写的模拟/tuu，思路还行。
分类讨论两个 V 是否相交，只会相交，不相交看了尺子姐姐的题解才会呜呜呜。
  • 先讲相交的情况。
第一种是形如样例，给出的近似 W 的形状，我们不妨考虑枚举中间的那个顶端，思考两边的最值怎么取。
来看右边怎么取，实际上是这样的一个问题：
对于 (i,j),(i+1,j+1),…(i+x,j+x)(i,j),(i+1,j+1),\dots(i+x,j+x) 这一段连续的白色格子，定义 gi,jg_{i,j} 为每个白色格子往右上延续的长的白格数量，定义 fi,j=max⁡i+x≤n,j+x≤mgi+x,j+x+xf_{i,j}=\max_{i+x\le n,j+x\le m }{g_{i+x,j+x}+x}。
gg 跑一次预处理求出，问题是 ff 怎么求。
很经典的问题了吧，这个东西是有单调性的。
对于两个位置 (i+x,j+x)(i+x,j+x) 和 (i+x′,j+x′)(i+x',j+x') 而言 (x′>x)(x'>x)，(i,j)→(i+x−1,j+x−1)(i,j)\rightarrow (i+x-1,j+x-1) 这一段贡献是一样的，那我们只用把 (i+x′,j+x′)(i+x',j+x') 平移到 (i+x,j+x)(i+x,j+x)，比较谁更优即可。
这个人一开始用 deque 维护，但是 9×1069\times 10^6 个，用 vector 维护即可。
对于左半部分的处理是类似的。
还有一种相交情况形如：
这个是好处理的，直接维护前缀 max⁡\max 即可。
  • 不相交的情况。
观察奇偶性，发现若 (i,j),(i−1,j−1),(i−1,j+1)…(i,j),(i-1,j-1),(i-1,j+1)\dots 为白色，那么这些点坐标和的奇偶性不变。
那么可以枚举 V 底端那个点，两个点奇偶性不一样，说明必然不相交。
还有一种情况是包含，这种就考虑一个 Bi,jB_{i,j} 表示以 (i,j)(i,j) 为底部点，能完全包含最大的 V 的格子数量，递推式显然：
Bi,j=max⁡{Bi−1,j,Bi−1,j−1,Bi−1,j+1,vali,j}B_{i,j}=\max\{B_{i-1,j},B_{i-1,j-1},B_{i-1,j+1},val_{i,j}\}
其中 vali,jval_{i,j} 表示当前点为底部点能最大构成 V 的格子数。
最后一种情况，就是注意到构成 V 的所有点坐标，右边的边的 i+ji+j 是定值，左边的边 i−ji-j 是定值，那么分别以两种情况作为分割线，分左右统计即可。
难写到爆炸。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N =3001;
char ch[N][N];
struct node{
	int i,j,val; 
};
vector<node> q[9000001]; 
int predis1[N<<1],predis[N<<1],sum1[N][N],sum2[N][N],tot,LU_Mx[N][N],RU_Mx[N][N],id[N][N][2];
int num1,num2,ans,n,m,RU[N][N],LU[N][N],Now[N][N],B[N][N];
int main(){
//	freopen("P12650_36.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	cin>>ch[i][j];
	// 1,2
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			RU[i][j]=RU[i-1][j+1]+1,LU[i][j]=LU[i-1][j-1]+1,Now[i][j]=RU[i][j]+LU[i][j]-1;
			if((i+j)%2==0)	num1=max(num1,Now[i][j]); else num2=max(num2,Now[i][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			B[i][j]=max(max(B[i-1][j],max(B[i-1][j-1],B[i-1][j+1])),Now[i][j]);
			ans=max(ans,B[i-1][j]+Now[i][j]);
		}
		
//	cout<<B[3][1]<<endl;
	ans=max(ans,num1+num2);
	
	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	predis[i+j]=max(predis[i+j],Now[i][j]),predis1[i-j+m]=max(predis1[i-j+m],Now[i][j]);
	
	for(int i=1;i<=n+m;i++)	predis[i]=max(predis[i],predis[i-1]);
	for(int i=1;i<=n+m-1;i++)	predis1[i]=max(predis1[i],predis1[i-1]);	

	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			int now=i+j-LU[i][j]*2;
			ans=max(ans,Now[i][j]+predis[now]);
			
			int now1=i-j+m-2*RU[i][j];
			ans=max(ans,Now[i][j]+predis1[now1]);
	}
		
	
	// 3 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			RU_Mx[i][j]=max(RU_Mx[i-1][j-1],RU[i][j]),LU_Mx[i][j]=max(LU_Mx[i-1][j+1],LU[i][j]);
			ans=max(ans,RU_Mx[i-1][j-1]-1+Now[i][j]);
			ans=max(ans,LU_Mx[i-1][j+1]-1+Now[i][j]);
		}
	// 4  RU:1 LU:0 
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			
			// LU
			if(ch[i-1][j-1]=='1'){
				int now=id[i-1][j-1][0];
				while(!q[now].empty()&&RU[i][j]+(i-q[now].back().i)>=q[now].back().val)	q[now].pop_back();
				q[now].push_back({i,j,RU[i][j]}),id[i][j][0]=id[i-1][j-1][0];
			}
			else id[i][j][0]=++tot;
			
			// RU
			
			if(ch[i-1][j+1]=='1'){
				int now=id[i-1][j+1][1];
				while(!q[now].empty()&&LU[i][j]+(i-q[now].back().i)>=q[now].back().val)	q[now].pop_back();
				q[now].push_back({i,j,LU[i][j]}),id[i][j][1]=id[i-1][j+1][1];
			}
			else id[i][j][1]=++tot;	
		}
	
	
	
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			if(ch[i-1][j-1]=='0'||(i-1<1)||(j-1<1)){
				int now=id[i][j][0],lsti=i,lstj=j;
				for(int l=0;l<q[now].size();l++){
					int nowi=q[now][l].i,nowj=q[now][l].j;
					while(lsti<nowi){
						sum1[lsti][lstj]=Now[nowi][nowj]-LU[lsti-1][lstj-1];
//						cout<<"0"<<' '<<lsti<<' '<<lstj<<' '<<sum1[lsti][lstj]<<endl;
						lsti++,lstj++;
					}
				} 
			}	
			
			if(ch[i-1][j+1]=='0'||(i-1<1)||(j+1>m)){
				int now=id[i][j][1],lsti=i,lstj=j;
				for(int l=0;l<q[now].size();l++){
					int nowi=q[now][l].i,nowj=q[now][l].j;
					while(lsti<nowi){
						sum2[lsti][lstj]=Now[nowi][nowj]-RU[lsti-1][lstj+1];
//						cout<<"1"<<' '<<lsti<<' '<<lstj<<' '<<sum2[lsti][lstj]<<endl;
						lsti++,lstj--;
					}
				}
			} 
		} 
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='0')	continue;
			ans=max(ans,sum1[i][j]+sum2[i][j]-1+max(LU[i][j],RU[i][j])-1);
//			if(ans==36)	cout<<i<<' '<<j<<' '<<sum1[i][j]<<' '<<sum2[i][j]<<endl,exit(0);
		} 
	
	
//	cout<<sum1[3][7]<<' '<<sum2[3][7]<<endl;
	
	cout<<ans<<endl;
	return 0;
}
/*
5 5
10101
01010
00100
01010
10101
*/

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...