P4905 报纸

【题目描述】

在 $n\times n$ 的方阵中，称一个点为特殊点当且仅当此点横纵坐标不互质，即 $(i,j)$ 满足 $\gcd(i,j)\ne1$。

一次操作可以任选一个 $1\times 2$ 的矩形并覆盖，矩形不能超出边界，求使所有特殊点都被覆盖的最小操作数。

$n\le 233$（其实可以加强到 $500$）。

【题目解析】

看到这个题首先想到打表，不直接输入特殊点，而是固定的，不就是让我们打表吗。

我们直接 $O(n^2\log n)$ 暴力算出所有特殊点的位置，然后标记为 $1$，依赖于 $1$ 的联通块大小会很大，爆搜枚举联通块摆放方案即可（好像爆搜不打表也直接能过）。

附上打好的表（前 $233$，答案为 $ans_n$）：

int ans[300]={0,0,1,2,5,6,11,12,19,22,31,32,43,44,57,64,79,80,97,98,117,126,147,148,171,176,201,210,237,238,267,268,299,312,345,356,391,392,429,444,483,484,525,526,569,590,635,636,683,690,739,758,809,810,863,880,933,954,1011,1012,1071,1072,1133,1160,1223,1240,1305,1306,1373,1398,1467,1468,1539,1540,1613,1648,1723,1740,1817,1818,1897,1924,2005,2006,2089,2112,2195,2226,2313,2314,2403,2424,2513,2546,2639,2662,2757,2758,2855,2894,2993,2994,3095,3096,3199,3256,3361,3362,3469,3470,3579,3618,3729,3730,3843,3870,3985,4030,4147,4170,4289,4300,4421,4464,4587,4612,4737,4738,4865,4910,5039,5040,5171,5196,5329,5392,5527,5528,5665,5666,5805,5854,5995,6018,6161,6194,6339,6402,6549,6550,6699,6700,6851,6908,7061,7096,7251,7252,7409,7464,7623,7652,7813,7814,7977,8062,8227,8228,8395,8408,8577,8640,8811,8812,8985,9046,9215,9276,9453,9454,9633,9634,9815,9878,10061,10102,10287,10314,10501,10582,10771,10772,10963,10964,11157,11256,11451,11452,11649,11650,11849,11918,12119,12154,12357,12404,12607,12682,12889,12918,13127,13128,13339,13412,13625,13672,13887,13924,14141,14216,14435,14464,14685,14686,14909,15014,15239,15240,15467,15468,15697,15808,16039,16040};

各种乱搞贪心做法也很好想，已被 hack，目前最高得到 $95$ 分。

接下来提供一种所谓的正解。

看到题目中 $1\times2$ 的矩形覆盖性质，有点像最小点覆盖问题。

顺着这个思路想，对网格图黑白染色以后连边情况变成二分图，于是网络流即可。

代码实现使用 $\text{Dinic}，$设边数为 $m$，则时间复杂度 $O(m\sqrt m)$。实测 $n=500$ 时总边数在 $3\times 10^5$ 左右，跑得飞快。

实现细节：

  • $O(n^2\log n)$ 时间暴力连边处理（$\log$ 来自 $\gcd$）。源点连黑点，白点连汇点，相邻的特殊点黑点连向白点，这样一定是二分图。

  • 最小点覆盖 $=$ 总点数 $-$ 最大匹配。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define cal(x,y) ((x-1)*n+y)
const int N=300,M=N*N,INF=0x3f3f3f3f;
int n,s,t,cnt,ans;
bool c[N][N];
struct edge{
    int v,next,w;
}e[M<<1];
int head[M],tot=1;
void add(int u,int v,int w){
    e[++tot]={v,head[u],w};
    head[u]=tot;
    e[++tot]={u,head[v],!w};
    head[v]=tot;
}
int dis[M],now[M];
bool bfs(){
    queue<int> q;
    memset(dis,0,sizeof(dis));
    q.push(s),dis[s]=1;
    now[s]=head[s];
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(!dis[v]&&e[i].w){
                dis[v]=dis[u]+1;
                q.push(v);
                now[v]=head[v];
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int sum){
    if(u==t) return sum;
    int res=0,tmp;
    for(int i=now[u];i&&sum;i=e[i].next){
        now[u]=i;
        int v=e[i].v;
        if((dis[v]==dis[u]+1)&&e[i].w){
            tmp=dfs(v,min(e[i].w,sum));
            if(!tmp) dis[v]=0;
            e[i].w-=tmp,e[i^1].w+=tmp;
            sum-=tmp,res+=tmp;
        }
    }
    return res;
}
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    s=n*n+1,t=s+1;
    for(int i=2;i<=n;++i){
        for(int j=2;j<=n;++j){
            if(gcd(i,j)!=1){
                c[i][j]=1;
                cnt++;
                int odd=(i+j)&1;
                if(odd) add(cal(i,j),t,1);
                else add(s,cal(i,j),1);
                if(c[i-1][j]) add(cal(i-1,j),cal(i,j),odd);
                if(c[i][j-1]) add(cal(i,j-1),cal(i,j),odd);
            }
        }
    }
    while(bfs()) ans+=dfs(s,INF);
    cout<<cnt-ans<<endl;
    return 0;
}

有问题或错误欢迎交流，个人觉得码风还行，完结撒花！