题解 P4905 【报纸】

· · 题解

这道题其实顶天黄题真没蓝题内味

也许是我太菜只会暴力吧。

先说说我的做法其实跟楼上的做法大差不差

First：建议一个f二维数组，一个ans=0，一个n；

Second：暴力循环开找，记录GCD！=1的位置，用到了一个函数GCD，用法如下

GCD：头文件algorithm（其实背不到就把所有的都写出来就行了）

格式：__gcd(i,j) 下划线不能少 返回的值即i与j的最大公因数。好了，科普完了。

Third：再次暴力开找把记录了的位置改为找过，然后找它的四方有就变找过不加一，第一次加一。

其实我觉得这道题是题目描述的问题，我也认为要加。

Fourth 提交AC

上代码了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
bool f[1000][1000];
int ans=0;
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(__gcd(i,j)!=1)f[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(f[i][j]==1)
            {
                f[i][j]=0;
                ans++;
                if(f[i+1][j]==1)f[i+1][j]=0;
                if(f[i][j+1])f[i][j+1]=0;
                if(f[i-1][j])f[i][j-1]=0;
                if(f[i][j-1])f[i][j-1]=0;
            }
        }
    }
    cout<<ans; 
}