CF1981B 题解

ikunTLE · 2024-06-01 08:42:18 · 题解

题目描述

在每个元素 a_i 上执行更新操作，其中 a_i 在 m 秒后变为 a_{i - 1} \operatorname{or} a_i \operatorname{or} a_{i + 1} ，而 a_0 在 m 秒后变为 a_0 \operatorname{or} a_1 。

解题思路

本题的 n,m \le 10^9，想要循环一次都不可能，所以本题的正解是位运算。

每一个点每次最多移动一格，所以我们要求的范围是从 \max(0,n-m) 到 n+m。所以对于每一次特判，我们需要判断是否在上述的范围内。

我们可以从高位到低位一位位地判断，每一次发现符合条件就更新一次答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int t,a,b,ans;
int main(){
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d%d",&a,&b);
        for(int i=30;i>=0;--i)
            if((a+b)>>i&1||max(0,a-b)>>i&1||(a+b-max(0,a-b)>=(1<<i)))//特判
                ans|=(1<<i);//更新答案
        printf("%d\n",ans);
    }
    return 0;
}