2019 杭电多校第八场　hdu 6660(构造)

125 阅读 0 评论 83 点赞

我是靠谱客的博主甜蜜冰淇淋，这篇文章主要介绍2019 杭电多校第八场　hdu 6660(构造)，现在分享给大家，希望可以做个参考。

题意：给你一个ｎ和一个ｍ,让你放置n*m个陷阱,现在让你构造出一条路径，使得每个点只走一次，然后本次的位置与上一次的位置的 Euclidean distance 要严格大于１小于３,这里 Euclidean distance 的计算就是sqrt((x1-x2)^2 +(y1-y2)^2)。
题解：我们经过手推几组发现当n<2＆＆m<3的时候，是无法构造出来的n=1&&m=1是特殊情况，之后所有情况都是可以构造出来的，之后我们就采用之字形构造方法，对其进行构造。
1.我们分两部分进行构造，当行数大于等于３行且列数大于等于３行的时候，当行数为奇数行时从后往前开始构造,列数为奇数从最后一个位置构造，列数为偶数从倒数第二个位置开始构造;当行数为偶数时从第二个位数开始从前往后构造每位数隔二个距离。根据上面描述构造完成后我们会发现他一定是刚好跳到３　１　这个位置，之后我们就跳到１　１　这个位置后，开始在第二行从二开始往后两位两位的构造
构造完成后，在第一行开始我们从后往前开始构造当列数为偶数时候从倒数第二个开始构造，当列数为奇数的时候从倒数第一个开始构造　构造到第三列这个位置
2.　第二部分我们跑一个for从１到ｍ从２　１，　１　２，　２　３　，１　４开始行数２　１　２　１　２　１　这样开始构造列数每次增加１跑到ｍ为止。之后从第３行开始奇数行且奇数列的从倒数第二个开始构造，奇数行偶数列的从最后一个开始构造　，当行数为偶数的时候从１开始构造即可
具体实现方法看代码实现.

复制代码

#include<bits/stdc++.h>
using namespace std;
int flag;
void dfs1(int n,int m)
{
  for(int i=n;i>=3;i--)
    {
        if(i&1) for(int j=m&1?m:m-1;j>=1;j-=2){if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl; }
        else for(int j=2;j<=m;j+=2){if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl;}
   }
    cout<<"1 1"<<endl;
    for(int i=2;i<=m;i+=2) if(flag)cout<<i<<" 2"<<endl;else cout<<"2 "<<i<<endl;
    for(int i=m&1?m:m-1;i>=3;i-=2) if(flag)cout<<i<<" 1"<<endl;else cout<<"1 "<<i<<endl;
}
void dfs2(int n,int m)
{
    for(int i=1;i<=m;i++)
    {
       if(i&1){if(flag)cout<<i<<" 2"<<endl;else cout<<"2 "<<i<<endl;}
      else {if(flag)cout<<i<<" 1"<<endl;else cout<<"1 "<<i<<endl;}
    }
    for(int i=3;i<=n;i++)
    {
        if(i&1)
        {
            for(int j=m&1?m-1:m;j>=1;j-=2)
              if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl;
        }else 
        {
         for(int j=1;j<=m;j+=2)
            if(flag)cout<<j<<" "<<i<<endl;
            else cout<<i<<" "<<j<<endl;
        }   
    }
}
int main()
{  
    int t,n,m;
    cin>>t;
    while(t--)
    {   cin>>n>>m; flag=0;
       if(n>m) {flag=1;swap(n,m);}
        if(n==1&&m==1)
        {
            cout<<"YES"<<endl;
            cout<<"1 1"<<endl;
            continue;
        }
        if(n<2||m<3)
        {
            cout<<"NO"<<endl;
            continue;
        }
       cout<<"YES"<<endl; 
       dfs1(n,m);
       dfs2(n,m);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
int flag;
void dfs1(int n,int m)
{
  for(int i=n;i>=3;i--)
    {
        if(i&1) for(int j=m&1?m:m-1;j>=1;j-=2){if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl; }
        else for(int j=2;j<=m;j+=2){if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl;}
   }
    cout<<"1 1"<<endl;
    for(int i=2;i<=m;i+=2) if(flag)cout<<i<<" 2"<<endl;else cout<<"2 "<<i<<endl;
    for(int i=m&1?m:m-1;i>=3;i-=2) if(flag)cout<<i<<" 1"<<endl;else cout<<"1 "<<i<<endl;
}
void dfs2(int n,int m)
{
    for(int i=1;i<=m;i++)
    {
       if(i&1){if(flag)cout<<i<<" 2"<<endl;else cout<<"2 "<<i<<endl;}
      else {if(flag)cout<<i<<" 1"<<endl;else cout<<"1 "<<i<<endl;}
    }
    for(int i=3;i<=n;i++)
    {
        if(i&1)
        {
            for(int j=m&1?m-1:m;j>=1;j-=2)
              if(flag)cout<<j<<" "<<i<<endl;else cout<<i<<" "<<j<<endl;
        }else 
        {
         for(int j=1;j<=m;j+=2)
            if(flag)cout<<j<<" "<<i<<endl;
            else cout<<i<<" "<<j<<endl;
        }   
    }
}
int main()
{  
    int t,n,m;
    cin>>t;
    while(t--)
    {   cin>>n>>m; flag=0;
       if(n>m) {flag=1;swap(n,m);}
        if(n==1&&m==1)
        {
            cout<<"YES"<<endl;
            cout<<"1 1"<<endl;
            continue;
        }
        if(n<2||m<3)
        {
            cout<<"NO"<<endl;
            continue;
        }
       cout<<"YES"<<endl; 
       dfs1(n,m);
       dfs2(n,m);
    }
}