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