CF1333E-Road to 1600题解

构造题？{% label 人类智慧题 red %} 挺震惊的，我居然想到了怎么构造它

题意#

棋盘上有到的值
可以走前后左右四个方向，可以走八个方向
和都会挑他们能走到的最小的格子跳过去
如果当前他们跳不到任何格子，可以花跳过去
如果棋盘都被跳过了，就结束

给你棋盘大小,要求你构造一个棋盘，使花的钱比少，若果没有，输。

思路#

我们手模一些棋盘可以发现

当时一定无解。因为棋盘任意可达。

当时，我们可以通过构造一组棋盘使得最后必须使用跳过去。比如我构造的是

在最后一步必须从跳到而消耗，而不用

当时，我们可以发现只要上下左右中有比当前位置值大的位置，和一定会往那里走，因此我们在棋盘基础上，向下向右扩展边长，最后把和全部引导到棋盘中的位置即可即我们可以构造出这样的棋盘

也就是

再如

其中我们看到蓝色部分需要调换顺序。这样就完成了构造。

AC Code#

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
int a[555][555],n,cnt=0;
int ds[4][2]={{0,1},{-1,0},{1,0},{0,-1}};
void dfs(int x,int y,int d,int maxn){
    if(maxn==3) return ;
    if(y==2&&x==4){
        a[1][4]=++cnt;
        a[2][4]=++cnt;
        return;
    }
    if(y==maxn&&x==maxn){
        a[y][x]=++cnt;
        dfs(x+ds[d+1][0],y+ds[d+1][1],d+1,maxn);
    }else if(y==maxn&&x==1){
        a[y][x]=++cnt;
        if(y-1==3)return;
        a[y-1][x]=++cnt;
        dfs(x+1,y-1,2,maxn-1);
    }else if(y==1&&x==maxn){
        a[y][x]=++cnt;
        if(x-1==3)return;
        a[y][x-1]=++cnt;
        dfs(x-1,y+1,0,maxn-1);
    }else{
        a[y][x]=++cnt;
        dfs(x+ds[d][0],y+ds[d][1],d,maxn);
    }
}
int main(){
    n=read();
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    else if(n>3){if(n&1){
        a[1][n]=++cnt;
        dfs(n,2,0,n);
    }else{
        a[n][1]=++cnt;
        dfs(2,n,2,n);
    }}
    a[3][1]=cnt+4,
    a[3][2]=cnt+9,
    a[3][3]=cnt+3,
    a[2][1]=cnt+5,
    a[2][2]=cnt+1,
    a[2][3]=cnt+2,
    a[1][1]=cnt+8,
    a[1][2]=cnt+7,
    a[1][3]=cnt+6;//关键部分3x3矩阵的构造！
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}

cpp

题意#

思路#

AC Code#

Comments