AtCoder Beginner Contest 313D题题解
文章目录
- [ Odd or Even](https://atcoder.jp/contests/abc313/tasks/abc313_d)
- 问题建模
- 问题分析
- 1.分析每次查询的作用
- 2.利用异或运算的性质设计查询方法
Odd or Even


问题建模
有n个数,每个数为0或者1,最多可以进行n次询问,每次询问选择k个不同的数,每次询问会得到这些数相加的奇偶性,问这n个数的值分别为多少。
问题分析
1.分析每次查询的作用
每次查询,可以获得这些数相加的奇偶性,即0或者1,则等价于将这些数进行异或得到的异或值。
2.利用异或运算的性质设计查询方法
异或运算有一个性质,就是一个数异或上另一个数偶数次,等价于没有异或该数。所以我们可以构造一种查询方法,其中某一个数被异或奇数次,而剩余数被异或上偶数次,从而得到该数的值。
则可以先进行k+1次查询,每次查询缺少k+1个数中的一个,这样k+1次查询得到的异或值,为k+1个元素每个元素出现奇数次的总异或值,那对于该值异或上前k+1次查询单次得到的异或值,等价于缺少值出现奇数次,其余值出现偶数次,则可以得到缺少值的数值。
然后对于剩下的元素,查询只需要前k-1个数再带一个数的异或值,然后与前k个数的异或值进行比较,若相同,则说明当前元素值与第k个元素相同,否则不同。
#include<bits/stdc++.h>#define x first
#define y second
#define C(i) str[0][i]!=str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N =1100, Mod =998244353;
int a[N];
int s[N];
int n,k;void get_k(){///获得前k+1个数每个数出现奇数次的总异或值int res=0;for(int i=1;i<=k+1;i++){cout <<"? ";for(int j=1;j<=k+1;j++){if(j!=i) cout <<j <<" ";}cout<<endl;cin >>s[i];res^=s[i];}///用总异或值,异或是上缺少某一个值的异或值,从而得到对应为的值for(int i=1;i<=k+1;i++){a[i]=res^s[i];}
}void solve() {cin >>n >>k;get_k();///用前k个数的异或值与后面仅有第k个数不同的异或值作比较,从而得到对应位置的值for(int i=k+2;i<=n;i++){cout <<"? " <<i <<" ";for(int j=1;j<=k-1;j++){cout <<j <<" ";}cout <<endl;cin >>s[i];if(s[i]==s[k+1]) a[i]=a[k];else a[i]=a[k]^1;}cout <<"! ";for(int i=1;i<=n;i++){cout <<a[i] <<" ";}cout <<endl;
} int main() {int t = 1;//cin >> t;while (t--) solve();return 0;
}
相关文章:
AtCoder Beginner Contest 313D题题解
文章目录 [ Odd or Even](https://atcoder.jp/contests/abc313/tasks/abc313_d)问题建模问题分析1.分析每次查询的作用2.利用异或运算的性质设计查询方法 Odd or Even 问题建模 有n个数,每个数为0或者1,最多可以进行n次询问,每次询问选择k个…...
mybatis 中的<![CDATA[ ]]>用法及说明
<![CDATA[ ]]>作用 <![CDATA[ ]]> 在mybatis、ibatis等书写SQL的xml中比较常见,是一种XML语法,他的作用是 可以忽略xml的转义(在该标签中的语句和字符原本是什么样的,在拼接成SQL后还是什么样的) 使用&a…...
从零学算法34
34.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1࿱…...
qiankun-微前端--vue2
项目结构 主应用技术: vue2 子应用技术:vue2 项目目录 这里是特意将主子项目分开来的,方便管理 主应用 安装 qiankun npm install qiankun重新定义一个启动端口,防止和其它子应用共用同一个端口(vue.config.js&…...
Win7累积补丁更新包_UpdatePack7R2-23.8.10
UpdatePack7是最新的Win7补丁累积更新包,Windows 7更新补丁安装包,Win7累积更新离线安装包包括所有关键更新和安全更新及Internet Explorer所有版本的更新,此外还集成了NVMe驱动和USB3.0驱动,使用它还可以将累积更新封装到系统内&…...
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历
理论基础、前中后序遍历的递归法和迭代法、层序遍历 1,二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2,存储方式链式存储线式存储 3,二叉树的遍历深度优先搜索前序遍历(递归法、迭代法)中序遍历࿰…...
Mybatis-plus动态条件查询QueryWrapper的使用
Mybatis-plus动态条件查询QueryWrapper的使用 一:queryWrapper介绍 queryWrapper是mybatis plus中实现查询的对象封装操作类,可以封装sql对象,包括where条件,order by排序,select哪些字段等等,他的层级关…...
Redis安装配置远程连接
1. yum 安装 redis: 直接使用命令,将 redis 安装到 linux 服务器中: yum -y install redis 2. 启动 redis: 在 xshell 里,可以使用下面命令,以后台方式启动 redis: [rootVM-8-17-centos /]…...
pycharm中配置conda
安装好pycharm和conda后,打开pycharm:...
matlab解常微分方程常用数值解法1:前向欧拉法和改进的欧拉法
总结和记录一下matlab求解常微分方程常用的数值解法,本文先从欧拉法和改进的欧拉法讲起。 d x d t f ( x , t ) , x ( t 0 ) x 0 \frac{d x}{d t}f(x, t), \quad x\left(t_{0}\right)x_{0} dtdxf(x,t),x(t0)x0 1. 前向欧拉法 前向欧拉法使用了泰勒展开的第…...
SQL | 计算字段
7-创建计算字段 7.1-计算字段 存储在数据库中的数据一般不是我们所需要的字段格式, 需要公司名称,同时也需要公司地址,但是这两个数据存储在不同的列中。 省,市,县和邮政编码存储在不同的列中,但是当我们…...
leetcode做题笔记67
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 思路一:模拟题意 void reserve(char* s) {int len strlen(s);for (int i 0; i < len / 2; i) {char t s[i];s[i] s[len - i - 1], s[len - i - 1] t;} }char* addBinary(cha…...
fastadmin 自定义搜索分类和时间范围
1.分类搜索,分类信息获取----php 2.对应html页面,页面底部加搜索提交代码(这里需要注意:红框内容) 图上代码----方便直接复制使用 <script id"countrySearch" type"text/html"><!--form…...
Oracle Data Redaction与Data Pump
如果表定义了Redaction Policy,导出时数据会脱敏吗?本文解答这个问题。 按照Oracle文档Advanced Security Guide第13章,13.6.5的Tutorial,假设表HR.jobs定义了Redaction Policy。 假设HR用户被授予了访问目录对象的权限…...
设计模式(6)原型模式
一、介绍 Java中自带的原型模式是clone()方法。该方法是Object的方法,native类型。他的作用就是将对象的在内存的那一块内存数据一字不差地再复制一个。我们写简单类的时候只需要实现Cloneable接口,然后调用Object::clone方法就可实现克隆功能。这样实现…...
pywinauto结合selenium实现文件上传
简介 PC端-Windows上的元素识别可用viewWizard工具 PC端-Windows上的元素操作可用pywinauto库 浏览器上网页的元素识别可用selenium 安装 pip installer pywinauto 使用须知 pywinauto官方文档 确定app的可访问技术 1、win32 API(backend=“win32”) 一般是MFC、VB6、VC…...
【Java多线程学习7】Java线程池技术
线程池技术 一、什么是线程池 线程池顾名思义是管理一组线程的池子。当有任务要处理时,直接从线程池中获取线程来处理,处理完之后线程不会立即销毁,而是等待下一个任务。 二、为什么要使用线程池? 线程池的作用? 1、降低资源…...
VMware虚拟机NAT模式Ubuntu无法上网解决方案
发现只要NAT模式,ping地址时就报网络不可达,且右上方网络图标消失,但是外部USB网络设备又只能在NAT模式下使用。。。 博主的解决方案如下: 按WinR键入services.msc, 找到VMware DHCP Service、VMware NAT Service和V…...
Linux中无法忘记mysql密码处理办法
找到/etc/my.cnf或者/etc/mysql/my.cnf文件 添加下面两行代码,取消密码验证 [mysqld] skip-grant-table使用命令登录:mysql -u root -p,回车,回车使用sql语句来修改密码 mysql>use mysql; mysql>update user set password…...
vue 使用 el-upload 上传文件(自动上传/手动上传)
vue 使用 el-upload 上传文件(自动上传/手动上传) 文章目录 1. 自动上传(选择完文件后,调用axios上传)2.手动上传 1. 自动上传(选择完文件后,调用axios上传) <el-uploadref"upload1"action:multiple"false"accept".xlsx,.csv,.xls":auto-upl…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...
动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...
