模拟 (NOIP17提高模拟训练11六边形)

时间:2022-12-17 10:25:31
棋盘是由许多个六边形构成的,共有5种不同的六边形编号为1到5,棋盘的生成规
则如下:
1.从中心的一个六边形开始,逆时针向外生成一个个六边形。
2.对于刚生成的一个六边形,我们要确定它的种类,它的种类必须满足与已生成的相
邻的六边形不同。
3.如果有多个种类可以选,我们选择出现次数最少的种类。
4.情况3下还有多个种类可以选,我们选择数字编号最小的。
现在要你求第N个生成的六边形的编号?
前14个六边形生成图如下:

模拟 (NOIP17提高模拟训练11六边形)

输入格式:

第一行:T,表示数据组数
接下来T行,每行一个数:N,表示第N个六边形

输出格式:

共t行,每行一个数,表示第N个数据的答案

样例输入:

4
1
4
10
100

样例输出:

1
4
5
5
思路就是模拟啦,主要是把六边形转换成矩形存在数组里面难度有点大,这是同学zhoukaicheng给我的一张解析图,orz~

模拟 (NOIP17提高模拟训练11六边形)

按照这个图进行储存,并且将关联的点的规律找出来,然后每一次搜一个点的时候判断他六个角的点,于是就很轻松的完成了~

#include<bits/stdc++.h>
using namespace std;
int now=1,k=1;
int ans[20000],f[1010][1100];

struct Point
{
int key,num;

}p[10];

bool cmp(Point a,Point b)
{
if(a.num<b.num||(a.num==b.num&&a.key<b.key))
return 1;
return 0;
}

void put(int x,int y)
{
sort(p+1,p+6,cmp);
bool book[8];
memset(book,false,sizeof(book));
book[f[x-1][y-1]]=book[f[x+1][y+1]]=book[f[x][y-1]]=book[f[x][y+1]]=book[f[x-1][y]]=book[f[x+1][y]]=1;
for(int i=1;i<=5;i++)
{
if(!book[p[i].key])
{
p[i].num++;
f[x][y]=p[i].key;
ans[now]=p[i].key;
break;

}
}
}

int main()
{
int x=250,y=250;
for(int i=1;i<=5;i++)
p[i].key=i;
f[x][y]=1;ans[1]=1;p[1].num++;


while(now<10005)
{
x++;y++;
for(int i=1;i<=k;i++)now++,x--,put(x,y);
for(int i=1;i<=k;i++)now++,x--,y--,put(x,y);
for(int i=1;i<=k;i++) now++,y--,put(x,y);
for(int i=1;i<=k;i++) now++,x++,put(x,y);
for(int i=1;i<=k;i++) now++,x++,y++,put(x,y);
for(int i=1;i<=k;i++) now++,y++,put(x,y);
k++;
}
int s,t;
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>s;
cout<<ans[s]<<endl;
}
return 0;
}