【JSCPC】2021江苏省赛 D. Pattern Lock | 结构

标题链接

Problem – D – Codeforces

标题

标题大意

$n$ 行 $m$ 列的点阵图，要求结构 $nm$ 个整点的摆放，摆放中恣意相邻两个点构成一条线段，满足以下条件：

• 任一线段不通过除端点外的其他整点。
• 相邻两条线段形成的角是锐角。

数据规模：$2\le n,m\le 500$。

思路

有多种解法，下面给出一种合法的结构办法：

整体思想为尽量走 Z 字，每相邻两个点的横坐标或纵坐标相差 $1$ 即可确保不每个线段不通过其他点。

蓝色部分

假如 $n$ 为偶数，咱们能够每两行为一组进行结构。

具体完成如下：

//从第 u 行到第 d 行，第 l 列到第 r 列用蓝色办法进行掩盖
void solven(int u,int d,int l,int r)
{
	for (int i=u,t=0;i<=d;i+=2,t=!t)
	{
		if (t&1)
		{
			for (int j=r;j>l;--j) ans.push_back({i,j}),ans.push_back({i+1,j-1});
			ans.push_back({i,l});
			ans.push_back({i+1,r});
		}
		else
		{
			for (int j=l;j<r;++j) ans.push_back({i,j}),ans.push_back({i+1,j+1});
			ans.push_back({i,r});
			ans.push_back({i+1,l});
		}
	}
}

这里有一种特殊状况，若 $n$ 为偶数但不等于 $2$，且 $m=2$ 时，用这种办法掩盖会呈现直角，所以进行讨论时这种状况转到黄色部分的结构办法。

黄色部分

假如 $m$ 为偶数，咱们能够每两列为一组进行结构，具体完成与蓝色部分相似，详见代码不再赘述。相同的，若 $m$ 为偶数但不等于 $2$，且 $n=2$ 时，用黄色部分的结构办法会呈现直角，所以在这种状况下应该使用蓝色结构办法。

赤色部分

当 $n$ 和 $m$ 均为奇数时，咱们从左上角取出一个 $33$ 的矩阵直接手玩出答案，就能够把剩下的部分划分红两个有偶数边长的矩阵。

赤色部分为手玩出来的固定解法，直接按图片将点顺次参加答案即可。

ans.push_back({1,3});
ans.push_back({3,2});
ans.push_back({1,1});
ans.push_back({2,3});
ans.push_back({3,1});
ans.push_back({1,2});
ans.push_back({3,3});
ans.push_back({2,1});
ans.push_back({2,2});

离开赤色部分能够直接用黄色部分的结构办法掩盖右侧的 $n(m-3)$ 的点阵，但是从赤色部分直接转向蓝色部分会呈现钝角，于是用绿色部分进行衔接。

绿色部分

当 $n$ 和 $m$ 均为奇数且 $n>3$ 时，咱们需要用蓝色的结构办法掩盖一个 $(n-3)m$ 的矩阵，但是从 $(2,2)$ 点出发直接转为蓝色结构办法会呈现钝角，于是用绿色结构办法进行衔接。

该部分也是手玩出来的……相同按图顺次参加答案。

ans.push_back({4,1});
ans.push_back({4,2});
ans.push_back({5,1});
ans.push_back({4,3});
ans.push_back({5,2});
ans.push_back({5,3});

代码

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct asdf{
	int x,y;
};
vector<asdf> ans;
int n,m;
void solven(int u,int d,int l,int r)
{
	for (int i=u,t=0;i<=d;i+=2,t=!t)
	{
		if (t&1)
		{
			for (int j=r;j>l;--j) ans.push_back({i,j}),ans.push_back({i+1,j-1});
			ans.push_back({i,l});
			ans.push_back({i+1,r});
		}
		else
		{
			for (int j=l;j<r;++j) ans.push_back({i,j}),ans.push_back({i+1,j+1});
			ans.push_back({i,r});
			ans.push_back({i+1,l});
		}
	}
}
void solvem(int u,int d,int l,int r)
{
	for (int i=r,t=((r-l+1)/2)%2;i>=l;i-=2,t=!t)
	{
		if (t&1)
		{
			ans.push_back({d,i});
			ans.push_back({u,i-1});
			for (int j=u;j<d;++j) ans.push_back({j,i}),ans.push_back({j+1,i-1});
		}
		else
		{
			ans.push_back({u,i});
			ans.push_back({d,i-1});
			for (int j=d;j>u;--j) ans.push_back({j,i}),ans.push_back({j-1,i-1});
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	if (n%2==0&&m!=2) solven(1,n,1,m);
	else if (m%2==0) solvem(1,n,1,m);
	else
	{
		solvem(1,n,4,m);
		ans.push_back({1,3});
		ans.push_back({3,2});
		ans.push_back({1,1});
		ans.push_back({2,3});
		ans.push_back({3,1});
		ans.push_back({1,2});
		ans.push_back({3,3});
		ans.push_back({2,1});
		ans.push_back({2,2});
		if (n>3)
		{
			ans.push_back({4,1});
			ans.push_back({4,2});
			ans.push_back({5,1});
			ans.push_back({4,3});
			ans.push_back({5,2});
			ans.push_back({5,3});
		}
		solven(6,n,1,3);
	}
	for (auto v:ans) printf("%d %d\n",v.x,v.y);
	return 0;
}