A.Race

**在这里插入图片描述**

题目大意

给你两个x,y，终点会在二点之间随机出现,alice在点a，假设alice和bob有相同的速度（距离更短者用时更少），问对于bob是否存在一点，无论终点是x还是y,他都能比alice更快到达

思路

如果alice在x,y点之间，bob无法比他更快否则只要在外侧，bob选择比她更接近终点的一点即可

// Author: zengyz
// 2025-06-23 14:59#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= k; i++)cout << 1;for (int i = 1; i <= n - k; i++)cout << 0;cout << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

B.Shrinking Array

在这里插入图片描述

题目大意

定义一个数组“美丽”如果存在一点i, $b_i-b_{i+1}|<=1$

你可以进行如下操作：
每次选择i和i+1,在 $min(a_i,a_{i+1})到max(a_i,a_{i+1})$ 之间选择一个值，将 $a_i和a_{i+1}$ 从数组中移除（数组元素个数减一）
，并将x放到他们的位置上

思路

实际上只有三种情况：
1.一开始就满足要求，存在“美丽”的情况，输出0
2.不满足要求，查看数组是否单调递增或递减，如果是这样那么无论多少次都无法构成，输出-1
3.数组并非单调递增或递减，那么一定存在一个数i,在它左侧或者右侧两个数的最大最小值之间，输出1

//Author: zengyz
//2025-06-23 22:41#include <bits/stdc++.h>using namespace std;
using i64 = long long;void solve()
{int n;cin>>n;vector<int>a(n);for(auto &x:a)cin>>x;for(int i=1;i<n;i++){if(abs(a[i-1]-a[i])<=1){cout<<0<<endl;return;}}bool flag=false;if(a[1]>a[0]){for(int i=1;i<n;i++){if(a[i]<a[i-1])flag=true;}}else {for(int i=1;i<n;i++){if(a[i]>a[i-1])flag=true;}}if(flag){cout<<1<<endl;return;}cout<<-1<<endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while(_T --) {solve();}return 0;
}

C.Coloring Game

在这里插入图片描述

题目大意

给你一个n个元素的数组，Alice先手可以涂任意3个元素，Bob后手涂任意一个（包括Alice涂过的)
问Alice有多少种涂法使得无论Bob怎么涂，Alice涂过的元素和加起来大于Bob涂过的

思路

Alice获胜一共有两种情况
假设Alice涂的元素为a<=b<=c,数组最后一个元素为y
Bob有两种选择，要么涂c要么涂y
要么a+b+c>=y
要么a+b>c
选定a,b，然后二分c可能的取值即可

// Author: zengyz
// 2025-06-23 22:53#include <bits/stdc++.h>using namespace std;
typedef long long ll;
void solve()
{int n;cin >> n;vector<int> a(n);for (auto &x : a)cin >> x;long long res = 0;long long ans = 0;for (int i = 0; i < n-1; i++){for (int j = i + 1; j < n - 1; j++){long long tmp = a[i] + a[j];long long l = j + 1, r = n - 1;l = max(l, (ll)upper_bound(a.begin(), a.end(), a[n-1] - tmp) - a.begin());r = min(r,(ll) lower_bound(a.begin(), a.end(), tmp) - a.begin()-1);res = max(0ll, r - l + 1);ans += res;}}cout << ans << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

D. Reachability and Tree

在这里插入图片描述

题目大意

给你一颗n个节点n-1条边的树，设u,v是一对有序对如果从u到v存在一条路径，将每条边都分配方向，确定树上是否存在n对有序对

思路

如果每条边都是相反的方向，那么存在n-1条有序对，这是最少的情况，那么怎么再增加一对有序对呢？考虑树上存在两条边为相同方向，那么两条边存在三对有序对(a->b->c，有ab,ac,bc)
所以我们要找这样的一组两条边，在树上寻找度为2的点，将它和它相邻的两个点的两条边设为相同方向，让其他边彼此都为不同方向即可

// Author: zengyz
// 2025-06-24 10:24#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<int> du(n + 1);vector<vector<int>> edge(n + 1);for (int i = 0; i < n - 1; i++){int x, y;cin >> x >> y;du[x]++;du[y]++;edge[x].push_back(y);edge[y].push_back(x);}int idx = 0;while (du[idx] != 2){idx++;if (idx == n+1){cout << "NO" << endl;return;}}vector<pair<int, int>> ans;auto dfs1 = [&](auto &&dfs1, int now, int fa, int status) -> void{if (idx == now){int u = edge[now][0], v = edge[now][1];ans.push_back({u, idx});ans.push_back({idx, v});dfs1(dfs1, u, idx, 1);dfs1(dfs1, v, idx, -1);return;}for (auto i : edge[now]){if (i == fa)continue;if (status == 1){ans.push_back({now, i});dfs1(dfs1, i, now, -1);}else{ans.push_back({i, now});dfs1(dfs1, i, now, 1);}}};dfs1(dfs1, idx, -1, 1);cout << "YES" << endl;for (int i = 0; i < ans.size(); i++){cout << ans[i].first << " " << ans[i].second << endl;}return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}