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