首页 > 其他分享 >XOR Break — Solo Version

XOR Break — Solo Version

时间:2024-03-04 23:35:25浏览次数:23  
标签:Solo 那么 高位 Break Version 如果 操作 最高 对应

这道题目就是纯纯的题面搞人心态,看到\(63\)次操作真的很容易想到从高位到低位一位位进行操作。然而正解却不是

先来看官解

首先每次操作只会将\(n\)变小,所以如果\(m>n\),那么肯定无解;如果\(m=n\)那么不用操作;接下来假定\(m<n\)

如果\(m\)最高位\(1\)和\(n\)最高位\(1\)一样,那么直接令\(y=m,n=y\)即可

如果\(m\)最高位\(1\)在\(n\)次高位\(1\)之后(也可以刚好在次高位\(1\)的位置),那么我们令\(y\)为\(2^b-1\),其中\(b\)是次高位\(1\)所在位置。比如\(n=1001000\),则\(y=1111\)(相当于把次高位\(1\)及其后面的所有位全部变成\(1\)),然后令\(n=y\)。如果此时\(m=n\)那么不用再操作,否则的话就转换为了上一种情况

如果\(m\)最高位\(1\)在\(n\)最高位\(1\)和\(n\)次高位\(1\)之间,那么此时无解,官方解答给出了一个reason,但是看不太懂。。。下面我会说我的证法

然后说说我的想法

很自然的一个想法就是从高到低地考虑,我们还是直接假设\(m<n\)

如果\(m\)最高位\(1\)对应的\(n\)的位为\(1\),那么令\(y=m,n=y\)即可

如果\(m\)最高位\(1\)对应的\(n\)的位为\(0\),那么我们考虑\(n\)比这更高的位的\(1\)的个数

如果\(1\)的个数超过一个,那么我们任取其中两个\(1\),令更高位的\(1\)所对应的位置赋\(0\),更低位的\(1\)所对应的位置赋\(1\),然后再将\(m\)最高位的\(1\)的位置赋\(1\),然后把刚刚得到的数令成\(y\),然后令\(n\)与\(y\)异或,这样\(m\)的最高位就和\(n\)的最高位一样了,就像前面一样操作就好了

如果\(1\)的个数只有一个,那么此时无解,因为如果有解,那么对某种操作序列,一定会存在某次操作,将\(m\)的最高位所对应的\(n\)的位置变成\(1\),即\(y\)在\(m\)的最高位这里要取\(1\),根据题目,此时\(y\)在\(n\)的最高位无论取\(1\)还是\(0\)都是不行的(假设此次操作的时候,\(n\)的更高位仍然只有一个\(1\)),所以我们一定会在这种操作的前面将\(n\)的更高位变成两个\(1\),相当于就是将\(n\)的某一位\(0\)变成\(1\),其实就是上面的过程,然后你会发现就循环论证了,所以不可能

标签:Solo,那么,高位,Break,Version,如果,操作,最高,对应
From: https://www.cnblogs.com/dingxingdi/p/18053012

相关文章

  • 关于SAP-APP机器-R3trans -d报错-R3trans: /lib64/libstdc++.so.6: version `GLIBCXX_
    在SAP-应用-APP-机器上执行如下命令报错awpxxx03:prdadm270>R3trans-dR3trans:/lib64/libstdc++.so.6:version`GLIBCXX_3.4.26'notfound(requiredbyR3trans) 其实之前,使用过一种方法解决这个问题,可以参考笔者另一篇文章《关于Redhat-Linux中-compat-sap-c++的说......
  • Java流程控制11:break、continue、goto
    breakcontinue1.break在任何循环语句的主体部分,均可用break控制循环的流程。break用于强行退出循环,不执行循环中剩余的语句。(break语句也在switch语句中使用)2.continue语句用在循环语句体中,用于终止某次循环过程,即跳过循环体中尚未执行的语句,接着进行下一次是否......
  • Maximum And Queries (hard version)
    首先来介绍一下SOSDP看这篇文章解释一下,最开始的初始化for(inti=0;i<(1<<N);i++)f[i]=w[i];就是0/1背包的的初始化,可以模拟一下想一下为啥然后是DP的过程中,注意f[st^(1<<i)]是肯定不会在这一层被更新的(因为(st^(1<<i))&(1<<i)肯定为\(0\)),所以倒序循环还是正序循环是无所谓的......
  • CF1856E1 PermuTree (easy version) 题解
    假定当前在节点\(u\),它拥有两棵子树\(v,w\),此时\(u\)是\(\operatorname{lca}(v,w)\)。我们一定可以构造出一个排列\(a\),使得所有满足\(i\inv\)的节点\(i\)和满足\(j\inw\)的节点\(j\),有\(a_i<a_u<a_j\)。因此此时点\(u\)对于答案的贡献即为\(size_v\times......
  • Solo 开发者周刊 (第6期):仅需一个动作,秒变时间管理大师?
    这里会整合Solo社区每周推广内容、产品模块或活动投稿,每周五发布。在这期周刊中,我们将深入探讨开源软件产品的开发旅程,分享来自一线独立开发者的经验和见解。本杂志开源,欢迎投稿。产品推荐1.助眠类播客《静夜斋》一款能够愉悦身心,放松心情,帮助你快速入眠的博客节目,建立初衷......
  • Codeforces 1446D1 Frequency Problem (Easy Version)
    考虑求出全局的众数\(A\)。那么有一个结论,就是答案区间的众数中绝对有\(A\)。考虑反证法,如果没有\(A\),\(A\)在序列中出现的个数一定\(\ge\)区间内众数的出现个数,所以可以一直往外扩展直到\(A\)出现的个数与区间内非\(A\)众数的个数持平,这样肯定更优。于是可以考虑钦......
  • Codeforces 1446D2 Frequency Problem (Hard Version)
    考虑求出全局的众数\(A\)。那么有一个结论,就是答案区间的众数中绝对有\(A\)。考虑反证法,如果没有\(A\),\(A\)在序列中出现的个数一定\(\ge\)区间内众数的出现个数,所以可以一直往外扩展直到\(A\)出现的个数与区间内非\(A\)众数的个数持平,这样肯定更优。于是可以考虑钦......
  • [思维] [树形数据结构] CF1379F1 Chess Strikes Back (easy version)
    注意到棋盘大小为$2n,2m$,共$2nm$个白格,同时国王数量为$nm$,尝试将$2$个国王捆绑在一块,即将棋盘均匀划分为若干个$2*2$大小的大格子。在此基础上观察,显然同一个大格子内的两个白格不能同时放置国王,同时大格子数量为$nm$,因此问题转化为判定能否使得所有大格子都有一个国王,......
  • java中的break与continue
    breakbreak:打破结束终止注意事项:1、break不能单独使用,毫无意义2、要在switch语句或者循环语句中使用packagecom.shujia.day03;publicclassBreakDemo{publicstaticvoidmain(String[]args){//需求:循环输出1-5当i为3的时候,使用break......
  • CF1209G2 Into Blocks (hard version) 题解
    Description给你\(n\),\(q\),\(n\)表示序列长度,\(q\)表示操作次数。我们需要达成这么一个目标状态:如果存在\(x\)这个元素,那么必须满足所有\(x\)元素都必须在序列中连续。然后你可以进行这么一种操作,将所有的\(x\)元素的变为任意你指定的\(y\)元素,并且花费\(cnt[x......