题解：P15421 像你这样的朋友

lailai0916 · 2026-03-05 13:00:35 · 题解

题意简述

在 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;
}