CF1713.

A. Traveling Salesman Problem

注意到答案为 \(2 \cdot (Rx-Lx+Ry-Ly)\)，其中 \(Rx\) 为最大的横坐标，\(Lx\) 为最小的横坐标，\(Ry\) 与 \(Ly\) 同理。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, x[105], y[105];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	int Lx=0, Rx=0;
	int Ly=0, Ry=0;
	for(int i=1;i<=n;++i) {
		x[i]=read(), y[i]=read();
		Lx=min(Lx,x[i]), Rx=max(Rx,x[i]);
		Ly=min(Ly,y[i]), Ry=max(Ry,y[i]);
	}
	int d1=Rx-Lx;
	int d2=Ry-Ly;
	printf("%lld\n",(d1+d2)<<1);
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Optimal Reduction

最优策略是不断“削平”，\(1,2,3 \rightarrow 0,1,2, \rightarrow 0,0,1 \rightarrow 0 , 0 ,0\)。

注意到如果存在一个「谷」，那么在操作中必然存在 \(0\) 把两边元素隔开，从而让操作次数增加。\(2 ,1, 3 \rightarrow 1 , 0 ,2 \rightarrow 0 , 0 , 2 \rightarrow 0 , 0 ,1 \rightarrow 0 , 0 ,0\)。

而这个「谷」不一定非要是与相邻的两个数，比如 \(5 , 2 ,2 ,5\) 这样的。

所以设前缀 \(\max\) 为 \(p_i\)，后缀 $$ 为 \(q_i\)。判断是否存在一个 \(i\)，满足 \(p_{i-1} > a_i\) 且 \(a_i < q_{i+1}\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t, n, a[N], p[N], q[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	bool fg=1;
	p[0]=q[n+1]=-1;
	for(int i=1;i<=n;++i) a[i]=read(), p[i]=max(p[i-1],a[i]);
	for(int i=n;i;--i) q[i]=max(q[i+1],a[i]);
	for(int i=2;i<n;++i) {
		if(a[i]<p[i-1]&&a[i]<q[i+1]) fg=0;
	}
	puts(fg? "YES":"NO");
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Build Permutation

考虑一个事实，对于任意正整数 \(n\)，在 \([n,2n]\) 区间内一定存在一个完全平方数。

那么从 \(x=n-1\) 开始，找到大于 \(x\) 的最小的完全平方数 \(t\)，对于 \(i \in [t-x,x]\)，令 \(ans_i = t-i\) 即可，之后让 \(x= t-x-1\)。

直到 \(x=-1\) 为止。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t, n, ans[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	int x=n-1;
	while(~x) {
		int t=sqrt(2*x);
		t*=t;
		for(int i=t-x;i<=x;++i) ans[i]=t-i;
		x=t-x-1;
	}
	for(int i=0;i<n;++i) printf("%lld%c",ans[i]," \n"[i==n-1]);
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Tournament Countdown

这是一道交互题，也是我的第一道交互题。

先来考虑，两个人获胜场数相同意味着什么？由于胜利者会晋级，淘汰者再也不能参加比赛，所以两个人获胜场数相同，意味着这两人必定晋级到了同一轮。

那么如果 \(a\) 的获胜次数大于 \(b\)，说明 \(a\) 晋级到了更高的一轮，否则就反过来。

由于询问次数最多为 \(\frac{2}{3} 2^n\)，设 \(m= 2^n\) 所以有一个我想不到的结论，只要每次对 \(4\) 个人进行两次询问，就能直到哪个人晋级，从而询问数量为 \[ 2 \times ( \frac{1}{4}m + \frac{1}{16}m + \frac{1}{64}m +\cdots) = \frac{2}{3}m \] 等比数列求和公式——我从来都背不过的东西。

那么怎么样对 \(4\) 个人进行两次询问，就能得到最终晋级者呢？

对于第 \(i\) 个人，其中 \(i\) 是 \(4\) 人中的第一个，\(i\) 要和 \(i+1\) 对抗，\(i+2\) 和 \(i+3\) 对抗。

询问 \(i\) 和 \(i+2\)，如果胜利场数相同，说明二人都输给了与自己对抗的人。如果都打败了与自己对抗的人，虽然此时也相同，但是最后 \(i\) 和 \(i+2\) 必然要分出胜负，所以这种情况不会发生。此时只要询问 \(i+1\) 和 \(i+3\) 就能找到胜利者。

否则如果 \(i\) 的获胜次数大于 \(i+2\)，就询问 \(i\) 和 \(i+3\)。如果 \(i\) 的获胜次数小于 \(i+2\)，就询问 \(i+1\) 和 \(i+2\)。

综上，必然能够满足条件。

特别地，当只剩下 \(2\) 人时，只要询问 \(1\) 次就可以了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N=1e5+5;
int t, n, ans[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int ask(int a,int b){
	cout<<"? "<<a<<' '<<b<<endl;
	int x; cin>>x;
	return x;
}
void solve() {
	cin>>n;
	n=1<<n;
	vector<int> a, b;
	for(int i=1;i<=n;++i) a.pb(i);
	while(a.size()>2) {
		b.clear();
		for(int i=0;i<a.size();i+=4) {
			int res=ask(a[i],a[i+2]);
			if(!res) {
				if(ask(a[i+1],a[i+3])==1) b.pb(a[i+1]);
				else b.pb(a[i+3]);
			} else if(res==1) {
				if(ask(a[i],a[i+3])==1) b.pb(a[i]);
				else b.pb(a[i+3]);
			} else {
				if(ask(a[i+2],a[i+1])==1) b.pb(a[i+2]);
				else b.pb(a[i+1]);
			}
		}
		a=b;
	}
	if(a.size()==2) {
		int res=ask(a[0],a[1]);
		if(res==2) a[0]=a[1];
	}
	cout<<"! "<<a[0]<<'\n';
}
signed main() {
	t=read();
	while(t--) solve();
}