标签：cf1678D ch 1000100 int 行第 学生 一列

题意

参加会议的学生有n * m个，包括几个调皮的学生和几个认真的学生。

学生被从1到n⋅m进行计算。学生们将依次进入会场。

当第i位学生进入会场时，他将坐在第1排的第1列，已经就座的学生将向后移动一个座位。

具体来说，位于第i行第j列(1≤j≤m−1)的学生将移动到第i行第(j+1)列的第1列，位于第i行第m列的学生将移动到第(i+1)行第1列的第1列。

表示一行或一列，当且仅当该行或一列中至少有一个认真的学生时为好。请在第i位学生进入会场后，预测好排好列的数量。

初见

毫无想法，每次都要统计之前是否有新的行数或者列数发生变化

经过几番模拟发现，每次加入一个学生，列上的元素相对位置不变，那么一旦这一列出现了好学生，那么以后这一列一直都是好学生

那么考虑行，如果现在进入了i*j行,可以根据退后m个学生以及上一个好学生的位置来统计好的行和列

#include<bits/stdc++.h>
using namespace std;
int a[1000100],pre[1000100],g[1000100],f[1000100],ans[1000100];
int read()
{
	char ch=getchar();
	while (!(ch=='0'||ch=='1')) ch=getchar();
	return ch-'0';
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)
			{
				a[(i-1)*m+j]=read();
				g[(i-1)*m+j]=ans[(i-1)*m+j]=pre[(i-1)*m+j]=0;
				f[j]=0;
			}
		}
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)
			{
				g[(i-1)*m+j]=g[(i-1)*m+j-1];
				if (a[(i-1)*m+j]==1&&f[j]==0) f[j]=1,g[(i-1)*m+j]++;
			}
		}
		
		int las=-1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{	
				if (a[(i-1)*m+j]==1) las=(i-1)*m+j;
				pre[(i-1)*m+j]=las;
			}
		for (int i=1;i<=n*m;i++)
		{
			ans[i]=g[i];
			if (i<=m&&pre[i]!=-1) ans[i]++;
			else 
			if (i>m)
			{
				if (i-pre[i]<m&&pre[i]!=-1) ans[i]++;
				ans[i]=ans[i]+ans[i-m]-g[i-m];
			}
			printf("%d ",ans[i]); 
		}
		printf("\n");
	}
	return 0;
}

标签：cf1678D,ch,1000100,int,行第,学生,一列
From： https://www.cnblogs.com/by-w/p/16747701.html