信友队2023模拟赛第一题前三个样例过来最后一个栈溢出交上去0pts
  • 板块学术版
  • 楼主sad_desert
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/12 21:24
  • 上次更新2023/11/12 22:01:42
查看原帖
信友队2023模拟赛第一题前三个样例过来最后一个栈溢出交上去0pts
594257
sad_desert楼主2023/11/12 21:24

RT文件读写加了MLE不加TLE无语了

#include<iostream>
#include<cstdio>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define int unsigned int
int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  // ch 不是数字时
    if (ch == '-') w = -1;        // 判断是否为负
    ch = getchar();               // 继续读入
  }
  while (ch >= '0' && ch <= '9') {  // ch 是数字时
    x = x * 10 + (ch - '0'); 
    ch = getchar();  // 继续读入
  }
  return x * w;  // 数字 * 正负号 = 实际数值
}
void write(unsigned long long x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);  // 48 是 '0'
}
unsigned long long ans,ans1;
int heng[2010][2010],shu[2010][2010],siz,sum[2010][2010],kuaihao[2010][2010],m,n,kk;
int a[2010][2010];
struct kuai1{
	int size;
	bool zhengfangxing;
}kuai[4000010];
void dfs(int x,int y){
	kuaihao[x][y]=kk;
	if(x<n&&a[x+1][y]&&!kuaihao[x+1][y])
		dfs(x+1,y);
	if(x>1&&a[x-1][y]&&!kuaihao[x-1][y])
		dfs(x-1,y);
	if(y>1&&a[x][y-1]&&!kuaihao[x][y-1])
		dfs(x,y-1);
	if(y<m&&a[x][y+1]&&!kuaihao[x][y+1])
		dfs(x,y+1);
}
signed main(){
	//freopen("wu.in","r", stdin);
	//freopen("wu.out","w", stdout);
	n=read(),m=read();	
	for(int i=1;i<=n;i++){		
		for(int j=1;j<=m;j++){
			a[i][j]=read();
			sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
		}
	}	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]&&kuaihao[i][j]==0){
				++kk;//cout<<kk;
			//	cout<<"LKKKKKKKKKKK";
				dfs(i,j);
				
				int k;
				for(k=1;k+i<=n&&k+j<=m;k++){
					if(a[i+k][j+k]==0)
						break;
					if(sum[i+k][j+k]-sum[i-1][j+k]-sum[i+k][j-1]+sum[i-1][j-1]!=(k+1)*(k+1)){
						kuai[kk]={k,0};
						break;
					}
				}
				if(a[i+k][j+k]==0&&sum[i+k][j+k]-sum[i-1][j+k]-sum[i+k][j-1]+sum[i-1][j-1]==k*k){
					kuai[kk]={k,1};
				}
			}
		}
	}
	//
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i-1][j]==0&&a[i][j-1]==0&&kuai[kuaihao[i][j]].zhengfangxing==1){	
				siz=kuai[kuaihao[i][j]].size;
				int k;
				for(k=1;k+i+siz-1<=n&&k+j+siz-1<=m;k++){
					if(sum[i+k+siz-1][k+j+siz-1]-sum[i+k+siz-1][j-1]-sum[i-1][j+k+siz-1]+sum[i-1][j-1]!=siz*siz){
						break;
					}
				}
				k--;
				ans1=k*k;
				//cout<<i+k+siz-1<<' '<<j+k+siz-1<<endl;
				int kk=i+k+siz-1;
				for(int kj=j+k+siz;kj<=m;kj++){
				//	cout<<sum[kk][kj]<<' '<<sum[i+siz][siz+j]<<endl;
					while(sum[kk][kj]!=sum[i+siz][j+siz]){
						kk--;
						if(kk<i+siz)
							break;
					}
					if(kk<i+siz)
						break;
					ans1+=kk-i-siz+1;
				}
				kk=j+k+siz-1;
				for(int kj=i+k+siz;kj<=n;kj++){
					while(sum[kj][kk]!=sum[i+siz][j+siz]){
						kk--;
						if(kk<j+siz)
							break;
					}
					if(kk<j+siz)
						break;
					ans1+=kk-j-siz+1;
				}//cout<<ans1<<endl;
				ans+=ans1*siz;
			}
			
		}
	}
	write(ans);
	return 0;
}

2023/11/12 21:24
加载中...