A. Square Year

題目大意

給你一個四個字符的字符串，代表一個數字s
問是否存在a,b兩個數字，使得$(a+b{)}^2=s$

思路

如果s是奇數或不能被開根號一定不行
設sq為s開根號后的結果
將sq一分為2，考慮sq/2有沒有余數的情況

// Author: zengyz
// 2025-06-26 15:53#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{string s;cin >> s;int num = 0;for (int i = 0; i < s.size(); i++){num *= 10;num += s[i] - '0';}int sq = sqrt(num);// cout<<sq<<endl;if (sq * sq != num){cout << -1 << endl;}else{if (sq % 2 == 0)cout << sq / 2 << " " << sq / 2 << endl;elsecout << sq / 2 << " " << sq / 2 + 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;
}

B. Not Quite a Palindromic String

題目大意

給你一個01串，串s長度為n(偶數)
一對索引為好的如果$s_i=s_{n?i+1}$,
給你k,問在任意重排串s的情況下，是否存在k對好的索引

思路

求出能夠湊成的最大值和最小值，設有cnt0個0,cnt1個1,最大值為相同的對著放，即$(cnt0+cnt1)/2$
最小值就是0101插著放，無可避免會有它們的差值/2個好的索引
另外k-最小值一定要是偶數，因為每次翻轉01會多出兩對好的索引

// Author: zengyz
// 2025-06-26 15:58#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n, k;cin >> n >> k;string s;cin >> s;int cnt1 = 0, cnt0 = 0;for (int i = 0; i < n; i++){if (s[i] == '0')cnt0++;elsecnt1++;}if (cnt0 < cnt1)swap(cnt0, cnt1);int maxx = cnt0 / 2 + cnt1 / 2;int minn = (cnt0 - cnt1) / 2;if (minn <= k && k <= maxx){if((k-minn)%2==0)cout << "YES" << endl;else cout<<"NO"<<endl;return;}cout << "NO" << 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. Need More Arrays

題目大意

給你一個數組an，你可以移除數組中任意多個數，在你移除完后，
如果$a_i+1<a_{i+1}$ ，那么$a_{i+1}$會新開一個數組
問an最多會分成多少數組

思路

用idx記錄一下上一個分出去的數組,最優解肯定是每個數組就一個元素，方便下一個分新的數組，然后繼續遍歷數組，找到下一個滿足條件的數，將其賦值為idx

//Author: zengyz
//2025-06-26 16:12#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;int idx=0;int cnt=1;for(int i=1;i<n;i++){if(a[idx]+1<a[i]){cnt++;idx=i;}}cout<<cnt<<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. Come a Little Closer

題目大意

在一個1e9*1e9的平面上有n個妖怪，每個妖怪有自己的xy坐標，你可以最多移動一個妖怪，問能覆蓋所有妖怪的最小矩形是多大

思路

按x和y坐標進行排序，每次忽略第一個和最后一個元素（因為他們一定在最外面）
將剩下的元素求行坐標和縱坐標的最小最大值，將他們設成矩陣的長寬
如果算出來的矩陣=n-1,那么就得再多開一行或者一列，取一下最小值
四種情況取最小值即可

// Author: zengyz
// 2025-06-26 16:14#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<pair<int, int>> v(n), u(n);auto cmp1 = [&](pair<int, int> &a, pair<int, int> &b) -> bool{return a.first < b.first;};auto cmp2 = [&](pair<int, int> &a, pair<int, int> &b) -> bool{return a.second < b.second;};for (int i = 0; i < n; i++){cin >> v[i].first >> v[i].second;u[i].first = v[i].first, u[i].second = v[i].second;}sort(v.begin(), v.end(),cmp1);sort(u.begin(), u.end(),cmp2);if (n == 1 || n == 2){cout << n << endl;return;}ll ans = 1e18;auto calc = [&](auto &&calc, vector<pair<int, int>> &f, int l, int r) -> ll{long long idxi = 2e9, idyi = 2e9, idxa = 0, idya = 0;for (int i = l; i < r; i++){ll _x = f[i].first, _y = f[i].second;idxi = min(idxi, _x);idxa = max(idxa, _x);idyi = min(idyi, _y);idya = max(idya, _y);}ll res = (idxa - idxi + 1) * (idya - idyi + 1);if (res == n - 1)res += min(idxa - idxi + 1, idya - idyi + 1);return res;};ans = min(ans, calc(calc, v, 0, n - 1));ans = min(ans, calc(calc, v, 1, n));ans = min(ans, calc(calc, u, 0, n - 1));ans = min(ans, calc(calc, u, 1, n));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;
}

E. Kirei Attacks the Estate

題目大意

給你一棵樹，根節點為1
定義一個點的威脅值為$a_i?a_{p_i}+a_{p_{p_i}}?...$,其中$p_i$為i到根節點（1）的父結點
問每個點的最大威脅值為多少

思路

設每個點當前的最大值f1和最小值f2,用dfs開始從根節點1開始遍歷，取最小值的原因是當前的最小值對于子節點來說可能會使威脅值變大（若最小值為負數），使用dfs為當前節點的子節點先初始化最大值為max(0ll,max(-f1[now],-f2[now]));最小值為min(-f1[now],-f2[now]);(now為當前節點)
最后對每一個點取最大值f1即可

// Author: zengyz
// 2025-06-26 16:54#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<ll> a(n + 1), ans(n + 1), f1(n + 1), f2(n + 1);vector<vector<ll>> son(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i < n; i++){int u, v;cin >> v >> u;son[v].push_back(u);son[u].push_back(v);}auto dfs = [&](auto &&dfs, int now, int fa) -> void{f1[now] += a[now];f2[now] += a[now];// cout<<now<<" "<<f1[now]<<" "<<f2[now]<<endl;for (auto v : son[now]){if (v == fa)continue;f1[v] = max(0ll, max(-f1[now], -f2[now]));f2[v] = min(-f1[now], -f2[now]);dfs(dfs, v, now);}};dfs(dfs, 1, -1);for (int i = 1; i <= n; i++)cout << f1[i] << " ";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;
}