Codeforces Round #812 (Div. 2)A.B.C.D

A. Traveling Salesman Problem

题目链接：

Problem - A - Codeforces

题面：

 

题意：

你站在0，0的位置上，你可以往上，下，左，右，四个方向走。这片区域有n个箱子，位于（xi，yi），你需要走到（xi，yi）才能捡起箱子，问你从（0，0）捡完所有箱子再回到（0，0）需要几步

思路：

我们只需求出最左/右边箱子的横坐标，最上/下边箱子的纵坐标。这就是我们四个方向要走的最大距离，然后把四个数的绝对值乘2累加即可

代码：

#include
using namespace std;
 
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int a = 105;
		int b = 105;
		int c = -105;
		int d = -105;
		for(int i = 0; i < n; i++){
			int x, y;
			cin >> x >> y;
			if(x < 0){
				a = min(a, x);
			}else{
				c = max(c, x);
			}
			if(y < 0){
				b = min(b, y);
			}else{
				d = max(d, y);
			}
		}
		int ans = 0;
		if(a != 105){
			ans += abs(a) * 2;
		}
		if(b != 105){
			ans += abs(b) * 2;
		}
		if(c != -105){
			ans += c * 2;
		}
		if(d != -105){
			ans += d * 2;
		}
		cout << ans << endl;
	}
	return 0;
}

B. Optimal Reduction

题目链接：

Problem - B - Codeforces

题面：

题意：

你可以对一个数组进行操作：

1.选择两个索引l,r

2.将a[l] ~ a[r]的所有数-1。

f(a)表示把数组a的所有数变成0的操作数

现在规定一种数组B是a数组进行重新排列后的新数组

问是否所有满足条件的B数组f(B)>= f(a)

思路：

f(B)最小的B数组一定是一个满足Bi+1 >= Bi 或者 Bi+1 <= Bi的数组，那么如果a数组不满足的话，就会有f(B) < f(a) 

代码：

#include
using namespace std;
 
int a[100005];
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		bool f = 0;
		bool ff = 0;
		for(int i = 1; i < n - 1; i++){
			if(a[i] < a[i - 1]){
				f = 1;
			}
			if(f && a[i] < a[i + 1]){
				ff = 1;
				break;
			}
		}
		if(ff){
			cout << "NO" << endl;
		}else{
			cout << "YES" << endl;
		}
	}
	return 0;
} 

C. Build Permutation

题目链接：

Problem - C - Codeforces

题面：

题意：

有个数组a是0~n-1的排列的一种，如果ai + i是平方数，那么这个数组是好的，现在需要构造出a数组

思路：

我们可以把1e5内的所有完全平方数求出来，从（n-1）遍历到0，求出每个数能放的位置，（越大的数能放的位置越少）我们先把大的数放了，那么小的数能放的位置也会逐渐减少。我们遍历结束了a数组也就出来了

代码：

#include
using namespace std;
 
int arr[100005];
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i = 0; i < n; i++){
			arr[i] = -1;
		}
		vector<int> ve;
		for(int i = 0; i * i < n; i++){
			ve.push_back(i * i);
			if((i + 1) * (i + 1) >= n){
				ve.push_back((i + 1) * (i + 1));
			}
		}
		int m = ve.size() - 1;
		for(int i = n - 1; i >= 0; i--){
			for(int j = m; j >= 0; j--){
				if(ve[j] - i < n && arr[ve[j] - i] == -1){
					arr[ve[j] - i] = i;
					break;
				}
			}
		}
		for(int i = 0; i < n; i++){
			cout << arr[i] << " ";
		}
		cout << endl;
	}
	return 0;
}

D. Tournament Countdown

题目链接：

Problem - D - Codeforces

题面：

题意：

这是一个交互问题。

有一场由2n名选手组成的锦标赛。第一名选手与第二名选手竞争，第三名选手与第四名选手竞争，以此类推。之后，第一场比赛的获胜者与第二场比赛的获胜者进行竞争，依此类推。锦标赛结束时，只剩下一名选手，他被宣布为锦标赛的获胜者。这样的锦标赛方案被称为单淘汰赛。

你不知道结果，但你想找出锦标赛的获胜者。在一个查询中，您选择两个整数a和b，它们是两个参赛者的索引。如果A比B赢了更多的比赛，评审团将返回1，如果B比A赢了更多的比赛，评审团将返回2，如果他们的胜利数量相等，评审团将返回0。

在不超过⌈13个⋅2n+1个⌉查询中找到赢家。这里，⌈x⌉表示向上舍入到最接近的整数的x的值。

请注意，锦标赛已经结束很久了，这意味着结果是固定的，不依赖于您的查询。

思路：

我们需要在2 ^ (n+1)/3次查询内得出正确答案，所以如果有4个人我们需要在2次查询内得到谁是胜者：

有a，b，c，d四个人，我们先查询a，c

如果a > c,那么就说明d是c，d的迎着，我们再次查询a，d即可

如果a < c,那么我们查询b， c即可

如果a == c，那么两个人在第一轮都是输的一方，那么查询b， d，即可

如果剩下两人，我们需要查询这两人

直到只剩下一人就可以确定冠军了

代码：

#include
using namespace std;
 
int ask(int a, int b){
	cout << "? " << a << " " << b << endl;
	cout.flush();
	int ans;
	cin >> ans;
	return ans;
}
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		queue<int> q;
		int m = pow(2, n);
		for(int i = 1; i <= m; i++){
			q.push(i);
		}
		while(q.size() >= 4){
			int a = q.front();
			q.pop();
			int b = q.front();
			q.pop();
			int c = q.front();
			q.pop();
			int d = q.front();
			q.pop();
			int ans = ask(a, c);
			int x;
			if(ans == 2){
				ans = ask(b, c);
				if(ans == 2){
					x = c;
				}else{
					x = b;
				}
			}else if(ans == 1){
				ans = ask(a, d);
				if(ans == 1){
					x = a;
				}else{
					x = d;
				}
			}else{
				ans = ask(b, d);
				if(ans == 1){
					x = b;
				}else{
					x = d;
				}
			}
			q.push(x);
		}
		if(q.size() == 2){
			int a = q.front();
			q.pop();
			int b = q.front();
			q.pop();
			int ans = ask(a, b);
			if(ans == 1){
				q.push(a);
			}else{
				q.push(b);
			}
		}
		if(q.size() == 1){
			cout << "! " << q.front() << endl;
			cout.flush();
		}
	}
	return 0;
}