[ABC349D] Divide Interval 题解
题目简述
给定非负整数 \(l\) 和 \(r\)(\(l<r\)),令 \(S(l,r)\) 表示序列 \((l,l+1,\ldots,r-2,r-1)\),其中包含从 \(l\) 到 \(r-1\) 的所有整数。此外,一个序列被称为“好序列”,当且仅当它可以表示为 \(S(2^i j,2^{i}(j+1))\),其中 \(i\) 和 \(j\) 是非负整数。
解题思路
容易看出,使用贪心可以求解这个问题。即从左到右划分序列,每次划分的序列都是最大的即可。具体地,重复执行以下步骤:
- 当前起点为 now。
- 找到最大的合法 \(i\) 值,并反求 \(j\) 值。
- 分离序列 \((2^ij,2^i(j+1))\)。
- 将 now 更新为 \(2^i(j+1)\)。
如何找到最大的合法 \(i\) 值?
我们可以枚举 \(i\),然后判断反推出的 \(j\) 是否合法,当 \(j\) 不合法或此时右边界越界时,就退出枚举。
因为 \(2^i\) 是指数级增长的,所以枚举的次数不会超过 \(60\),不会超时。
注意:
-
需要使用
long long
存储数据。 -
如果使用位运算求解 \(2^i\) ,需要使用
(1LL << i)
,否则会因为爆出int
范围而返回错误值 \(0\)。
AC 代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int l, r;
signed main() {
cin >> l >> r;
int now = l, num = 0;
queue<pair<int,int>>ans;
while (now < r) {
int i = 0;
do { // 枚举 i 值
int pow = (1LL << i);
// 判断合法性
if (now % pow != 0) break;
if (pow * ((now / pow) + 1) > r) break;
} while (++i);
i--, num++;
int pow = (1LL << i);
int j = now / pow;
ans.emplace(pow * j, pow * (j + 1));
now = pow * (j + 1);
}
cout << num << endl;
while (!ans.empty()) {
cout << ans.front().first << " " << ans.front().second << endl;
ans.pop();
}
return 0;
}
标签:int,题解,long,枚举,ABC349D,now
From: https://www.cnblogs.com/Xiang-he/p/18350421