Bittttttts

[编程题]Bittttttts

热度指数：2530 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

现在有q个询问，每次询问想问你在[l,r]区间内，k进制表示中，k-1的数量最多的数是哪个数。比如当k=2时，9的二进制就是1001，那么他就有2个1.

输入描述:

第一行一个q，表示有q组询问。

接下来q行，每行三个整数k,l,r,分别表示进制数,查询的数字,以及查询的范围。

满足1<=q<=100000,2<=k<=16,1<=l<=r<=10^16

输出描述:

对于每组询问，输出答案。如果有多个答案，请输出最小的。

示例1

输入

1
8 1 100

输出

算法知识视频讲解

Java

_000110hwc

k进制，下限L，上限R，差值d=R-L。

思路是这样的：

先求出上限R的位数b。

if，R等于b位k进制数的最大值(比如5位3进制的22222)，那么输出就是R；

else if，L小于b位k进制数的最小值(比如5位3进制的10000)，那么输出就是(b-1)位k进制数的最大值(比如4位3进制的2222)；

再else，说明L和R的位数一样，用一个长度为b的数组，存储k进制L的各位值。从最低位开始，将各位值改为(k-1)，L的增加量就是d的减少量，如果d<=0，说明无法再增大了，输出并终止循环。

用java写的程序如下：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scn=new Scanner(System.in);
        while(scn.hasNextInt()){
            int q=scn.nextInt();
            for(int t=0;t<q;t++){
                int k=scn.nextInt();
                long l=scn.nextLong();
                long r=scn.nextLong();
                long d=r-l;
                long temp=r;
                int b=1;
                while((temp/=k)!=0) b++;
                if(Math.pow(k,b)-1==r) System.out.println(r);
                else if(Math.pow(k,b-1)>l) System.out.println((long)Math.pow(k,b-1)-1);
                else{
                    temp=l;
                    long[] a=new long[b];
                    for(int j=0;j<b;j++){
                        a[j]=temp%k;
                        temp/=k;
                    }
                    for(int j=0;j<b;j++){
                        d-=(k-1-a[j])*(long)Math.pow(k,j);
                        if(d<=0) System.out.println(l);
                        if(d<=0) break;
                        l=r-d;
                    }
                }
            }
            break;
        }
    }
}

反复考虑过代码应该没问题，pow函数的浮点不确定性也测试过没有影响，但是通过率只有20%（没有超时或内存不足的问题，就是没通过），求教问题出在哪

发表于 2020-06-30 18:41:19 回复(1)

Java

Hachiko123456

用java写的话如果用Scanner去读取数据会超时，所以用了BufferedReader去读取数据，成功AC

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author YHX
 * @date 2019/8/4 17:25
 * description
 */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /**
     * call thReader method to initialize reader for InputStream
     */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    /**
     * get next word
     */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        Reader.init(System.in);
        int n = Reader.nextInt();
        while (n-- != 0) {
            int k = Reader.nextInt();
            long l = Reader.nextLong();
            long r = Reader.nextLong();
            int[] llist = dec2K(l, k);
            long temp = 0;
            long[] longs = new long[1000];
            int cnt = 0;
            while (temp <= r) {
                longs[cnt] = temp;
                temp = temp * k + k - 1;
                cnt++;
            }
            if (longs[cnt - 1] >= l) System.out.println(longs[cnt - 1]);
            else {
                for (int i = 0; i < llist.length; i++) {
                    int tm = llist[i];
                    llist[i] = k - 1;
                    long x = K2Dec(llist, k);
                    if (x > r) {
                        llist[i] = tm;
                        System.out.println(K2Dec(llist, k));
                        break;
                    }
                }
//                System.out.println(ans);
            }
        }
    }

    private static long K2Dec(int[] list, int k) {
        long sum = 0;
        for (int i = list.length - 1; i >= 0; i--) {
            sum = sum * k + list[i];
        }
        return sum;
    }

    private static int[] dec2K(long m, int k) {
        int cnt = 0;
        long mm = m;
        while (mm != 0) {
            mm /= k;
            cnt++;
        }
        int[] list = new int[cnt];
        int j = 0;
        while (m != 0) {
            list[j++] = (int) (m % k);
            m /= k;
        }
//        System.out.println(Arrays.toString(list));
        return list;
    }
}
/*
1000
11 995685164714609 995685164714759
12 2736421049381634 2736421049406512
14 9118803148252731 9118865035350336
2 1999825671666783 2000343892027004
14 7193328445426973 7193328445427058
11 7732658659093208 7732658659093623
9 1480868347971885 1480868506943790
14 3042539992504302 3042540322182591
8 1389231659305990 1399565743027217
14 2932108313570593 7566855981538408
12 7325933386074263 7325933386150179
15 1475130408804666 1475130408814717
4 8369091548439239 8369091832832186
2 584922365242306 584928003053033
11 7722607142326413 7793990995548130
4 6402524556803908 6495021063230295
3 3030210225507683 3030210225507723
13 9258166811155326 9258166811155824
15 9721331831836073 9721331831863924
6 2729140398142086 2729140398194424
13 8051442428579126 8051442520463831
10 7797474285534101 7797474382623448
11 8086464978132222 8086507915606045
6 9943020962485391 9943028723407452
15 5136403641668815 5137054586129716
11 5622258309274901 5622404426526100
8 1536295471800580 2248394876465846
 */

/*
15
4 8442097414683844 8442097414683844
3 3173466882309064 3173466882309073
4 8527527027194177 8527527027194276
4 2661113491247500 2661113491248499
16 4448712248766526 4448712248776525
13 2684426398058983 2684426398158982
14 6562761408288807 6562761409288806
4 2847109288743406 2847109298743405
12 3011167199031338 3011167299031337
7 8655416323525458 8655417323525457
13 177186968879953 177196968879952
2 4133390730537405 4133490730537404
13 4680075382111731 4681075382111730
11 5341708995347620 5351708995347619
8 114951857079067 214951857079066
 */

发表于 2019-08-05 14:48:19 回复(0)