codeforces 2082B 题解

前言

好像是很久之前就没做出来的一道题（div2.B，鬼知道我那场掉了多少分），今天补的时候的想法和赛时一摸一样的，结果一摸一样的WA2了。题目其实不难（毕竟是div2.B），但是有些思维点还是挺关键的。

题意

有一个数x，可以对其执行n次除以二向下取整的操作和m次除以二向上取整的操作，求任意顺序操作后x的最小值和最大值。

赛时思路

n和m很大，但实际上x只要0之后就不需要考虑剩下的操作，暴力的复杂度应该为$O(logx)$.

赛时我用了个假贪心，求最小值时当x为奇数且n、m均大于0就向下取整，否则就向上取整；求最大值时当x为偶数且n、m均大于0就向下取整，否则就向上取整。

为什么这个贪心是错的？

考虑下面一组样例

3 1 2

求最小值时，对于x=3为奇数，我们先执行了向上取整，得到2；

x=2为偶数，我们向下取整得到1；

x=1为奇数，我们向上取整，值不变，最终结果为1.

但是显然，对x=3进行两次除以二向上取整后得到1，再进行向下取整可以得到0，这是一个更优的答案。

思路

根据除以二的操作联想到二进制

举个例子，$x=12=(1100)_2\ , n=1,\ m=2$

不管我们以什么样的顺序进行操作，最高位的1是保留的。

后面的(n+m)位呢？

进行n+m次位移后，后（n+m）位得到的结果一定为0或1.其中如果希望得到1，最后一次操作一定为除以二向上取整；

可以得到结论，先进行n次除以二向下取整操作，后进行m次除以二向上取整操作，最终得到的一定是最大值

同样，先进行m次除以二向上取整操作，后进行n次除以二向下取整操作，最终得到的一定是最小值

#include <bits/stdc++.h>

using namespace std;

int x, n, m;
void solve(int to, int e) {
    cin >> x >> n >> m;
    int tx = x, tn = n, tm = m;
    while(tx > 1 and tm > 0) {
        tx = tx + 1 >> 1;
        tm--;
    }

    while(tx and tn > 0) {
        tx = tx >> 1;
        tn--;
    }

    cout << tx << ' ';

    tx = x, tn = n, tm = m;
    while(tx and tn > 0) {
        tx = tx >> 1;
        tn--;
    }

    while(tx > 1 and tm > 0) {
        tx = tx + 1 >> 1;
        tm--;
    }

    cout << tx << '\n';
}

int main() {
    int t;  cin >> t;
    for(int i = 1; i <= t; ++i) {
        solve(t, i);
    }

    return 0;
}

后记

除了整道题目的大思路，这道题还有一些小细节，比如在向上取整时，如果x值为1，程序可能会连续执行m（最大为1e9）次操作，这是不能接受的，因此应该在x<=1时立即跳出循环。对于向下取整的部分，x非零即可。

最终复杂度 $O(logx)$，也许有$O(1)$的数学做法，但我没有去验证过。

这道题前前后后WA + TLE一共10发，其中WA的部分都是思路的问题。