洛谷——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;
}代码思路
- 首先读取数据组数
T。然后对于每组数据，读取s和m的值。通过两层循环来尝试构造满足条件的数组。外层循环遍历可能的数组长度n（从1到m），内层循环尝试确定数组的每个元素的值（从1到s）。 - 当找到满足条件（异或和为
0且元素总和为s）的数组时，输出数组长度和数组元素，并标记f为1，然后跳出内层循环。如果遍历完所有可能情况都没有找到满足条件的数组，则输出-1。 xorSum函数：用于计算给定数组arr中所有元素的异或和，通过遍历数组并依次对元素进行异或运算得到结果。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;
}代码思路
-
首先在
main函数中读取数据组数T，然后对于每组数据读取s和m的值。 -
接着进行一些特殊情况的判断：
- 如果
s为奇数且m为1，那么显然无法构造出满足条件的数组，直接输出-1。 - 如果
s为0，则构造一个长度为1，元素为0的数组并输出。
- 如果
-
然后尝试用两个数来构造满足条件的数组：当
m >= 2时，将s平均分成两份作为两个数组元素，检查其异或和与总和是否满足条件，如果满足则输出该数组。 -
如果前面的情况都不满足，就采用 01 构造模拟思想：
- 先将
s转化为二进制形式存储在binary_s数组中，并记录二进制的长度binary_len。 - 然后从二进制的最低位开始模拟构造数组
c_arr：如果二进制位为1，则对应的数组元素为2的相应幂次方；如果二进制位为0，则数组元素为0。 - 最后检查构造的数组是否满足异或和为
0以及总和为s的条件，如果满足则输出该数组，否则输出-1。 -
通过使用向量，代码在处理动态大小的数据结构时更加方便灵活，避免了像 C 语言中那样需要手动管理数组大小和内存分配等问题。
- 先将