恩情故事之 MAX0810 使用画图击落 N=100 构造 n^2 方案

· · 题解

野蛮题目，下次别出了，，，

经过手玩，奇数猜测是 n^2，偶数是 n^2-2（显然这是一个上界）。还可以发现在 n 小的时候（大的没试过）相当程度地乱放就可以达到这个上界，所以题目留给我们构造的空间非常宽松。

奇数一个想法是 n\to n+2，可以如下构造（图为 n=3）：

从两边没填的两行每次移动两格走到中心，每次调换先左/先右（先上/先下），最终剩下的 3\times 3 涂了左上角图形，此时除了这个左上角的已涂色格子加起来没有影响；随便构造（例如代码中 COL）一个方案。

偶数的一种较有规律的填法是在中间四个格子选一个填（如果 n=6 特殊处理，n\equiv 0\pmod 4 则取 (n/2+1,n/2+1) 否则 (n/2,n/2)）再从右下角填到选择格子的行列，每次把最右列最下行填了，然后递归到子问题。

每次填涂最右列最下行的方法是每次尽量选更靠近右下角的，懒得证明，反正这样确实是可以填完并且 AC 的。

应该是 O(n^3) 但是出题人素质高开 2^{10} 所以就通过了，，，

#include<bits/stdc++.h>
using namespace std;
const int maxn=1050;
int n,a[1050][1050];
int b[maxn],c[maxn],d[maxn*10],e[maxn*10],B=maxn*5;
inline void Pt(int x,int y){
    cout<<x<<" "<<y<<endl;
    if(n%2==0){
        a[x][y]=2;
        b[x]^=1,c[y]^=1,d[x+y+B]^=1,e[x-y+B]^=1;
    }
}
inline void COL(int x,int y){
    Pt(x+1,y+2);
    Pt(x+2,y+2);
    Pt(x+2,y+1);
    Pt(x+1,y+1);
    Pt(x+2,y);
    Pt(x,y+1);
    Pt(x,y+2);
    Pt(x+1,y);
}
inline void F(int n){
    if(n==4){
        if(a[4][4]!=2)Pt(4,4);
        Pt(2,3);Pt(3,4);Pt(4,1);Pt(4,3);
        Pt(1,4);Pt(2,4);Pt(4,2);Pt(3,3);
        Pt(3,1);Pt(1,2);Pt(2,1);Pt(2,2);
        Pt(1,1);
        return ;
    }
    if(n%4==0){
        Pt(n/2+1,n/2+1);
        for(int i=n;i>n/2;i--){
            for(int j=1;j<=2*i-1-(i==n/2+1);j++){
                int x=-1,y;
                for(int k=i;k>=1;k--){
                    if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
                    if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
                }   
                if(x==-1)exit(2);
                Pt(x,y);
            }
        }
        F(n/2);
    }else if(n!=6){
        Pt(n/2,n/2);
        for(int i=n;i>=n/2;i--){
            for(int j=1;j<=2*i-1-(i==n/2);j++){
                int x=-1,y;
                for(int k=i;k>=1;k--){
                    if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
                    if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
                }   
                Pt(x,y);
            }
        }
        F(n/2-1);
    }else{
        Pt(n/2+1,n/2+1);
        for(int i=n;i>n/2+1;i--){
            for(int j=1;j<=2*i-1;j++){
                int x=-1,y;
                for(int k=i;k>=1;k--){
                    if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
                    if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
                }   
                Pt(x,y);
            }
        }
        F(4);
    }
}
signed main(){
    cin>>n;
    if(n&1){
        cout<<n*n<<endl;
        Pt(1,1);
        for(int i=1;i<n;i+=2){
            int cur=0;
            for(int j=1;j<=i-1;j++){
                if(cur){
                    Pt(j,i+1);Pt(j,i+2);Pt(i+2,j);Pt(i+1,j);
                }else{
                    Pt(j,i+2);Pt(j,i+1);Pt(i+1,j);Pt(i+2,j);
                }
                cur^=1;
            }
            COL(i,i);
        }
    }else{
        if(n==2){
            cout<<1<<endl<<1<<" "<<1<<endl;
            return 0;
        }
        cout<<n*n-2<<endl;      
        F(n);
    }
    return 0;
}