Codeforces Round #812 (Div. 2)补题(A-E)

A. Traveling Salesman Problem

题目链接：Problem - A - Codeforces

 题意：有一个xy坐标系，在x轴和y轴的上有若干个箱子，人物可以上下左右移动，问最少多少步能拿完所有箱子。

思路：想象最短路径由一个长方形将四个角内凹，但这个图形的周长和原本长方形相同，所以只需找到一个最小的长方形把所有箱子罩住就行。寻找最左，最右，最上，最下的箱子，作为长方形的边界求边长

代码实现：

#include
#define ll long long
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int l=0,r=0,top=0,b=0;//左右上下四个边界 
		for(int i=1;i<=n;i++)
		{
			int x,y;
			cin>>x>>y;
			if(x==0)//寻找上下 
			{
				top=max(top,y);
				b=min(b,y);
			}
			else//寻找左右 
			{
				l=min(l,x);
				r=max(r,x);
			}
		}
		cout<<(r-l+top-b)*2<<'\n';
	}
	return 0;
}

B. Optimal Reduction

题目链接：Problem - B - Codeforces

 题意：可以进行任意次让一个区间所有值减1的操作，给一个数组a，问a的元素全部变为0所需要的操作数是否小于等于所有“a中元素的任意排列”中元素全为0所需要的操作数。

思路：

考虑一个区间，不断进行操作，直到出现为0的数字，当0在这个区间两边时，操作的范围缩短即可，也就是不再对0进行操作，但当这个0在区间的中间时，会将这个区间变成两个区间，操作数增加，因此一个排列操作数最小的情况必须是对于1-n不能出现中间小两边大的情况，a必须满足最小的情况，对于每个下标，寻找其前面到下标1的最大值和后面到下标n的最大值，判断该元素是否比这两边最大值都小。

代码实现：

#include
#define ll long long
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int pre[maxn];
int last[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		bool f=1;
		for(int i=1;i<=n;i++)
		{
		cin>>a[i];
		pre[i]=last[i]=a[i];	
		}
		pre[n+1]=last[n+1]=0;
		for(int i=1;i<=n;i++)//预处理前缀最大值 
		pre[i]=max(pre[i],pre[i-1]);
		for(int i=n;i>=1;i--)//预处理前缀最小值 
		last[i]=max(last[i],last[i+1]);
		for(int i=1;i<=n;i++)
		if(a[i]-1]&&a[i]1])//a不是最小排列的情况 
		f=0;
		if(f)
		cout<<"YES\n";
		else
		cout<<"NO\n";
	}
	return 0;
}

C. Build Permutation

题目链接：Problem - C - Codeforces

 题意：

给一个0-n-1的自然数，把这些数字放到下标为0-n-1的数组中，要求所有数组元素加上下标是一个数字的平方。输出一种放法。

思路：首先，某个数的平方肯定不超过n-1+n-1，因为这是最大数了，设某个数x*x=i，那么(x+1)*(x+1)<=i*2，证：

(x+1)*(x+1)=x*x+2*x+1

因为都是整数，所以x*x+1<=i

2*i-(x+1)*(x+1)>=2*x*x+2-x*x-2*x-1=(x-1)(x-1)>=0

先枚举0-2n-2中所有的平方数，假设最初0-n-1所有元素都对应放在数组下标0-n-1，从n-1位置开始向前遍历，从最大的可能的平方数寻找，根据上面的结论，n-1到2*n-2之间肯定存在一个可能的数的平方，找到其中的最大的，假设n-1需要再加x等于这个平方数，且这个x肯定小于等于n-1，那么就拿n-1和下标为x（因为此时它的元素是x）交换，这样n-1就完成了，在考虑n-2，n-2只需要放x+2就可以得到和n-1位置一样的平方数，因此这个区间[x,n-1]原本的元素可以完全翻转，且不会影响到区间外前面的元素的选取。

结论：实际上需要从n-1开始向前遍历，每个位置选取数字去匹配最大的可能平方数即可。

 代码实现：

#include
#define ll long long
using namespace std;
const int maxn=1e5+10;
int ans[maxn];//记录某个元素被哪个位置选走，同样也记录某个位置选了哪个元素，因为都是0-n-1 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		memset(ans,-1,sizeof(ans));//初始还没选择答案 
		int n;
		cin>>n;
		int ret=n;
		int sum=0;
		while(n*2-2>sum*sum)sum++;//记录最大可能的平方数＋1 
		for(int i=n-1;i>=0;i--)//
		{
			for(int j=sum;j>=0;j--)//枚举平方数 
			{
				int x=j*j-i;//该位置所需的数字 
				if(x>=0&&x-1)//这个数字在0-n-1范围内且还没被选走 
				{
					ans[x]=i;//这个x被i选走 
					break;
				}
			}
		}
		for(int i=0;i
		if(i==0)
		cout<
		else
		cout<<' '<
		cout<<'\n';
		}
	return 0;
}

D. Tournament Countdown

交互题：通过cout之类的输出向系统问问题，系统会根据询问通过cin之类的输入告诉你答案，根据答案求出最终结果 

