CodeForces 276D – Little Girl and Maximum XOR 贪心
整整10个月后第二次搞这个问题才搞懂........第一次还是太随意了。
解题思路:
经过打表可得规律答案要么是0 要么是2的N次 - 1
要得到最大的XOR值,其值一定是2的N次 - 1
即在 l 和 r 的二进制中,从左到右遍历过去,如果碰到 (2 ^ i) & l 为 1 , (2 ^ i) & r 为 0
即在 l 和 r 之间一定存在 形如 10+ 和01+这样的数。
则可说明在[l , r]中存在 1000000000 和 0111111111 可得到最大XOR值为2的N次 - 1
PS:不会存在首先出现 l 为 0 r 为 1 的情况,因为 l < r
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max (a,b) (((a) > (b)) ? (a) : (b))
#define Min (a,b) (((a) < (b)) ? (a) : (b))
#define Abs (x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template <class T> inline void checkmin (T &a,T b) { if (a > b) a = b; }
template <class T> inline void checkmax (T &a,T b) { if (a < b) a = b; } const double eps = 1e- ;
const int N = ;
const int M = ;
const ll P = 10000000097ll ;
const int INF = 0x3f3f3f3f ; int main(){
int i, j, k, t, n, m, numCase = ;
ll l, r;
while (cin >> l >> r){
for (i = ; i >= ; --i){
if ((l & (1LL << i)) ^ (r & (1LL << i))) break;
}
ll ans = pow (, i + ) - ;
cout << ans << endl;
} return ;
}
题目描述
A little girl loves problems on bitwise operations very much. Here's one of them.
You are given two integers l and r. Let's consider the values of for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.
Expression means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as «xor».
输入
The input consists of multiple test cases.
Each test case contains space-separated integers l and r (1 ≤ l ≤ r ≤ 1018).
输出
In a single line print a single integer — the maximum value of for all pairs of integers a, b (l ≤ a ≤ b ≤ r).
---恢复内容结束---
题目描述
A little girl loves problems on bitwise operations very much. Here's one of them.
You are given two integers l and r. Let's consider the values of for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.
Expression means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as «xor».
输入
The input consists of multiple test cases.
Each test case contains space-separated integers l and r (1 ≤ l ≤ r ≤ 1018).
输出
In a single line print a single integer — the maximum value of for all pairs of integers a, b (l ≤ a ≤ b ≤ r).
最新文章
- php cryptr 加密函数
- C++ win32线程数上限
- 利用Hexo搭建个人博客-博客初始化篇
- 【noip 2016】 组合数问题(problem)
- About “this” of Javascript
- PHP抓取及分析网页的方法详解
- 5、android ConnectivityManager获取网络状态
- 解决eclipse+git中每次clean项目需要重新commit文件
- NBUT 1673 迷宫问题(DP)
- 获取iOS设备信息的编程接口
- Spring Boot - Font Awesome OTS parsing error: Failed to convert 字体加载失败
- linux 命令之文件读取,head, tail, tailf, sed
- 痞子衡嵌入式:恩智浦LPC系列MCU开发那些事 - 索引
- 浅析data:image/png;base64的应用
- 新版的 selenium已经放弃PhantomJS改用Chorme headless
- MIME Types - Complete List
- 【转载】kafka 基础知识
- spring boot 集成 druid
- POJ 1014 Dividing (多重可行性背包)
- Docker容器的原理与实践(上)