蛇 | Hexo

归档于 2019-10-13 07:24

构造题,

题意

n条蛇,第i条长度为i,编号为奇数必须有奇数个转折点,编号为偶数必须有偶数个转折点,密铺一个矩形

输出矩形长宽,并依次输出每条蛇坐标

$n<=500$

题解

找规律,

首先根据等差数列,当$n$为奇数矩形长为$\frac{n+1}{2}$宽为$n$当$n$为偶数,矩形长为$\frac{n}{2}$宽为$n$

当$n$为偶数$n$这条蛇直接在前面基础上往右摞就完了

x x x x x n n

x x x x x n n

x x x x x n n

当$n$为奇数要找规律,往下摞最后规律是这样的

x x x x x n-2 n

x x x x x n-2 n

n-1 n-1 n-1 n-2 n-2 n-2 n

n-1 n-1 n-1 n n n n

蛇

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void f(ll n){
    ll nowx,nowy,lie,hang,num;
    if(n&1) nowx=(n+1)/2,nowy=n;
    else nowx=n/2,nowy=n+1;
    if(n==2){
        printf("1 1\n");
        printf("1 2 1 3\n");
        return ;
    }
    if(n==3){
        printf("2 1\n");
        printf("1 1 1 2\n");
        printf("1 3 2 3 2 2\n");
        return ;
    }
    if(n&1){
        f(n-3);
        hang=(n-3)/2;
        lie=n-2;
        num=(n-1)/2;
        //n-2
        for(ll i=1;i<=num;i++)
            printf("%lld %lld ",i,lie+1);
        for(ll i=0;i<num-1;i++)
            printf("%lld %lld ",hang+1,lie-i);
        puts("");
        //n-1
        for(ll i=1;i<=num;i++)
            printf("%lld %lld ",hang+1,i);
        for(ll i=num;i>=1;i--)
            printf("%lld %lld ",hang+2,i);
        puts("");
        //n
        for(ll i=1;i<=num+1;i++)
            printf("%lld %lld ",i,lie+2);
        for(ll i=0;i<num;i++)
            printf("%lld %lld ",hang+2,lie-i+1);
        puts("");
    }
    else {
        f(n-1);
        hang=(n+1)/2,lie=n-1;
        //n
        for(ll i=1;i<=hang;i++)
            printf("%lld %lld ",i,lie+1);
        for(ll i=hang;i>=1;i--)
            printf("%lld %lld ",i,lie+2);
        puts("");
    }
}
ll d;
int main(){
    ll x,y;
    while(cin>>d){
        if(d&1){
            x=(d+1)/2,y=d;
        }
        else x=d/2,y=d+1;
        printf("%lld %lld\n",x,y);
        f(d);
    }
}

View Code