题目链接：Problem - D - Codeforces

 题意：交互题，有2^n个选手打晋级赛（就那种16强进8强，8强进四强），给最多2*n/3次询问选手间胜负数量关系的机会，假设a与b，a的胜场比b多，回答1，b的胜场比a多，回答2，同样多，回答0，问谁是冠军。

思路：当比赛处于同一层时，对于相邻两组选手（打完之后胜者互打），a对b，c对d。只需要从两组中各取一名选手，比如a，c，如果a比c多，那冠军不可能是c，并且也不可能是b，因此b淘汰，反过来c多，a,d淘汰，同样多时，因为a和b，c和d打完之后胜者肯定会打起来，因此ac肯定在此前被淘汰了。淘汰两人后，去找询问没被淘汰的两人，少的一方淘汰，多的进入下一轮。

因此可以存储每一轮的选手，不断淘汰进入下一轮，直到比赛只存在一名选手或者两名选手，再进入下一轮。

代码实现：

#include
#define ll long long
using namespace std;
const int maxn=1e5+10;
int ans[maxn];
int k[5];//记录两组选手 
int ask()
{
	int x;
	cout<<'?'<<' '<1]<<' '<3]<//先询问选手1和选手2 
	cin>>x;
	int a=0,b=0;//记录没被淘汰的两人 
	switch(x)
	{
		case 0:a=k[2];b=k[4];break;
		case 1:a=k[1];b=k[4];break;
		case 2:a=k[3];b=k[2];break;
	}
	cout<<'?'<<' '<' '<
	cin>>x;
	if(x==1)
	return a;//返回两组最后胜出者 
	return b;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		vector<int>a;
		int n;
		cin>>n;
		for(int i=1;i<=(1<
		a.push_back(i);
		while(a.size()>2)
		{
			vector<int>temp;
			for(int i=0;isize();i+=4)
			{
				for(int j=0;j<4;j++)//记录两组选手 
				k[j+1]=a[i+j];
				temp.push_back(ask());//胜者进入下一轮 
			}
			a=temp;
		}
		if(a.size()==2)//剩余两人，进行决斗 
		{
		int x;
		cout<<'?'<<' '<0]<<' '<1]<
		cin>>x;	
		if(x==1)
		cout<<'!'<<' '<0]<
		else
		cout<<'!'<<' '<1]<
		}
		else//只剩一人就直接输出 
		cout<<'!'<<' '<0]<
	}
	return 0;
}

E. Cross Swapping

题目链接：Problem - E - Codeforces

题意：给一个n*n的矩阵，上面有元素aij，可以进行操作，给一个k，使得第k行和第k列互换，进行任意次操作后，输出字典序最小的矩阵，字典序小是从第一行第一个从左到右从上到下一行一行比较。 

思路：想要交换a[i][j]和a[i][j]，可以使i行i列交换或者j行j列交换，但是不能同时交换，因为会换回来，因此两者只能选其一，当不想交换a[i][j]和a[j][i]时，两种操作都要或者都不要，因此可以用并查集的思想，当i和j不能同时操作时，它们不在同一个集合并且要记录对立关系，将i+n和j合并，j+n和i合并，i+n代表和i对立的集合，j同样和i对立，因此就会加入i+n的集合，这样就能维护对立关系，当要维护i和j同时操作时，将i和j合并，i+n和j+n合并，因为i和i+n对立，j和j+n对立，i和j相同，那么j+n和i+n就相同，当两个元素对同一个元素对立，那么这个两个元素都要操作或者都不操作。如果a[i][j]和a[j][i]相同，随意，ij没有关系，越上面越前面的元素肯定是优先交换的， 因此发现i和j之前有对立关系，即使遍历到这需要让两个集合相同操作，也不能合并，因为优先满足前面的条件。

代码实现：

#include
#define ll long long
using namespace std;
const int maxn=2e3+10;
int fa[maxn];
int a[maxn][maxn];
int find(int x)//并查集 
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
	fa[x]=y;
}
int ans[maxn]; //记录是否操作 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=2*n;i++)//初始化 1-n记录同类关系，n+1-2n记录对立关系 
		{
		fa[i]=i;
		ans[i]=0;	
		}
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		cin>>a[i][j];
		for(int i=1;i<=n;i++)
		{
		for(int j=i;j<=n;j++)
		if(a[i][j]//不需要交换 
		{
			if(find(i)==find(j+n)||find(i+n)==find(j))//先前存在i j所属集合对立关系 
			continue;
			merge(i,j);
			merge(i+n,j+n);
		}
		else if(a[i][j]>a[j][i])//需要交换 
		{
			if(find(i)==find(j)||find(i+n)==find(j+n))//先前存在 i j所属集合同类关系 
			continue;
			merge(i,j+n);
			merge(i+n,j);
		}
		}
	for(int i=1;i<=n;i++)//让每个元素所属集合的对立集合和本集合不一样 
	ans[find(i+n)]=ans[find(i)]^1;
	for(int i=1;i<=n;i++)//交换操作 
	if(ans[find(i)])
	{
		for(int j=1;j<=n;j++)
		swap(a[i][j],a[j][i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		if(j==1)
		cout<
		else
		cout<<' '<
		cout<<'\n'; 
	}	
	}
	return 0;
}