Codeforce8.29-9.4做题笔记
Tokitsukaze and Meeting（1700）
题意：给定n*m的网格。学生从第一行(1,1)开始进入，每来一个学生改行学生往后右移一个位置，该行最后一个位置学生进入下一行第一个，以此类推。每个学生有个标志0和1.求第i个学生进入后，至少一行有学生1和至少一列有学生1的行列个数总和。
题解：
对列，使用队列模拟。
对行，可以增量更新。第二行到最后的情况可以由前面已求过dp[j-m]的推出，只需考察第一行的情况即可。（子问题）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t; cin>>t;
for(int i = 0;i<t;i++)
{
int n,m; cin>>n>>m;
string s;cin >> s;
queue<int> q;
int dp[n*m],dpcol[n*m],ans[n*m];
int row1count = 0;
int col1count = 0;
for(int j = 0;j<m;j++) {
q.push(s[j] - '0');
if(s[j]=='1') {
row1count++; col1count++;
}
dp[j]=row1count>0;
ans[j]=dp[j]+col1count;
}
for(int j = m;j<n*m;j++)
{
//update the row
row1count = row1count + (s[j] - '0') - (s[j - m] - '0');
dp[j] = dp[j - m] + (row1count > 0);
//update the coloum
col1count -= q.front();
int a = q.front() || (s[j] - '0');
col1count += a;
q.pop();
q.push(a);
ans[j] = col1count + dp[j];
}
for(int j = 0;j<n*m;j++)cout<<ans[j]<<" ";cout<<endl;
}
system("pause");
return 0;
}
反思：可以考虑多个时间步长的增量关系，不要仅限于相邻步长的增量关系。多考虑是否有可以利用的子问题。