360建站系统,网站建设流程策划书,网站上的个人词条怎么做的,桂林漓江风景图片P8468 [Aya Round 1 C] 文文的构造游戏
题目描述
[Aya Round 1 C] 文文的构造游戏 - 洛谷 运行代码#xff08;暴力枚举#xff09;——超时
#include stdio.h
#define ll long long
const int N 1e6 5;
// 计算数组元素的异或和
ll xorSum(ll arr[], int n) {l…
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 vectorll arr) {ll res 0;for (ll num : arr) {res ^ num;}return res;
}// 计算向量元素的和
ll sumArray(const vectorll 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;vectorll 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表示成二进制形式vectorll binary_s;ll temp_s s;while (temp_s 0) {binary_s.push_back(temp_s % 2);temp_s / 2;}// 从二进制的最低位开始模拟构造向量n binary_s.size();vectorll 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 语言中那样需要手动管理数组大小和内存分配等问题。
