A. Race

题意

在一个数轴上，奖品可能出现在 $x$ 点或 $y$ 点，Alice 现在在 $a$ 点，请问Bob是否存在一个点 $b$，使得无论奖品出现在 $x$ 点还是 $y$ 点，Bob都能比Alice先拿到（$|b-x|<|a-x|$ 且 $|b-y|<|a-y|$）。注意，$b$ 点不可以与 $a$ 点重合，但可以与 $x$ 点、$y$ 点重合。若存在，输出 YES，否则输出 NO。

题目保证 $a,x,y$ 两两不同。

思路

首先假设 $x<y$（若 $x>y$ 就交换一下）。

• 如果 $a<x$ ，Bob 一定可以选择 $a$ 右边的那个点作为点 $b$，显然满足 $|b-x|<|a-x|$ 且 $|b-y|<|a-y|$；

• 如果 $a>y$，Bob 一定可以选择 $a$ 左边的那个点作为点 $b$，显然也满足 $|b-x|<|a-x|$ 且 $|b-y|<|a-y|$；

• 否则，即 $x<a<y$，Bob 选择任何一个点都一定存在 $|b-x|>|a-x|$ 和 $|b-y|>|a-y|$ 中的一个，所以这种情况一定不可以。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
void solve(){int a,x,y;cin>>a>>x>>y;if(x>y) swap(x,y);if(a<x||a>y){cout<<"YES\n";}else{cout<<"NO\n";}
}
int main(){int T;cin>>T;while(T--){solve();}return 0;
}

B. Shrinking Array

题意

如果一个数组 $b$ 存在至少两个元素，且存在至少一个 $i(1\le i<n)$，使得 $|b_i-b_{i+1}|\le 1$，则称这个数组是 美丽的。

你有一个数组 $a$，你可以按顺序执行以下操作，求出使得数组 $a$ 是 美丽的 的最小操作次数，若不能变成，输出 -1：

• 选择一个 $i(1\le i<n)$，并选择满足 $\min (a_i,a_{i+1})\le x\le \max (a_i,a_{i+1})$ 的任意一个整数 $x$，随后把 $a_i,a_{i+1}$ 替换成一个 $x$，很明显这个时候数组长度减小了 $1$。

思路

观察发现，若数组严格递增或严格递减，且不存在 $|a_i-a_{i+1}|=1$，则不可以变成 美丽的，答案为 -1。（情况 $01$）

其它情况下，若已经存在 $|a_i-a_{i+1}|\le 1$，答案为 $0$。（情况 $02$）

其余情况答案一定是 $1$（情况 $03$）：

• 证明：这些情况中，数组一定不是严格递增的，肯定存在相邻的三个数 $(a,b,c)$ ， 一定满足一个：$b<a<c$ 或 $c<a<b$ 或 $a<c<b$ 或 $b<c<a$。一步操作就可以满足了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int v[maxn];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>v[i];//情况01 递增bool flag=true;for(int i=2;i<=n;i++){if(v[i]<=v[i-1]||v[i]-v[i-1]==1){flag=false;break;}}if(flag){cout<<-1<<endl;return;}//情况01 递减flag=true;for(int i=n-1;i>=1;i--){if(v[i]<=v[i+1]||v[i]-v[i+1]==1){flag=false;break;}}if(flag){cout<<-1<<endl;return;}//情况02for(int i=2;i<=n;i++){if(v[i-1]==v[i]||abs(v[i]-v[i-1])==1){cout<<0<<endl;return;}}//情况03cout<<1<<endl;
}
int main(){int T;cin>>T;while(T--){solve();}return 0;
}

C. Coloring Game

题意

一个大小为 $n$ 的整数数组 $a$。

最初，数组中的所有元素都是无色的。首先，Alice 选择 $3$ 个元素并将它们染成红色。然后 Bob 可以选择任意 $1$ 个元素染成蓝色（如果该元素原本是红色，则会被重新着色）。如果所有红色元素的总和严格大于蓝色元素的值，爱丽丝就获胜。

你的任务是计算爱丽丝有多少种选择 $3$ 个元素的方法，可以确保无论鲍勃如何操作都能获胜。

题目保证 $a$ 数组单调不减。

思路

很明显，我们可以暴力枚举前两个元素，然后查找第三个元素，假设 $a,b,c(a\le b\le c)$ 为这三个元素，则必须满足 $a+b>c$ 且 $a+b+c>\max a_i$。

可以想到用双指针，具体内容请看代码。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5005;
int v[maxn];
void solve(){int n;cin>>n;for(int i=0;i<n;i++){cin>>v[i];}int ans=0;for(int i=2;i<=n-1;i++){int l=0,r=i-1;while(l<r){if(v[l]+v[r]>max(v[n-1]-v[i],v[i])){ans+=r-l;r--;}else{l++;}}}cout<<ans<<endl;
}
signed main(){int T;cin>>T;while(T--){solve();}return 0;
}

D. Reachability and Tree

题意

一棵树有 $n$ 个节点，你要给出一种方案，给每条边加上方向，要存在恰好 $n$ 个数对 $(u,v)$，使得 $u$ 和 $v$ 之间有路径；或者说明这是不可能的。

思路

首先，不管怎么加方向，一定存在至少 $n-1$ 个这样的数对，就是每条边的两个点都可以组成一个数对，所以，只要再加上一对即可。

如果只要 $n-1$ 对，若 $1$ 为根节点，我们可以想到这样子加边：第一层全朝上，第二层全朝下，以此类推。

要想再加上一条边，应该找一个 $2$ 度点，它连接的两条边的方向设为相同的，比如上图中，$8$ 是唯一一个 $2$ 度点，所以把 $9\to 8$ 改为 $8\to 9$。

若没有两度点，就是不可以。

C++ 代码

#include<bits/stdc++.h>
#define pb push_back
#define mpr make_pair
using namespace std;
const int maxn=200005;
int n;
vector<int> g[maxn];
bool flag=false;
int cg;
vector<pair<int,int> > ans;
void find(int v,int fa,int col){for(int x:g[v]){if(x!=fa){if(col) ans.pb(mpr(x,v));else ans.pb(mpr(v,x));find(x,v,col^1);}}
}
void solve(){flag=false; cg=0;for(int i=1;i<=n;i++){g[i].clear();}cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);}for(int i=1;i<=n;i++){if(g[i].size()==2){cg=i;flag=true;break;}}if(!flag){cout<<"NO\n";return;}cout<<"YES\n";int prv=g[cg][0],nxt=g[cg][1];ans.clear();ans.pb(mpr(prv,cg));ans.pb(mpr(cg,nxt));find(prv,cg,0);find(nxt,cg,1);for(pair<int,int> x:ans){cout<<x.first<<" "<<x.second<<endl;}
}int main(){int T;cin>>T;while(T--){solve();}return 0;
}