D. Tokitsukaze and Meeting

D. Tokitsukaze and Meeting

题意：

给定一个n*m的空矩阵 和一个01串 从左到右一次将01串的元素填入矩阵中 每次从（1,1）的位置新加入元素，已有元素总体右移 一行最右端的元素就移到下一行第一个 就每加入一个元素后当前矩阵中含有1的行和列加起来一共有几个

思路

将行和列分开计算
计算列 ：
因为每次加入一个元素 都是往右移的 所以 列的数量只会增多不会减少
如果加入的那个元素是0 答案不会增加 只有当加入的那个元素是1 且加入后除新加入的元素之外第一列的其他元素都是0那么答案会加一
而可以发现第一列每个元素的位置%m的值相同 所以只要 当前 i 多次减m去查询即可 （这样才不会超时直接遍历寻找取模相同值会超时）
计算行：
对于行 加入第i个元素时的答案 可以由加入i - m时的答案来转移  因为正好相差一行 只要判断多出的这一行有没有1即可
如何判断： 我们可以 将最后一个1的位置记入下来(p) 如果 i - p 小于m说明多出的那一行有1 答案就是 i - m时的答案加1; 否则就是i-m时的答案
最后将行和列的答案加起来即可
这样判断效率比较高

#include
#include
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll N = 1e6 + 5;
const int M = 1e5 + 5;
const int mod = 1e9 + 7;
ll n, m;
mapans1, ans2;
string s;

void solve() {
	cin >> n >> m;
	cin >> s;
	ans1.clear();//行答案
	ans2.clear();//列答案
	for (int i = 0; i < n * m; i++) {
		int flag = 0;
        ans1[i + 1] = ans1[i];
		if (s[i] == '0') continue;
		for (int j = i - m; j >= 0; j -= m) {
			if (j % m == i % m && s[j] == '1') {
				flag = 1;
				break;
			}
		}
		if (!flag) ans1[i + 1]++;
	}
	ll last = 0;
	for (int i = 0; i < n * m; i++) {
		if (s[i] == '1') last = i;
		if (i < m) {//首行要特殊处理
            ans2[i + 1] = max(ans2[i], (ll)(s[i] == '1'));
			continue;
		}
	    ans2[i + 1] = ans2[i - m + 1];
		if (i - last < m) ans2[i + 1]++;
	}
	for (int i = 1; i <= n * m; i++) cout << ans1[i] + ans2[i] << " \n"[i == n * m];
}

signed main()
{
	IOS;
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}

}