洛谷-P9496 题解

正文

在讲解之前，先来几种简单情况：

让 \(n=1\) 转变成 \(m=0\)，只需要让 \(n \land 0\) 即可；

让 \(n=0\) 转变成 \(m=1\)，只需要让 \(n \lor 1\) 即可。

将 \(n\) 扩展成更大的。对于 \(n\) 二进制的每一位数，只需要按上述情况处理即可，而由于可以对任意数进行位运算，所以相同类型的位运算可以合并成一次。

由于只有两种位运算，很容易知道，最终答案 \(ans\in \{0,1,2\}\)。

如果 \(n\) 有一个二进制位需要或，则最终 \(ans \leftarrow ans+1\)，若有一个二进制位需要与，则最终 \(ans \leftarrow ans+1\)。

输出 \(ans\) 即可。

#include<iostream>
using namespace std;
long long n,m;
int T,huo,yu;
int main(){
  ios::sync_with_stdio(false),cin.tie(0);
  cin>>T;
  while(T--){
    cin>>n>>m,huo=0,yu=0;
    for(int i=0;(n>>i)||(m>>i);i++)
      if((n>>i&1)==0&&(m>>i&1)==1) huo=1;
      else if((n>>i&1)==1&&(m>>i&1)==0) yu=1;
    cout<<huo+yu<<'\n';
  } 
}

AC 记录。

后附

日志

v1.0 on 2023.08.07: 发布