洛谷——P8468 [Aya Round 1 C] 文文的构造游戏（01构造问题）

P8468 [Aya Round 1 C] 文文的构造游戏

题目描述

[Aya Round 1 C] 文文的构造游戏 - 洛谷

运行代码（暴力枚举）——超时

#include <stdio.h>
#define ll long long
const int N = 1e6 + 5;
// 计算数组元素的异或和
ll xorSum(ll arr[], int n) {ll res = 0;for (int i = 0; i < n; i++) {res ^= arr[i];}return res;
}// 计算数组元素的和
ll sumArray( ll arr[], int n) {ll res = 0;for (int i = 0; i < n; i++) {res += arr[i];}return res;
}int main() {int T;scanf_s("%d", &T);while (T--) {ll s, m;scanf_s("%lld%lld", &s, &m);int f = 0;// 从长度为1开始尝试构造数组for (int n = 1; n <= m; n++) {// 只需要确定前n - 1个元素，最后一个元素通过总和计算得出ll arr[N];for (int i = 0; i < n - 1; i++) {arr[i] = 1;}arr[n - 1] = s - sumArray(arr, n - 1);// 检查是否满足条件if (arr[n - 1] >= 1 && arr[n - 1] <= s && xorSum(arr, n) == 0 && sumArray(arr, n) == s) {printf("%d ", n);for (int i = 0; i < n; i++) {printf("%lld ", arr[i]);}printf("\n");f = 1;break;}}if (!f) {printf("-1\n");}}return 0;
}

代码思路

1. 首先读取数据组数 T。然后对于每组数据，读取 s 和 m 的值。通过两层循环来尝试构造满足条件的数组。外层循环遍历可能的数组长度 n（从 1 到 m），内层循环尝试确定数组的每个元素的值（从 1 到 s）。
2. 当找到满足条件（异或和为 0 且元素总和为 s）的数组时，输出数组长度和数组元素，并标记 f为 1，然后跳出内层循环。如果遍历完所有可能情况都没有找到满足条件的数组，则输出 -1。
3. xorSum 函数：用于计算给定数组 arr 中所有元素的异或和，通过遍历数组并依次对元素进行异或运算得到结果。
4. sumArray 函数：用于计算给定数组 arr 中所有元素的总和，通过遍历数组并依次将元素相加得到结果。

运行代码（01构造）——ac

C代码

#include <stdio.h>
#define ll long long 
const int N = 1e6 + 5;
// 计算数组的异或和
ll xorSum(ll arr[], int n) {ll res = 0;for (int i = 0; i < n; i++) {res ^= arr[i];}return res;
}// 计算数组的和
ll sumArray(ll arr[], int n) {ll res = 0;for (int i = 0; i < n; i++) {res += arr[i];}return res;
}
int main() {int T;scanf("%d", &T);while (T--) {ll s, m;scanf("%lld%lld", &s, &m);// 如果s为奇数且m为1，无解if (s % 2 == 1 && m == 1) {printf("-1\n");continue;}// 如果s为0，构造长度为1，元素为0的数组if (s == 0) {printf("1 0\n");continue;}int n = 2;long long arr[2];// 尝试用两个数构造满足条件的数组if (m >= 2) {arr[0] = s / 2;arr[1] = s / 2;if (xorSum(arr, 2) == 0 && sumArray(arr, 2) == s) {printf("2 %lld %lld\n", arr[0], arr[1]);continue;}}// 如果前面的情况都不满足，尝试用多个数构造// 先将s表示成二进制形式ll binary_s[64];int binary_len = 0;ll temp_s = s;while (temp_s > 0) {binary_s[binary_len++] = temp_s % 2;temp_s /= 2;}// 从二进制的最低位开始模拟构造数组n = binary_len;ll c_arr[N];for (int i = 0; i < binary_len; i++) {if (binary_s[i] == 1) {c_arr[i] = 1LL << i;}else {c_arr[i] = 0;}}// 检查构造的数组是否满足条件if (xorSum(c_arr, n) == 0 && sumArray(c_arr, n) == s) {printf("%d ", n);for (int i = 0; i < n; i++) {printf("%lld ", c_arr[i]);}printf("\n");}else {printf("-1\n");}}return 0;
}

C++ 向量 

#include <iostream>
#include <vector>
#define ll long long
using namespace std;// 计算向量元素的异或和
ll xorSum(const vector<ll>& arr) {ll res = 0;for (ll num : arr) {res ^= num;}return res;
}// 计算向量元素的和
ll sumArray(const vector<ll>& arr) {ll res = 0;for (ll num : arr) {res += num;}return res;
}int main() {int T;cin >> T;while (T--) {ll s, m;cin >> s >> m;// 如果s为奇数且m为1，无解if (s % 2 == 1 && m == 1) {cout << "-1" << endl;continue;}// 如果s为0，构造长度为1，元素为0的向量if (s == 0) {cout << "1 0" << endl;continue;}int n = 2;vector<ll> arr(2);// 尝试用两个数构造满足条件的向量if (m >= 2) {arr[0] = s / 2;arr[1] = s / 2;if (xorSum(arr) == 0 && sumArray(arr) == s) {cout << "2 " << arr[0] << " " << arr[1] << endl;continue;}}// 如果前面的情况都不满足，尝试用多个数构造// 先将s表示成二进制形式vector<ll> binary_s;ll temp_s = s;while (temp_s > 0) {binary_s.push_back(temp_s % 2);temp_s /= 2;}// 从二进制的最低位开始模拟构造向量n = binary_s.size();vector<ll> c_arr(n);for (size_t i = 0; i < n; i++) {if (binary_s[i] = = 1) {c_arr[i] = 1LL << i;}else {c_arr[i] = 0;}}// 检查构造的向量是否满足条件if (xorSum(c_arr) == 0 && sumArray(c_arr) == s) {cout << n << " ";for (ll num : c_arr) {cout << num << " ";}cout << endl;}else {cout << "-1" << endl;}}return 0;
}

代码思路

1. 首先在 main 函数中读取数据组数 T，然后对于每组数据读取 s 和 m 的值。

2. 接着进行一些特殊情况的判断：

   • 如果 s 为奇数且 m 为 1，那么显然无法构造出满足条件的数组，直接输出 -1。
   • 如果 s 为 0，则构造一个长度为 1，元素为 0 的数组并输出。

3. 然后尝试用两个数来构造满足条件的数组：当 m >= 2 时，将 s 平均分成两份作为两个数组元素，检查其异或和与总和是否满足条件，如果满足则输出该数组。

4. 如果前面的情况都不满足，就采用 01 构造模拟思想：

   • 先将 s 转化为二进制形式存储在 binary_s 数组中，并记录二进制的长度 binary_len。
   • 然后从二进制的最低位开始模拟构造数组 c_arr：如果二进制位为 1，则对应的数组元素为 2 的相应幂次方；如果二进制位为 0，则数组元素为 0。
   • 最后检查构造的数组是否满足异或和为 0 以及总和为 s 的条件，如果满足则输出该数组，否则输出 -1。

   • 通过使用向量，代码在处理动态大小的数据结构时更加方便灵活，避免了像 C 语言中那样需要手动管理数组大小和内存分配等问题。