Codeforces 2057. 二进制题5
原题链接
简单
作者:
Dessa
,
2025-01-10 17:19:18
,
所有人可见
,
阅读 1
如果这三个数相同,那么对答案贡献为0,如果不都相同,对答案贡献为22^i,直接拿r和l比较,从高位开始,如果出现r的二进制位与l的二进制位不同,那么r的必定是1,l的必定是0,因为r>l,那么之后的所有二进制位r全部设为0,l全部设为1,分别得到a,b,这样才能保证设好的这两个数a,b一定在lr区间内,至于第三个数,可以是a+1,或者b-1,这样才能保证每一位的贡献是22^i
const int N = 1e6 + 10;
string bin2(int n) {
string str = "";
while (n != 0) {
str = to_string(n % 2) + str;
n = n / 2;
}
return str;
}
int bin10(string n)
{
int sum = 0;
for (int i = 0; i < n.size(); i++)
{
if (n[i] == '1')
{
int j = pow(2, n.size() - i - 1);
sum += j;
}
}
return sum;
}
void solve()
{
int l, r; cin >> l >> r;
string sl = bin2(l);
string sr = bin2(r);
while (sr.size() > sl.size()) sl = "0" + sl;
int n = sr.size();
sl = " " + sl;
sr = " " + sr;
int len = 0;
int ok = 0;
for (int i = 1; i <= sr.size(); i++)
{
if (sl[i] != sr[i])
{
ok = i;
break;
}
}
string a, b;
for (int i = 1; i <= n; i++)
{
if (i > ok)
{
a += "0";
b += "1";
}
else
{
a += sr[i];
b += sl[i];
}
}
int oa = bin10(a);
int ob = bin10(b);
if (oa + 1 <= r) cout << oa + 1 << " " << oa << " " << ob << '\n';
else cout << oa << " " << ob << " " << ob - 1 << '\n';
}