为什么洛谷多测未清空不会寄?
查看原帖
为什么洛谷多测未清空不会寄?
47911
xiaozhangma楼主2022/12/6 23:03

RT,求解释数据的差异何在。

#include<bits/stdc++.h>
#define LL long long
#define F(x,s,t) for(int x=s;x<=t;x++)
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const int N = 1e3 + 10;
const int MOD = 998244353; 
int T, id;
int n, m, c, f;
bool b[N][N];
int r[N][N],d[N][N];
char s[N];
int main(){
	freopen("plant.in","r",stdin);
	freopen("plant.out","w",stdout);
	
	//预处理每个点向右最远能延伸到那个格子
	//            向下 
	T = read(),id = read();
	while(T -- ){
		n = read(),m = read(),c = read(),f = read();
		F(i, 1, n){
			scanf("%s",&s);
			F(j, 0, m - 1){
				b[i][j+1] = s[j] - '0'; 
			}
		}
		
		F(i, 1, n){
			for(int j = m; j >= 1; j -- ){
				if(b[i][j]){//当前格子有障碍 
					r[i][j] = 0;
				}else{//当前格子无障碍 
					r[i][j] = max(j, r[i][j + 1]);
				}
			}
		}
		F(j, 1, m){
			for(int i = n; i >= 1; i -- ){
				
				if(b[i][j]){
					d[i][j] = 0;
				}else{
					d[i][j] = max(i, d[i + 1][j]);
				}
			}
		}
		/*
		F(i, 1, n){
			F(j, 1, m){
				cout<<b[i][j]<<' ';
			}
			cout<<endl;
		}
		F(i, 1, n){
			F(j, 1, m){
				cout<<r[i][j]<<' ';
			}
			puts("");
		}
		F(i, 1, n){
			F(j, 1, m){
				cout<<d[i][j]<<' ';
			}
			puts("");
		}
		*/
		
		LL cntc = 0,cntf = 0;
		F(i, 1, n){
			F(j, 1, m){
				//枚举左上角
				if(!r[i][j] || r[i][j] == j)continue;
				//无法向右拓展
				for(int k = i + 2; k <= d[i][j]; k ++ ){
				 	//从下两行开始
					if(r[k][j] && r[k][j] != j){
						//当前行可以向右拓展,累加答案
						cntc += (r[i][j] - j) * (r[k][j] - j);
						cntc %= MOD;
						cntf += (r[i][j] - j) * (r[k][j] - j) * (d[k][j] - k) % MOD;
						cntf %= MOD; 
					} 
				} 
			}
		}
		cntc *= c;
		write(cntc);
		putchar(' ');
		cntf *= f;
		write(cntf);
		putchar(' ');
		puts("");
	}	
		
	return 0;
}

2022/12/6 23:03
加载中...