51nod3047 位移运算 java题解

51nod3047 位移运算 java题解

题目描述

给出两个数a，b。问a能否只通过位移运算（ >>和 << 可以多次使用）变成b。如果可以输出"Yes"，否则输出"No"。

输入 第一行：一个数 t ( 1≤t≤100000)。 第2 ~ t+1行：每行2个a,b中间用空格分隔（0≤a, b≤10^9）。 输出 输出共t行，对应答案的"Yes"和"No" 数据范围 对于20%的数据，1≤t≤50，0≤a, b≤20； 对于40%的数据，1≤t≤2000； 对于100%的数据，1≤t≤100000，0≤a, b≤10^9； 输入样例 4 4 2 2 4 3 4 1 3 输出样例 Yes Yes Yes No

解题思路

规律：二进制b去掉末端连续0以后，总是二进制a的一部分 故我们把a和b都转换成二进制字符串，截取b串有效部分去匹配a串就可以了

原来的思路：二进制b去掉末端连续0以后，总是二进制a的一部分 故我们把a和b都转换成二进制字符串，截取b串有效部分去匹配a串就可以了

import java.util.Scanner;import static java.lang.Math.log;public class code16 { public static String bijiao(int n){ //二进制倒序 String s=""; for (int i = 0; n>0 ; i++) { s+=n%2; n/=2; } return s; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); //输入n表示N行数字 int n = sc.nextInt(); int[] brr = new int[n * 2]; int t = 0; for (int i = 0; i < n; i++) { int flag = 0; int a = sc.nextInt(); int b = sc.nextInt(); if (a == b) { flag = 1; } else if (a >= 1) { //进行特殊处理 { String s1 = bijiao(a); String s2 = bijiao(b); //只用把s2的字符串转移成数组 char[] array = s2.toCharArray(); int j=0; //当j++不是0时候退出 while(array[j++]=='0'); s2=s2.substring(j-1); //如果s1包含s2 if (s1.contains(s2)) { flag = 1; } } } if (flag == 1) { System.out.println("Yes"); } else { System.out.println("No"); } } }}

结果提交显示

后来检查发现是

​​while(array[j++]=='0'); s2=s2.substring(j-1);​​ 这两行代码的事情，

当b是0的时候要特殊处理

AC代码

import java.util.Scanner;public class code16 { /** * 测试 * */ public static String bijiao(int n){ //二进制倒序 String s=""; for (int i = 0; n>0 ; i++) { s+=n%2; n/=2; }// System.out.println(s); return s; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); //输入n表示N行数字 int n = sc.nextInt(); for (int i = 0; i < n; i++) { int flag = 0; int a = sc.nextInt(); int b = sc.nextInt(); //进行特殊处理 if (b == 0 ) { flag = 1; } else{ String s1 = bijiao(a); String s2 = bijiao(b); //只用把s2的字符串转移成数组 char[] array = s2.toCharArray(); int j=0; //当j++不是0时候退出 while(array[j++]=='0'); s2=s2.substring(j-1); //如果s1包含s2 if (s1.contains(s2)) { flag = 1; } } if (flag == 1) { System.out.println("Yes"); } else { System.out.println("No"); } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。