A. Lever

题目大意

给你两个长度为n的数组a,b
在每次迭代中：
1.对于任意一个$a_i>b_i$的下标i，会让$a_i-1$
2.对于任意一个$a_i<b_i$的下标i，会让$a_i+1$
如果操作1无法执行，迭代终止
问会进行几次迭代

思路

迭代的次数为对于所有$a_i>b_i$的下标i,$a_i-b_i$的总和
操作2对操作1没有影响

// Author: zengyz
// 2025-08-13 16:55

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < n; i++)
    cin >> b[i];
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (a[i] > b[i])
      cnt += a[i] - b[i];
  }
  cout << cnt + 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. Alternating Series

题目大意

我们称一个数组是好的，当
对于任意i，有$a_i\ast a_{i+1}<0$
且任意连续子数组的和为正数
给你数组长度n，构造字典序最小的好的数组

思路

首先要求字典序最小，所以我们让负数都为-1（这样对应的正数也是最小的），然后考虑如何构造
首先对于任意i，有$a_i\ast a_{i+1}<0$，所以数组内肯定是一正一负
然后考虑样例2的情况，中间一个正数，左右两个负数，那么正数最小的情况是3
那么按-1 3 -1 3。。。的情况构造出来的一定是一个好的数组
考虑数组长度为偶数时 最后一位为2同样满足条件，且字典序更小
所以当数组为奇数时，-1 3 -1 3。。。且以-1 结尾
当数组长度为偶数时，以2结尾

// Author: zengyz
// 2025-08-13 16:58

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n;
  cin >> n;
  if (n % 2)
  {
    for (int i = 1; i <= n / 2; i++)
    {
      cout << -1 << " " << 3 << " ";
    }
    cout << -1 << endl;
  }
  else
  {
    for (int i = 1; i < n / 2; i++)
    {
      cout << -1 << " " << 3 << " ";
    }
    cout << -1 << " " << 2 << 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. Make it Equal

题目大意

给你两个可重集合S，T
你可以从S中任意选择一个元素x,令x=x+k或者｜x-k |
问是否能让S和T相等

思路

令x=x+k或者｜x-k |可以变成余数为x%k或者k - (x%k)的任何数
所以我们只要逐个判断一下T中所有元素的x%k或k - (x%k)是否与S中对应即可 ，
用mp存储余数，操作S同时增加x%k或者k - (x%k)的次数
操作T同时删除x%k或者k - (x%k)的次数,如果二者都为0说明无法相等

// Author: zengyz
// 2025-08-13 17:00

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n, k;
  cin >> n >> k;
  vector<int> s(n), t(n);
  map<int, int> mp;
  for (int i = 0; i < n; i++)
  {
    cin >> s[i];
    mp[s[i] % k]++;
    mp[k-(s[i]%k)]++;
  }
  bool flag = true;
  for (int i = 0; i < n; i++)
  {
    cin >> t[i];
    if (mp[t[i] % k] == 0 &&  mp[k-(t[i]%k)] == 0)
    {
      flag = false;
    }
    else
    {
      mp[t[i] % k]--;
      mp[k-(t[i]%k)]--;
    }
  }
  if (flag)
  {
    cout << "YES" << endl;
  }
  else
    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;
}

D. Arboris Contractio

题目大意

给你一棵树，你可以进行如下操作：
选择两个节点u,v
删除这两个节点之间的路径上的所有边，对于这条路径上的所有节点t
构建新的边(u,t)
问最少经过几次操作，可以使得树上任意两个节点的最短距离最小

思路

要使得任意两个节点的最短距离最小，那么这棵树一定是一棵星型的树，除一个中心结点外，其他结点都是它的叶子结点，这样任意两个节点的最短距离为2

那么我们要通过操作实现，我们就要找到一个结点t，然后对于这个结点t，将其他叶子结点和这个结点t进行操作，就可以得到这样一棵树，那么最小操作次数就是要找到这样一个t，它的子结点的叶子结点最多
我们遍历所有叶子结点的父节点并为其打上标记
找到叶子结点最多的父节点，操作次数就是总叶子结点数减去最多叶子的结点 数

// Author: zengyz
// 2025-08-13 17:21

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n;
  cin >> n;
  vector<vector<int>> edge(n + 1);
  map<int, int> mp;
  for (int i = 1; i < n; i++)
  {
    int u, v;
    cin >> u >> v;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  if(n==2)
  {
    cout<<0<<endl;
    return;
  }
  int cnt=0;
  for (int i = 1; i <= n; i++)
  {
    if (edge[i].size() == 1)
    {
      mp[edge[i][0]]++;
      cnt++;
    }
  }
  int maxx=0;
  for(int i=1;i<=n;i++)
  maxx=max(maxx,mp[i]);
  cout<<cnt-maxx<<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. Adjacent XOR

题目大意

给你两个数组a,b
对于数组a的每个下标i,你可以进行至多一次操作
使得$a_i=a_i\oplus a_{i+1}$
问是否能通过操作将a变成b

思路

对于每个$a_i$
首先判断$a_i是否等于b_i$
如果不相等，那么从左到右考虑当前的i,判断$a_i\oplus a_{i+1}是否=b_i$
如果不相等，那么从右到左考虑当前的i,判断$a_i\oplus b_{i+1}是否=b_i$(因为$a_{i+1}$最后需要变成b_{i+1},我们先操作$a_{i+1}$
如果以上三种情况都不行，那么输出no
记得特判最后一个元素

// Author: zengyz
// 2025-08-13 17:29

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < n; i++)
    cin >> b[i];
  bool flag = true;
  if (a[n - 1] != b[n - 1])
  {
    cout << "NO" << endl;
    return;
  }
  for (int i = n - 2; i >= 0; i--)
  {
    if (a[i] != b[i])
    {
      if ((a[i] ^ a[i + 1]) != b[i])
      {
        if ((a[i] ^ b[i + 1]) != b[i])
        {
          flag = false;
          break;
        }
      }
    }
  }
  if (flag)
  {
    cout << "YES" << endl;
  }
  else
  {
    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;
}