P12 ABC086D Checker

​ “执此剑，踏破混沌黑白。”

​ 隔岸相望，已然是一年半载。如今总算踏过此城。

​ 这题真是搞心态，刚开始看感觉好有意思，结果做了半天没抓住重点，一直没淦出来。

​ 首先，倒是很容易就能发现，对于坐标是可以对 \(2k\) 取模的，毕竟是个周期。然后更进一步，其实可以再化为对 \(k\) 取模，因为如果一个点 \((x,y)\) 为黑，那么 \((x-k,y)\) 一定为白。所以可以用等价条件替换。所有要求全部都处在 \(k \times k\) 的方格中了。

​ 接下来还需要想到二维前缀和，因为最容易想到的就是 \(for\) 循环直接爆力把方格给跑一边，然后看哪一种能满足最多的要求。对于每一种情况，我们需要的就是某一个矩形块中黑色或者白色要求的数目，刚好可以用二维前缀和解决。

const int N=100010,K=1005;

char c[N];
int n,k;
struct Node{
  bool c;
  int x,y;
}node[N];

int sum[K][K][2];

inline void solve(){
  for(int i=1;i<=n;++i){
    node[i].x%=(k<<1),node[i].y%=(k<<1);
    if(node[i].x>=k) node[i].x-=k,node[i].c^=1;
    if(node[i].y>=k) node[i].y-=k,node[i].c^=1;
    sum[node[i].x][node[i].y][1]+=node[i].c,
    sum[node[i].x][node[i].y][0]+=(!node[i].c);
  }
  for(int i=1;i<k;++i)
    sum[0][i][1]+=sum[0][i-1][1],sum[i][0][1]+=sum[i-1][0][1],
    sum[0][i][0]+=sum[0][i-1][0],sum[i][0][0]+=sum[i-1][0][0];
  for(int i=1;i<k;++i)
    for(int j=1;j<k;++j)
      sum[i][j][0]+=sum[i-1][j][0]+sum[i][j-1][0]-sum[i-1][j-1][0],
      sum[i][j][1]+=sum[i-1][j][1]+sum[i][j-1][1]-sum[i-1][j-1][1];
  
  int ans=0;
  for(int i=0;i<k;++i)
    for(int j=0;j<k;++j){
      int b=sum[i][j][1]+sum[k-1][k-1][1]-sum[i][k-1][1]-sum[k-1][j][1]+sum[i][j][1];
      int w=sum[i][k-1][0]-sum[i][j][0]+sum[k-1][j][0]-sum[i][j][0];
      sMax(ans,Max(w+b,n-w-b));
    }
  cout<<ans<<'\n';
}

signed main(){
  cin>>n>>k;
  for(int i=1;i<=n;++i){
    char ch;
    cin>>node[i].x>>node[i].y>>ch;
    node[i].c=(ch=='B');
  } solve();

  return 0;
}

· EOF