Pinely Round 4 (Div. 1 + Div. 2)

A

题意：通过多次删除相邻的两个元素，最终剩下的一个元素的最大可能值。由于数组的长度是奇数，最终总会剩下一个元素。求剩余元素的最大值

可以发现一个数左右数的个数为偶数时，可以删除到只剩该元素，且左边为偶数，则右边为偶数，因此我们只需找出最大值的位置，判断其位置是否为奇数位。

• 是，则输出其

• 否，则置0，再次寻找最大数

#include <iostream>

using namespace std;
const int N = 105;
int arr[N];
void solve() {
  int num;
  cin >> num;
  int maxpos = 0;
  int maxnum = 0;
  for (int i = 0; i < num; i++) {
    cin >> arr[i];
    if (arr[i] > maxnum) {
      maxnum = arr[i];
      maxpos = i;
    }
  }
  while (1) {
    if (maxpos % 2 == 0) {
      cout << arr[maxpos] << endl;
      return;
    } else {
      arr[maxpos] = 0;
      maxpos = 0;
      maxnum = 0;
      for (int i = 0; i < num; i++) {

        if (arr[i] > maxnum) {
          maxnum = arr[i];
          maxpos = i;
        }
      }
    }
  }
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

B

题意：题目要求构建一个数组 a，使得 b[i] = a[i] & a[i+1] 对于所有的 1 <= i <= n-1 成立。对于给定的数组 b，我们需要判断是否有可能构造这样的数组 a，如果可能，输出任意一个符合条件的数组 a，否则输出 -1。

通过推断，我们发现，在a[1]-a[n-1]的数组可以由b[i-1] | b[i]得到，a[0]=b[0],a[n] = b[n - 1]。

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int b[N];

void solve() {
    int n;
    cin >> n;
    n = n - 1;
    for(int i = 0; i < n; i++)
        cin >> b[i];
    a[0] = b[0];
    a[n] = b[n - 1];
    for(int i = 1; i < n; i++)
    {
        a[i] = b[i - 1] | b[i];
    }
    for(int i = 0; i < n; i++)
    {
        if(b[i] != (a[i] & a[i + 1]))
            {
                cout << "-1" << endl;
                return;
            }
    }
    for(int i = 0; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意：

你有一个整数数组 a，需要通过一系列操作将数组中的所有元素都变为 0。每次操作包括以下两个步骤：

1. 选择一个整数 x（0 ≤ x ≤ 10^9）。
2. 用 |ai - x| 替换每个元素 ai，其中 |v| 表示 v 的绝对值。

例如，通过选择 x=8，数组 [5, 7, 10] 将变为 [|5-8|, |7-8|, |10-8|] = [3, 1, 2]。

你需要构建一个操作序列，在最多 40 次操作内将所有元素变为 0，或者确定这是不可能的。

这里通过观察发现，每次的x都是取最大值与最小值的一半。得出题解：

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
#define ll long long

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n), b;
  bool flag = false;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  if (n == 1) { //特判
    cout << "1" << endl;
    cout << arr[0] << endl;
    return;
  }

  //有元素不为0
  while (*max_element(arr.begin(), arr.end()) > 0) {
    if (b.size() >= 40) {
      cout << "-1" << endl;
      return;
    }

    int max_elem = *max_element(arr.begin(), arr.end());
    int min_elem = *min_element(arr.begin(), arr.end());
    int x = (max_elem + min_elem) / 2;
    b.push_back(x);

    for (int i = 0; i < n; i++) {
      arr[i] = abs(arr[i] - x);
    }
  }
    cout << b.size() << endl;
    for (const auto &item : b) {
      cout << item << " ";
    }
    cout << endl;
  }


int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

D

​

题意：你被给定了一个有 n 个顶点的无向图，顶点编号从 1 到 n。当且仅当$u⊕vu$ 是一个素数时，顶点 u 和 v之间存在一条边，其中 ⊕表示按位异或运算。

你的任务是用最少的颜色对图中的所有顶点进行着色，使得没有两条直接连接的顶点具有相同的颜色。

由于自然数中最小的不是质数的数是4，且由异或性质可知，连续四个数异或的二进制低两位是一定不同的。

因此考虑让同色的数之间的异或值都是 4 的倍数就可以构造一种符合要求的做法

显然将所有数按照它们模 4 的余数分组，同组数染一种颜色即可，这样组内任意两数异或值都是 4 的倍数

参考博客Pinely Round 4 (Div. 1 + Div. 2) - 空気力学の詩 - 博客园 (cnblogs.com)

#include <stdio.h>

int t,n;
signed main()
{
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n);
		if (n==1) puts("1\n1"); else
		if (n==2) puts("2\n1 2"); else
		if (n==3) puts("2\n1 2 2"); else
		if (n==4) puts("3\n1 2 2 3"); else
		if (n==5) puts("3\n1 2 2 3 3"); else
		{
			puts("4");
			for (int i=1;i<=n;++i) printf("%d%c",i%4+1," \n"[i==n]);
            //i！=n时输出第一个" "，当n==i时输出\n
		}
	}
	return 0;
}