当前位置: 首页 > news >正文

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

相关文章:

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

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…...

双击热备和负载均衡的区别

区别&#xff1a; 双机热备 (heartbeat)&#xff1a;对同一应用来讲&#xff0c;永远是主机应用启动&#xff0c;备机应用停止的一主一备模式(两台通常叫双击热备&#xff0c;多台称为高可用) 负载均衡&#xff1a;两台/多台服务器 上同一个应用系统同时工作&#xff0c;分担负…...

如何使用 cPanel 部署 WordPress临时网站

对于依赖WordPress站点或WooCommerce商店的企业来说&#xff0c;在生产环境中直接修改站点风险很大。而WordPress的临时网站是一个更安全的选择&#xff0c;可以通过使用临时网站进行编辑来规避风险。 在本文中&#xff0c;我们将详细介绍WordPress临时网站的相关知识、使用临时…...

Android 自定义 Dialog 实现列表 单选,多选,搜索

前言 在Android开发中&#xff0c;通过对话框让用户选择&#xff0c;筛选信息是很方便也很常见的操作。本文详细介绍了如何使用自定义 Dialog、RecyclerView 以及自定义搜索框 来实现选中状态和用户交互&#xff0c;文中大本分代码都有明确注释&#xff0c;主打一个简单明了&a…...

下载地址合辑(持续更新)

下载地址合辑 汇总OSG相关地址Visual Studio Qt 地址qt插件安装失败 Boost库boost库编译步骤 FFmpeg 地址osg编译库 常用的下载地址&#xff1a; 汇总 vlc 地址&#xff1a; https://www.videolan.org/vlc/index.zh_CN.html visual 地址&#xff1a;https://my.visualstudio.…...

Android Kotlin 高阶函数详解及其在协程中的应用

文章目录 1. 引言2. 什么是高阶函数&#xff1f;3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda 表达式3.3 匿名函数3.4 返回函数 4. 高阶函数的深入用法4.1 函数组合4.2 内联函数4.3 高阶扩展函数 5. Kotlin 高阶函数的对比优势5.1 与 Java 的对比5.2 与 JavaScript 的…...

CSS基础—网页布局(重点!)

1、两列布局 &#xff08;1&#xff09;概念 经典两列布局是指一种网页布局方式&#xff0c;其中一列宽度固定&#xff0c;另一列宽度自适应。‌ 这种布局方式在网页设计中非常常见&#xff0c;因为它能够提供良好的视觉效果和用户体验。 如图所示&#xff1a; 页面顶部放置一…...

【Fargo】17:vs工程转qt构建:QT6 不支持32bit转向qt5.15.2

vs2022的console 工程加入qt支持后使用qt15.2 的vs2019 库,变为一个qt界面程序。最终效果 一些参考 qt5的项目搭建 qt5 最多支持到vs2019 qt6 最新 已经支持vs2022 国内还是以qt5.15为主 升级qt的vstools...

​智能电表蓝牙芯片方案

RAMSUN基于自研射频技术和基带算法提供蓝牙MCU。蓝牙MCU配套成熟的网络协议栈和丰富的示例代码及多平台APP工具。部分芯片型号无需二次开发&#xff0c;即连即用&#xff1b;提供特色蓝牙/串口/USB三通芯片&#xff0c;为更多复杂无线应用赋能。 应用案例说明: BLE方便用户直接…...

miRNA分析流程学习(一)/TCGAmiRNA数据下载

miRNA&#xff08;microRNA&#xff09; 是一种小的非编码 RNA 分子&#xff0c;通常由 20 到 24 个核苷酸组成。miRNA 主要存在于动植物中&#xff0c;并在基因表达调控中起到关键作用。它们通过与特定的信使 RNA&#xff08;mRNA&#xff09;分子结合来抑制基因表达&#xff…...

西南大学软件专硕考研难度分析!

C哥专业提供——计软考研院校选择分析专业课备考指南规划 西南大学软件工程学硕近三年呈现出招生规模稳定、复试线稳中有升的特点。2024届实际录取8人&#xff0c;复试分数线305分&#xff0c;复试录取率67%&#xff0c;相比去年复试线略有下降但仍高于2022届&#xff0c;显示出…...

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-21

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-21 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-21目录1. The Fair Language Model Paradox摘要研究背景问题与挑战如何解决创新点算法模型实验效果重要数据与结论推荐阅读指数&…...

安全芯片 OPTIGA TRUST M 使用介绍与示例(基于STM32裸机)

文章目录 目的资料索引硬件电路软件框架介绍数据存储框架移植框架使用 使用示例示例地址与硬件连接通讯测试功能测试 总结 目的 OPTIGA TRUST M 是英飞凌推出的安全芯片&#xff0c;芯片通提供了很多 slot &#xff0c;用于存放各类安全证书、密钥、用户数据等&#xff0c;内置…...

【AI换装整合及教程】CatVTON:时尚与科技的完美融合

在当今数字化时代&#xff0c;时尚行业正经历着一场前所未有的变革&#xff0c;而 CatVTON 作为一款由中山大学、Pixocial 等机构联合研发的轻量化 AI 虚拟换装工具&#xff0c;无疑是这场变革中的璀璨明星。 一、独特的技术架构 CatVTON 基于 Stable Diffusion v1.5 inpainit…...

接口测试(七)jmeter——参数化(RandomString函数)

一、RandomString函数 需求&#xff1a;模拟10个用户注册 1. 【工具】–>【函数助手对话框】 2. 选择RandomString函数 假设手机号码前3位设置为固定数值136&#xff0c;后8位可用RandomString函数随机产生数值 ① Random string length&#xff1a;8&#xff08;随机长度…...

simple_php

访问靶场 这里传入a和b参数&#xff0c;绕过三个if即可拿到flag a a a_GET[ a’ ];中是抑制报错信息的。 第一个if非常的抽象&#xff0c; if($a0 and $a){echo $flag1; }处理a 要输出flag1,a0&#xff0c;但是&#xff0c;在php中0被视为假也就是Flase 如果a0&#xff0…...

网络搜索引擎Shodan(4)

声明&#xff1a;学习视频来自b站up主 泷羽sec&#xff0c;如涉及侵权马上删除文章 声明&#xff1a;本文主要用作技术分享&#xff0c;所有内容仅供参考。任何使用或依赖于本文信息所造成的法律后果均与本人无关。请读者自行判断风险&#xff0c;并遵循相关法律法规。 感谢泷…...

【Flask】一、安装与第一个测试程序

目录 Flask简介 安装Flask 安装pip&#xff08;Python包管理器&#xff09; 使用pip安装Flask 验证安装 创建Flask程序 创建应用 运行 访问测试 Flask简介 Flask是一个用Python编写的轻量级Web应用框架。它被设计为易于使用和扩展&#xff0c;使其成为构建简单网站或复…...

R语言笔记(二):向量

文章目录 一、Data structure: vectors二、Indexing vectors三、Re-assign values to vector elements四、Generic function for vectors五、Vector of random samples from a distribution六、Vector arithmetic七、Recycling八、Element-wise comparisons of vectors九、Comp…...

信息安全工程师(71)隐私保护技术与应用

前言 隐私保护技术是指通过一系列的技术手段来保护人们的隐私不被公开泄露。随着数字化和网络化社会的发展&#xff0c;个人隐私的保护变得尤为重要&#xff0c;隐私保护技术也因此得到了广泛的应用和发展。 一、隐私保护技术概述 隐私保护技术主要包括数据加密技术、身份认证技…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...