P15421 像你这样的朋友

题意简述

在 $n\times n$ 的 $\texttt{01}$ 网格中尽可能多填入 $\texttt{1}$，使得选取任意一个 $\texttt{1}$ 上下左右移动一步后，都不会出现横向或纵向连续 $3$ 个 $\texttt{1}$。

填入 $\left\lceil\frac{n^2}{3}\right\rceil$ 个 $\texttt{1}$ 可以获得 $100$ 分基础分，超出部分可以获得附加分。

解题思路

我们可以将每个格子 $(i,j)$ 按照 $(i+j)\bmod 3=\set{0,1,2}$ 划分为 $3$ 个集合。显然在每个集合内，连续 $3$ 个格子至多有 $1$ 个 $\texttt{1}$，因此任意一个集合填入 $\texttt{1}$ 都满足条件。根据鸽巢原理，最大集合的大小为 $\left\lceil\frac{n^2}{3}\right\rceil$，即可获得 $100$ 分基础分。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int n=1;n<=270;n++)
	{
		int t=(n+1)%3;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cout<<((i+j)%3==t?'x':'o');
			}
			cout<<'\n';
		}
	}
	return 0;
}