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

D1. XOR Break — Solo Version

时间:2024-07-12 11:33:36浏览次数:14  
标签:Solo ll long Break Version solve bit

原题链接

题解,构造太难想了

当 \(x\) 在二进制表示下,只有一个1时,肯定不行
如果有两个1呢?
在这种情况下,如果 \(m\) 最大的一位,位于 \(x\) 最大的一和第二大的一之间,一定失败
为什么?
分类讨论即可

反之是否成立?
设 \(x\) 最大的一位 \(a\),第二大的位 \(b\)
\(m\) 最大的一位 \(c\)

如果 \(c==a\),那么 \(m\oplus x<x\) 一定成立(\(m<x\) 且最高位为零),所以可以直接输出 \(m\)
如果 \(c<=b\),那么我们可以先得到一个中间值 \(2^{b+1}-1\) ,然后发现可以直接得到 \(m\)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;


void solve()
{
    vector<int> n_bit,m_bit;
    ll n,m;
    cin>>n>>m;
    bool same=0,dif=0;
    for(ll i=63;i>=0;i--)
    {
        if((n>>i)&1)
        {
            n_bit.push_back(i);
        }
        if((m>>i)&1)
        {
            m_bit.push_back(i);
        }
    }
    int hi=m_bit[0];
    if(n_bit.size()==1)
    {
        cout<<"-1\n";
        return;
    }
    if(hi==n_bit[0])
    {
        cout<<1<<'\n'<<n<<' '<<m<<'\n';
        return;
    }
    if(hi<n_bit[0])
    {
        if(hi>n_bit[1])
        {
            cout<<"-1\n";
            return;
        }
        else
        {
            ll mid=(1LL<<(n_bit[1]+1))-1;
            if(mid==m)
            {
                cout<<1<<'\n'<<n<<' '<<m<<'\n';
                return;
            }
            cout<<2<<'\n'<<n<<' '<<mid<<' '<<m<<'\n';
            return;
        }
    }


    cout<<1<<'\n'<<n<<' '<<m<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}


标签:Solo,ll,long,Break,Version,solve,bit
From: https://www.cnblogs.com/pure4knowledge/p/18297953

相关文章

  • Solo 开发者周刊 (第13期):独立开发者的创新集——橘猫、记一杯与Newcar
    这里会整合Solo社区每周推广内容、产品模块或活动投稿,每周五发布。在这期周刊中,我们将深入探讨开源软件产品的开发旅程,分享来自一线独立开发者的经验和见解。本杂志开源,欢迎投稿。产品推荐1、橘猫起始页——一款不一样的浏览器标签页功能介绍极简首屏聚合搜索,支持快捷......
  • Go 语言 UUID 库 google/uuid 源码解析:UUID version4 的实现
    google/uuid库地址本文将解析googl/uuid库中UUID变体10版本4的实现。版本4的UUID采取完全随机的方式实现,简单来说就是将UUID中的122位全部随机填充(剩余的6位作标记位)。版本4的UUID存在一定的重复风险,但就如源码注释中所说:“一年内创建几十万亿个UUI......
  • Crontab定时任务更新SOLO以及备份数据库
    Linux定时执行任务Crontab1.安装Crontab1.1安装命令#vixie-cron软件包是cron的主程序yuminstallvixie-cron#crontabs软件包是用来安装、卸装、或列举用来驱动cron守护进程的表格的程序yuminstallcrontabs1.2启动命令#启动服务/sbin/servicecrondstar......
  • 【Azure App Service】访问App Service应用报错 SSL: WRONG_VERSION_NUMBER
    问题描述应用部署在AzureAppService中,访问DefaultURL,遇见SSL:WRONG_VERSION_NUMBER错误。RESTAPI工具调用时错误信息:writeEPROTO8936192:error:100000f7:SSLroutines:OPENSSL_internal:WRONG_VERSION_NUMBER:..\..\third_party\boringssl\src\ssl\tls_record.cc:231:......
  • Nerdbank.GitVersioning .net 版本自动生成工具
    在.NET7中使用Nerdbank.GitVersioning进行版本控制,可以按照以下步骤进行配置:安装Nerdbank.GitVersioning包:使用NuGet包管理器控制台安装该包: Install-PackageNerdbank.GitVersioning安装nbgv工具:使用.NETCLI安装nbgv工具:dotnettoolinstall-gnbgv......
  • break与continue与goto
    break:强制退出循环,不执行循环中剩余语句,可以在任何循环体中的主体部分inti=0;while(i<100){i++;System.out.print(i+"\t");if(i==5){break;}}System.out.println("123"......
  • ARC180E LIS and Inversion
    题目大意一个排列\(p\)分数为\(p\)的最长上升子序列的长度,代价为满足\(\sum_{j=1}^{i-1}[p_j>p_i]<a_{i}\)的\(i\)的数量给定\(\{a_n\}\),对于\(\forallk\in[1,n]\),求分数大于等于\(k\)的排列的代价的最小值\[n\leq250000,1\leqa_i<i\]题解玄妙优化\(dp\)题我们可以考虑求......
  • 【C语言】break 关键字
    当在C语言中使用break关键字时,它通常用于两种主要情况:在循环中和在switch语句中。让我们详细看看每种情况下的用法和作用。在循环中的使用:在循环中,break语句的作用是立即终止当前所在的循环,然后跳出循环体执行循环后面的代码。这对于在达到某个条件后停止循环非常有用。......
  • 丝滑解决ImportError: /usr/lib/x86_64-linux-gnu/libstdc++.so.6: version `GLIBCXX_
    基础环境:MacOSm1、python=3.9前情提要:在Anaconda终端运行代码的时候,显示报错:importError:/usr/lib/x86_64-linux-gnu/libstdc++.so.6:version`GLIBCXX_3.4.29'notfound1问题分析:根据提示是/usr/lib/x86_64-linux-gnu/路径下的libstdc++.so.6缺少版本GLIBCXX_3.4.29解......
  • Nanami and the Last Enigma (hard version)
    如果从前缀和的视角考察题目中需要统计的信息,那么子段和=x等价于s[r]-s[l-1]=x于是我们虽然不能O(1)地求出w(l,r),但是可以O(1)地将已知的w(l,r)扩展w(l,r)是一个非常明显的满足“包含大于等于交叉”的四边形不等式的函数,除此之外,通过打表找规律,也可以发现DP有决策单调性决策单......