情况

时间：2024年7月5日8:00
备注：太难了这场，盯着开赛情况看不对劲，B题又是不熟悉的位运算，想了一小时果断看题解cheat了，狼狈的交了B题。
情况：
image.png

A - Turtle and Piggy Are Playing a Game

题意

区间内选一个整数，看最多被任何数整除多少次。

思路

看了用例，然后想了下感觉和2的n次方有关。找区间内2的n次方的最大n，输出n-1。竟然过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    int l, r;
    cin >> l >>r;
    int target = 0;
    int i;
    for ( i = 1;pow(2,i) <=r;i++){
        }
        if (pow(2, i) < l)
        {
            i--;
        }
        target = i;
        cout << target-1 << endl;
}
//很笨的__lg()函数写法....但好像没弄好外部库，也没了解。
//好像直接用logb这个函数也可以。

其他人的手写写法：

1
2
3
while((1ll<<target)<=r)
        target++;
    cout << target-1 << endl;

B

题意

一个无限序列$a_n = n$
每次操作，同时变化：
$a_i = a_{i-1}|a_{i}|a_{i+1}$
| 是 按位或
输出$a_n$在第m次变化后的值。

思路

每个位置的值的范围是:
左边界：max（0，n-m）
右边界：n+m
左边界肯定比右边界小。
区间按位或有如下结论：
从左往右！找到第一位left为0，且right为1的。该位右边全部取1，即为最终结果。
代码中用r|(2^(i+1)-1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve()
{
    int n, m;
    cin >> n >> m;
    if (m == 0)
    {
        cout << n << endl;
        return;
    }
else{
    int left = max(0, n -m);
    int right = m + n;
    for (int i = 30; i>=0;i--){
        if ((right >> i & 1) && !(left >> i & 1))
        {
            cout << (((1ll << i + 1) - 1)| left) << endl;
            return;
        }
    }
} 

}

问题

想到了传染，但位运算实在不熟练，也没推出来结论。

不补了，去学位运算了。