NOIP T1 求助
  • 板块灌水区
  • 楼主RLFEi
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/11/26 19:52
  • 上次更新2023/10/27 01:21:45
查看原帖
NOIP T1 求助
543958
RLFEi楼主2022/11/26 19:52

评测记录 我不理解为什么第一个点T了,求大佬解答。 以下是考场代码,可能有点丑

#include<bits/stdc++.h>
#define int long long
#define in rd()
using namespace std;
const int N=1005,mod=998244353;
int n,m,T,id,c,f,len,pos[N][N];
int ansc,ansf,num[N][N],cnt[N][N],sum1[N][N],sum2[N][N];
char s[N][N];
int rd() 
{
	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;
}
signed main()
{
	freopen("plant.in","r",stdin);
	freopen("plant.out","w",stdout);
	T=in,id=in;
	while(T--) {
		n=in,m=in,c=in,f=in;
		if(c==0&&f==0) {
			cout<<0<<' '<<0<<'\n';
			continue;
		}
		memset(num,0,sizeof(num));
		memset(cnt,0,sizeof(cnt));
		memset(sum1,0,sizeof(sum1));
		memset(sum2,0,sizeof(sum2));
		ansc=ansf=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j) cin>>s[i][j];
		for(int i=1;i<=n;++i) {
			len=0;
			for(int j=m;j>=1;--j) {
				if(s[i][j]=='0') ++len,num[i][j]=len-1;
				else num[i][j]=0,len=0;
			}
		}//计算横向最大扩展 
		for(int i=1;i<=m;++i) {
			len=0;
			for(int j=n;j>=1;--j) {
				if(s[j][i]=='0') ++len,cnt[j][i]=len-1;
				else cnt[j][i]=0,len=0;
			}
		}//计算纵向最大扩展 
		for(int i=1;i<=m;++i) {
			int hc=n;
			for(int j=n;j>=1;--j) {
				if(s[j][i]=='1') {hc=j-1;continue;}
				pos[j][i]=hc;
			}
		}//计算向下第一个障碍的位置
		for(int i=1;i<=m;++i) 
			for(int j=1;j<=n;++j) {
				sum1[j][i]=(sum1[j][i]+sum1[j-1][i]+num[j][i])%mod;
				sum2[j][i]=(sum2[j][i]+sum2[j-1][i]+num[j][i]*cnt[j][i])%mod;//前缀和优化一维 
			}
		for(int i=1;i<=m;++i) 
			for(int j=1;j<=n;++j) {
				if(s[j][i]=='1'||j==n||j==pos[j][i]) continue;
				ansc=(ansc+num[j][i]*((sum1[pos[j][i]][i]-sum1[j+1][i])%mod+mod)%mod)%mod;
				ansf=(ansf+num[j][i]*((sum2[pos[j][i]][i]-sum2[j+1][i])%mod+mod)%mod)%mod;
			}
		cout<<ansc*c<<' '<<ansf*f<<'\n';
	}
	return 0;
}
2022/11/26 19:52
加载中...