赛后补题:Codeforces Round #843 (Div. 2) 1775C. Interesting Sequence

news/2024/11/9 1:57:47/

传送门:CF

题目描述:

Petya and his friend, robot Petya++, like to solve exciting math problems.
One day Petya++ came up with the numbers n and x and wrote the following equality on the board:
n & (n+1) & … & m=x,
where & denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal 
m (m≥n) that the equality on the board holds.
Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He 
quickly wrote a program and found the answer.
Can you solve this difficult problem?
输入:
5
10 8
10 10
10 42
20 16
1000000000000000000 0
输出:
12
10
-1
24
1152921504606846976

赛场上的做法假了,一直挂在一个点上,感觉还是自己前面的题做的太慢了,导致这道题时间并不充裕,然后慌起来之后脑子也比较混乱.赛后感觉这道题也并不是很难…

主要思路:

  1. 首先我们把玩一下我们的题目,我们会发现原来的式子n&(n+1)&…&m=xn\&(n+1)\& … \&m=xn&(n+1)&&m=x有一个比较显然的性质,那就是我们&\&&的越多,我们的式子显然是越小的.因为我们的之前的二进制1会因为后面的0变成0,但是并不会有新的1出现,所以肯定是越变越小的
  2. 所以一个比较简单的枚举区间就出来了,那肯定就是一直进行&\&&运算,然后到式子的值比x还要小的时候如果还没有和x相等过的话,肯定就不可能再相等了,直接输出-1即可,但是直接一个一个枚举肯定是不行的,必超时,所以我们需要进行一点点优化.
  3. 我们把玩一下我们的二进制式子和我们的&\&&运算.我们会发现因为二进制1后面的0存在,所以我们的二进制位最后一个1后面的数字再变化就没有意义,并不会改变我们的所有式子,讲起来可能比较抽象,举一个简单的栗子:
1010101000

比如上面的这个二进制数字,假设当前我们的式子最终的数字是这个,那么此时我们给他+1,+2,+3+1,+2,+3+1,+2,+3等等都是没有任何意义的,因为加的数字只贡献最后一个1后面的0的数字,和我们的0与起来依旧是0.那么加多少才有意义呢,我们会发现需要一直加到(1000)这个数字才会发生改变,而这个数字恰好是我们最后一个1形成的二进制数!!

至于如何找到我们的二进制位中的最后一个1,我们有一个比较模板的写法,称之为lowbit函数lowbit函数lowbit函数,这个函数在树状数组中会使用到,网上博客介绍得到也十分详细,此处就不再赘述了

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long 
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int t;
int n,x;
int lowbit(int x) {return x&(~x+1);}
signed main() {t=read();while(t--) {n=read();x=read();if(x>n) {printf("-1\n");continue;}if(x==n) {printf("%lld\n",x);continue;}int flag=0;while(n>=x) {int temp=n+lowbit(n);n&=temp;if(n==x) {printf("%lld\n",temp);flag=1;break;}}if(flag==0) printf("-1\n");}return 0;
}

http://www.ppmy.cn/news/11364.html

相关文章

JVM- 第二章-类加载子系统

类加载子系统 2. 类加载子系统 2.1. 内存结构概述2.2. 类加载器与类的加载过程 加载阶段链接阶段初始化阶段 2.3. 类加载器分类 2.3.1. 虚拟机自带的加载器2.3.2. 用户自定义类加载器 2.4. ClassLoader的使用说明2.5. 双亲委派机制2.6. 其他 2. 类加载子系统 2.1. 内存结构…

唤醒手腕 Go 语言开发学习笔记(基本简介、环境安装)

1. Go语言简介 Go&#xff08;又称 Golang&#xff09;是 Google 的 Robert Griesemer&#xff0c;Rob Pike 及 Ken Thompson 开发的一种静态强类型、编译型语言。Go 语言语法与 C 相近&#xff0c;但功能上有&#xff1a;内存安全&#xff0c;GC&#xff08;垃圾回收&#xf…

指针进阶篇(2)

进阶指针 &#x1f914;前言&#x1f914; 一、&#x1f60a;函数指针&#x1f60a; 二、&#x1f61c;函数指针数组&#x1f61c; 三 、&#x1f61d;指向函数指针数组的指针&#x1f61d; 四、&#x1f31d;回调函数&#x1f31d; &#x1f340;小结&#x1f340; &…

结构体 · 内存对齐

欢迎来到 Claffic 的博客 &#x1f49e;&#x1f49e;&#x1f49e; 前言&#xff1a; 在初识C语言中简单介绍了结构体&#xff0c;结构体可以理解为不同类型数据的集合体&#xff0c;但是你想过结构体的大小是如何计算的吗&#xff1f;看完这篇博客&#xff0c;你就能给自己答…

测试开发基础 mvn test | 利用 Maven Surefire Plugin 做测试用例基础执行管理

一、需求在测试工作场景中&#xff0c;经常会遇到下面的问题&#xff1a;1、执行自动化测试用例的时候&#xff0c;只想指定某个测试类&#xff0c;或者某个方法&#xff0c;又或者某一类用例等&#xff0c;怎么办&#xff1f;2、想要和 Jenkins 一起进行持续集成&#xff0c;可…

java 数组看这一篇文章就够了

第一章 数组概述 数组介绍1 2 3 41. 数组是多个相同类型数据的组合 2. 数组中的元素可以是任何数据类型,包括基本数据类型和引用数据类型 3. 数组属引用类型,数组中的每个元素相当于该对象的成员变量 4. 数组中的数据是有序的,可以通过序号(索引或者下标)获取,索引从0开始数组…

米筐量化终端是什么?

米筐量化终端大家应该也能想象到是应用的终端&#xff0c;是系统执行的终端环节&#xff0c;如果是用在量化方面&#xff0c;那它就是策略定制的终端&#xff0c;是方便投资者输入量化策略执行出来发最终优质目的&#xff0c;精确到细分股票的账户成交量&#xff0c;股价以及融…

刚当上leader,我让组员去开会,他非说有更重要的会

☆ 职场上经常有那么一种情况就是组长喊组员开会&#xff0c;开周会&#xff0c;开晨会&#xff0c;开各种会&#xff0c;而更有一种常见的情况呢就是组长缺失威严&#xff0c;喊组员开会&#xff0c;组员不听话&#xff0c;说有更重要的会议&#xff0c;不想参加。 ☆ 本文将以…