洛谷——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 语言中那样需要手动管理数组大小和内存分配等问题。
- 先将