题目链接

C

核心思路

其实还是得根据样例，首先我们先自己分析出来。现根据边地数目来分析。

我们其实不难发现四个端点必须得连上边。

1. 边数为2.那么只有两条竖线。方案数是一种
2. 边数为3，那么就一条竖线还有就是一把叉这里交换位置就是两条了。还有就是平行四边形和一条斜线，也是可以交换位置的。这里就有四种。
3. 边数为4.这个就可以发现就是两把叉就好了。方案数是一种。

所以综上就这么些情况，还是不难的。

// Problem: C. Fault-tolerant Network
// Contest: Codeforces - Educational Codeforces Round 124 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1651/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

const int N=2e5+10;
int a[N],b[N];


void solve()
{
	int n;
	cin>>n;
	int a1=1e10,an=1e10,b1=1e10,bn=1e10;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i];
	int ans=abs(a[1]-b[1])+abs(a[n]-b[n]);
	for(int i=1;i<=n;i++)
	{
		a1=min(a1,abs(a[1]-b[i]));
		b1=min(b1,abs(a[i]-b[1]));
		
		an=min(an,abs(a[n]-b[i]));
		bn=min(bn,abs(b[n]-a[i]));
		
	}
	ans=min(ans,a1+b1+an+bn);
	ans=min(ans,a1+b1+abs(a[n]-b[n]));
	ans=min(ans,an+bn+abs(a[1]-b[1]));
	ans=min(ans,abs(a[1]-b[n])+an+b1);
	ans=min(ans,abs(a[n]-b[1])+a1+bn);
	ans=min(ans,abs(a[1]-b[n])+abs(b[1]-a[n]));
	cout<<ans<<endl;
	
	
	
	
	
	
}


signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
}

D

核心思路

其实我们可以发现一个结论，那就是最终地答案一定就是每个已经知道的点地周边的点。所以这个题目就很好做了。

我们首先把周边地点全都入手，然后以周边的作为起点来所有其他已经知道的点。我们可以数形结合把这个理解为一个一个雷达，他们首先是进行半径为1地搜索，然后是半径为2地，一次类推.....。

我们不难发现这样一定是正确的，因为边权都是1.

#include <bits/stdc++.h>

using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
typedef pair<int,int> PII;


int main()
{
	int n;
	cin>>n;
	vector<PII> a(n);
	for(auto &[x,y]:a)
	{
		cin>>x>>y;
	}
	set<PII> st(a.begin(),a.end());//判重
	map<pair<int,int>,pair<int,int>> ans;
	queue<PII> q;
	for(auto [x,y]:a)
	{
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(!st.count({tx,ty}))
			{
				ans[{x,y}]={tx,ty};
				q.push({x,y});
				break;//只要找到一个这样的点就好了。
			}
			
		}
	}
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int x=t.first;
			int y=t.second;
			int tx=x+dx[i],ty=y+dy[i];
			if(!st.count({tx,ty})||ans.count({tx,ty}))
			continue;
			ans[{tx,ty}]=ans[{x,y}];
			q.push({tx,ty});
		}
	}
	for(auto [x,y]:a)
	{
		auto it=ans[{x,y}];
		cout<<it.first<<" "<<it.second<<endl;
	}
	return 0;
	
	
	
	
	
	
}