【题解】CF1554 Mikasa
2021/7/30 23:10:14
本文主要是介绍【题解】CF1554 Mikasa,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
给你两个整数 n
和 m
,求集合的 mex
。n,m<=1e9
。
Solution:
考点:二进制+模拟。
本人打的 数位 dp
。反正打着很恶心的模拟。
看了标算后豁然开朗:n^x=k <=> n^k<=m
。所以我们只需要检查第一个 n^k>m
的数即可。因为要 k
最小,所以从高到低枚举,取 n^k>=m+1
。
- 如果
n>=m+1
,那么k
取0
都能满足 ,直接break;
- 如果最高位上的数字相同,此时最高位取
0
满足n[i]>=p[i]
- 如果最高位
n[i]=0,p[i]=1
,此时最高位只能填1
- 如果最高位
n[i]=1,p[i]=0
,根据上述条件直接break;
看来还是缺乏思考。
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define ll long long #define PII pair<ll,int> #define All(a) a.begin(),a.end() using namespace std; ll n,m; int main() { ll T; cin>>T; while(T--) { cin>>n>>m; ll res = 0; m++; for(int i = 30; i >= 0 && n < m; i --) { ll t1 = (n>>i) & 1, t2 = (m>>i) & 1; if(t1 == t2) continue; if(t2) res += 1<<i, n |= 1<<i; } cout<<res<<endl; } }
这篇关于【题解】CF1554 Mikasa的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享