提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【Codeforces 484A】Bits

Codeforces Bits
2023-09-14 09:03:44 时间

【链接】 我是链接,点我呀:)
【题意】

让你求出l~r当中二进制表示1的个数最多的数x

【题解】

最多有64位 我们可以从l开始一直增大到r 怎么增大? 找到l的二进制表示当中0所在的位置 假设i这一位的0经过加法变成了1 那么我们再从低位到高位依次枚举那一位为1就好 然后把这个二进制转换成十进制 看看它是不是比ri来的小 如果是,则尝试更新最小值 a[i]=(int)一个long类型的数字%2 a[i]是Int 会出错..

另解
从低位到高位依次让每个0bit都变成1bit
看看新变成的数字是否小于等于ri就好.
如果小于等于,那么就继续尝试让更高位的0变成1
因为是从低位到高位,因此每次增加1个0的代价肯定都是最小的

        cin >>l>>r;
        for(long long i=1;(l|i)<=r;i<<=1)l|=i;
        cout <<l<<endl;

【代码】

import java.io.*;
import java.util.*;

public class Main {
    
    
    static InputReader in;
    static PrintWriter out;
        
    public static void main(String[] args) throws IOException{
        //InputStream ins = new FileInputStream("E:\\rush.txt");
        InputStream ins = System.in;
        in = new InputReader(ins);
        out = new PrintWriter(System.out);
        //code start from here
        new Task().solve(in, out);
        out.close();
    }
    
    static int N = 50000;
    static class Task{
        int n,len;
        long li,ri;
        long Bits[];
        
        public void solve(InputReader in,PrintWriter out) {
        	Bits = new long[100];
        	n = in.nextInt();
        	for (int ii = 1;ii <= n;ii++) {
        		li = in.nextLong();ri = in.nextLong();
        		long ans = li;int ans1 = 0;
        		for (int j = 63;j >= 1;j--){
        			Bits[j] = li%2;
        			li = li/2;
        			ans1 += Bits[j];
        		}
        		
        		//out.println("ans="+ans);
        		//out.println("ans1="+ans);
        		long temp = ans;
        		int temp1 = ans1;
        		long now = 1;
        		for (int j = 63;j >= 1;j--) {
        			temp = temp - now*Bits[j];
        			temp1-=Bits[j];
        			if(Bits[j]==0) {
        				temp1 = temp1+1;
        				temp = temp + now;
        				//out.println("temp="+temp+" now = "+now);
        				if (temp<=ri) {
        					if (temp1>ans1) {
	        					ans1 = temp1;
	        					ans = temp;
        					}else if (temp1==ans1 && temp<ans) {
        						ans = temp;
        					}
        				}
        				long temp2 = 1,cur = 0;
        				for (int k = 1;k <= (63-j);k++) {
        					cur = cur + temp2;
        					if (temp + cur<=ri) {
        						if (temp1 + k > ans1) {
	        						ans1 = temp1 + k;
	        						ans = temp + cur;
        						}else if (temp1+k==ans1 && temp+cur<ans) {
        							ans = temp + cur;
        						}
        					}else break;
        					temp2 = temp2*2;
        				}
        				temp = temp - now;
        				temp1 = temp1-1;
        			}
        			now = now * 2;
        		}
        		out.println(ans);
        		//out.println(ans1);
        	}
        	
        }
    }

    

    static class InputReader{
        public BufferedReader br;
        public StringTokenizer tokenizer;
        
        public InputReader(InputStream ins) {
            br = new BufferedReader(new InputStreamReader(ins));
            tokenizer = null;
        }
        
        public String next(){
            while (tokenizer==null || !tokenizer.hasMoreTokens()) {
                try {
                tokenizer = new StringTokenizer(br.readLine());
                }catch(IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
        	return Long.parseLong(next());
        }
    }
}

相关文章