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;
}