低级错误……

[KOI 2023 Round 1] 避难所

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x,y;
};
int n,k,len,ans = 1e9,ii = 1;
node kk[5],a[55];
bool f[55];
void dfs(int cur)
{
	if (cur > k)
	{
		for (int i = 1;i <= n;i++) if (f[i]) 
		{
			kk[++len].x = a[i].x,kk[len].y = a[i].y;
			//cout << "//" << kk[len].x << " " << kk[len].y << endl;
		}
		int maxx = 0;
		for (int i = 1;i <= n;i++)
		{
			int minn = 1e9;
			for (int j = 1;j <= k;j++) minn = min(minn,abs(kk[j].x - a[i].x) + abs(kk[j].y - a[i].y));
			maxx = max(minn,maxx);
		}
		ans = min(ans,maxx);
		len = 0;
	}
	for (int i = ii;i <= n;i++) if (!f[i])
	{
		f[i] = true;
		ii = i + 1;
		dfs(cur + 1);
		f[i] = false;
	}
}


int main()
{
	cin >> n >> k;
	for (int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y;
	dfs(1);
	cout << ans;
	return 0;
}

写了 dfs ，找半天没找出问题，后面红温了，写了如下暴力：

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x,y;
} a[55];

int main()
{
	int n,k,ans = 1e9;
	cin >> n >> k;
	for (int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y;
	if (k == 1)
	{
		for (int i = 1;i <= n;i++)
		{
			int maxx = 0;
			for (int j = 1;j <= n;j++)
			{
				maxx = max(maxx,abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y));
			}
			ans = min(maxx,ans);
		}
	}
	if (k == 2)
	{
		for (int i = 1;i <= n;i++)
		{
			for (int j = i + 1;j <= n;j++)
			{
				int maxx = 0,minn;
				for (int l = 1;l <= n;l++)
				{
					minn = min(abs(a[l].x - a[j].x) + abs(a[l].y - a[j].y),abs(a[l].x - a[i].x) + abs(a[l].y - a[i].y));
					maxx = max(maxx,minn);
					//cout << "//" << minn << " " << maxx << endl;
				}
				ans = min(maxx,ans);
			}
		}
	}
	if (k == 3)
	{
		for (int i = 1;i <= n;i++)
		{
			for (int j = i + 1;j <= n;j++)
			{
				for (int l = j + 1;l <= n;l++)
				{
					int maxx = 0,minn;
					for (int r = 1;r <= n;r++)
					{
						minn = min(min(abs(a[r].x - a[j].x) + abs(a[r].y - a[j].y),abs(a[r].x - a[i].x) + abs(a[r].y - a[i].y)),abs(a[r].x - a[l].x) + abs(a[r].y - a[l].y));
						maxx = max(maxx,minn);
					}
					ans = min(maxx,ans);
				}
			}
		}
	}
	cout << ans;
	return 0;
}

赛后发现代码1dfs的if下面没写return直接无语……
写了就过了。

7月9日比赛简介很棒。但是我也被 hack 了（悲）
模板题过了一遍。然后就没有然后了。