題目描述
There is a new attraction in Singapore Zoo: The Infinite Zoo.
The Infinite Zoo can be represented by a graph with an infinite number of vertices labeled 1,2,3,…. There is a directed edge from vertex u to vertex u+v if and only if u&v=v, where & denotes the bitwise AND operation. There are no other edges in the graph.
Zookeeper has q queries. In the i-th query she will ask you if she can travel from vertex ui to vertex vi by going through directed edges.
Input
The first line contains an integer q (1≤q≤105) — the number of queries.
The i-th of the next q lines will contain two integers ui, vi (1≤ui,vi<230) — a query made by Zookeeper.
Output
For the i-th of the q queries, output “YES” in a single line if Zookeeper can travel from vertex ui to vertex vi. Otherwise, output “NO”.
You can print your answer in any case. For example, if the answer is “YES”, then the output “Yes” or “yeS” will also be considered as correct answer.
Example
input
5
1 4
3 6
1 6
6 2
5 5
output
YES
YES
NO
NO
YES
Note
The subgraph on vertices 1,2,3,4,5,6 is shown below.
題目描述
有一個序列1,2,3,……,正無窮，u可以到u+v當且僅當u&v=v，有q個查詢，每個查詢給出兩個點u和v，問u是否能到v，
題目分析
首先我們可以確定，如果u能到v，那么v一定大于u，因為所有邊都是
u
?
>
u
+
某
個
數
u->u+某個數
u?>u+某個數 得到的，條件1：v>=u
然后我們分析一下每個點之間的聯通條件，
以3為例，3可以到3+1、3+2和3+3，我們可以發現：一個數（二進制）的所有1的位置都可以向左移動，但是不能夠向右移動，
條件2：u和v(二進制)的1從右向左進行一一對應，如果u中的所有1所對應的v中的1，全部都大于u中對應的1的話，那么u可以到v，
舉例：6(110)可以到達6+2，6+4和6+6，但是6到不了7(111)和9(1001)，
代碼如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e4+5,mod=1e9+7;
bool check(int u,int v)
{
int a=0,b=0; //a記錄u中當前未匹配的個數，b記錄v中當前未匹配的個數
for(int i=0;i<31;i++)
{
if(u>>i&1) a++; //如果當前位上有1，那么進行記錄
if(v>>i&1) b++;
if(b) //如果b中有元素了
{
if(!a) return false; //但是a中還沒有元素，那么說明與當前位匹配的u中的1要大于該位，不合法
a--,b--; //否則匹配成功
}
}
return true;
}
int main()
{
int q;
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
if(u<=v&&check(u,v)) puts("YES"); //利用條件1,2進行匹配
else puts("NO");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/265438.html
標籤：其他