Codeforces Round #735 (Div. 2) C. Mikasa
2021/7/30 6:07:39
本文主要是介绍Codeforces Round #735 (Div. 2) C. Mikasa,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces Round #735 (Div. 2) C. Mikasa
ps:代码最后调出来来不及交了,没有AC,纯属口嗨 qwq
本质是找个最小的k使得n^k>m
\(n > m\) 则答案为0
下面描述的变化量即为要找的k。
1、找到n最高的值为1且不与m相同的一个二进制位,假设为第x位,代表的值为2^(x-1)
2、若能找到这样的二进制位,因为要使n^k>m,那么n高于该位的值为0的位都应该向m补齐(补齐,即若m此位为1,n此位为0,则应该补为1),低于该位的不做处理(保证n的变化量,即k尽量小)。
3、若找不到这样的二进制位,那么可以以最低的代价造一个这样的二进制位(即找到m的二进制值为0的最低位,把n对应位置变成1),然后再按照上面处理。
明天再交代码试试。
代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; int t; LL n, m; //找二进制为0的最低位 LL ct(LL x) { LL res = 1; while(true) { if ((x & res) == 0) return res; res <<= 1; } } int main() { scanf("%d", &t); while(t--) { scanf("%lld%lld", &n, &m); if (n > m) { printf("0\n"); continue; } //找x代表的值 LL tmp = 1, last = -1; while(tmp <= n) { if ((n & tmp) != 0 && (m & tmp) == 0) { last = tmp; } tmp <<= 1; } LL p = ct(m); if (last == -1) { printf("%lld\n", m+p-n-(m%p)+(n%p)); } else { printf("%lld\n", m-(m%last)-(n-(n%last)-last)); } } }
这篇关于Codeforces Round #735 (Div. 2) C. Mikasa的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21LangChain4j支持的API类型
- 2024-09-21企业如何判断自身的 CRM 系统需要多大的服务器配置?
- 2024-09-21拼接的xml报文,尖括号都被转移成了< 是什么原因-icode9专业技术文章分享
- 2024-09-21Svg Sprite Icon教程:从入门到实践
- 2024-09-21Svg Sprite Icon实战:从入门到上手
- 2024-09-20构建一个多PDF RAG聊天机器人:使用Langchain和Streamlit及代码
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程