zkx06111's Blog

//O(n^2)动态规划,f[i][j]前后分别表示以(i,j)为右下角的最多条数
//预处理出数组r[i][j]前后分别表示(i,j)左边和右边鱼的条数
//rn[i][j]表示(i,j)上方鱼的条数
//为了省空间只好回收利用数组了。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int ans=0,n,m,f[2505][2505];
unsigned short r[2505][2505],rn[2505][2505],pond[2505][2505];
int main(){
	scanf("%d%d",&n,&m);
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			scanf("%d",&pond[i][j]);
			r[i][j]=r[i][j-1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	for (int j=1;j<=n;++j)
		for (int i=1;i<=m;++i){
			rn[j][i]=rn[j-1][i]+pond[j][i];
			//printf("rm%d,%d=%d\n",j,i,rn[j][i]);
		}
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][1]=pond[j][1];
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			if (i==1 || j==1){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (r[i][j-1]==r[i][j-f[i-1][j-1]-1]
				&& rn[i-1][j]==rn[i-f[i-1][j-1]-1][j])
				f[i][j]=f[i-1][j-1]+1;
			//printf("f%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	memset(f,0,sizeof(f));
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][m]=pond[j][m];
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			r[i][j]=r[i][j+1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			if (i==1 || j==m){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (i==2 && j==3) {
				//printf("  %d,%d=%d\n",i-1,j,rn[i-1][j]);
				//printf("  %d,%d=%d\n",i-g[i-1][j+1]-1,j,rn[i-g[i-1][j+1]-1][j]);
			}
			if (r[i][j+f[i-1][j+1]+1]==r[i][j+1]
				&& rn[i-1][j]==rn[i-f[i-1][j+1]-1][j]){
				//printf("!!%d,%d!!\n%d,",i,j,f[i-1][j+1]);
				f[i][j]=f[i-1][j+1]+1;
			}	
			//printf("g%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	printf("%d",ans);
	
	return 0;
}

//史上写过最长的代码之一。。。80分，dfsp部分仍存在细节问题，不改了
//思路如下：求好数的个数只要求出不是好数的个数，
//求0-n不是好数只要连续1或0的个数小于等于2并且比n小就可以了
//这样就可以剪枝，大幅提高效率
#include <iostream>
#include <cstdio>
#define len(x) x[0]
using namespace std;

int mx[33];
long long low,up,ugl,ugu;

void dfs(int t,int lx,int ls){
	if (t==len(mx)){
		++ugu;
		return;
	}
	++ugu;
	if (lx==2 && ls==1){
		dfs(t+1,1,0);
		return;
	}
	if (lx==2 && ls==0){
		dfs(t+1,1,1);
		return;
	}
	if (ls==1){
		dfs(t+1,2,1);
		dfs(t+1,1,0);
		return;
	}
	dfs(t+1,1,1);
	dfs(t+1,2,0);
}

void dfsp(int t,int lx,int ls,bool flag){
	if (t>len(mx)){
		++ugu;
		return;
	}
	if (flag){
		if (ls==0 && lx==2){
			
			if (mx[t]==0) return;
			else{
				dfsp(t+1,1,1,1);
				return;
			}
		}
		if (ls==1 && lx==2){
			if (mx[t]==1){
				dfsp(t+1,1,0,0);
				return;
			}
			dfsp(t+1,1,0,1);
			return;
		}
		if (mx[t]==1){
			if (ls==0) dfsp(t+1,2,0,0);
			else{
				dfsp(t+1,2,1,1);
				dfsp(t+1,1,1,0);
			}
			return;
		}
		if (ls==0){
			dfsp(t+1,2,0,1);
			return;
		}
		dfsp(t+1,1,0,1);
		return;
	}
	if (ls==0 && lx==2){
		dfsp(t+1,1,1,0);
		return;
	}
	if (ls==1 && lx==2){
		dfsp(t+1,1,0,0);
		return;
	}
	if (ls==0){
		dfsp(t+1,1,1,0);
		dfsp(t+1,2,0,0);
		return;
	}
	dfsp(t+1,2,1,0);
	dfsp(t+1,1,0,0);
}

void conv(int x){
	len(mx)=0;
	while (x){
		mx[++len(mx)]=x%2;
		x/=2;
	}
	for (int i=1;i<=len(mx)/2;++i)
		swap(mx[i],mx[len(mx)-i+1]);
}

int main()
{
	cin>>low>>up;
	if (low<=5){
		ugl=low+1;
		goto u;
	}
	conv(low); good[1]=1;
	dfs(2,1,1);
	dfsp(2,1,1,1);
	ugl=ugu+1;
	for (int i=1;i<=len(mx)-2;++i)
		if (mx[i]==mx[i+1] && mx[i+2]==mx[i]){
			++ugl;break;}
	
	u:
	if (up<=5){
		ugu=up+1;
		goto l;
	}
	
	ugu=1;
	conv(up);
	dfs(2,1,1);
	dfsp(2,1,1,1);
	
	l:
	cout<<up-ugu-low+ugl;
	return 0;
}