菜鸟1025秋招笔试

菜鸟1025秋招笔试

还是挺思维的，套路不是很明显；主要考察的是灵活度，下面详细地来看看。

​

1025.T1

1. 题目说明

小红喜欢偶数，即一个数从因数分解的角度来看，其中的偶数因子越多，她就越喜欢这个数。也就是x=PiXP2X…XPk，其中Pi 都是偶数，那么大的最大值就是小红对这个数的喜欢程度。小红想知道区间[l,r]的数中，小红对哪个数的喜欢程度最高，输出小红的喜欢程度。

输入描述

一行两个整数l,r，表示区间[l,r]。1≤l≤r≤10^9

输出描述

输出一个整数，表示小红对这个数的喜欢程度。

示例

输入

3 10

输出

3

说明

小红最喜欢的数是8，喜欢程度是 3，因为8=2X2X2。

​

2. 分析解答

• 实际上求的是偶数的因子，这里利用二进制的思想对数进行划分即可。

• 利用的是二进制的位运算来寻找整数的特定位置的信息，找出给定范围内的整数的最大值。

  ​

3. 具体代码

import java.util.Scanner;

public class title1 {
    
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int l=in.nextInt(),r=in.nextInt();
        int res=0;
        for(int i=l;i<=r;i++){
            res=Math.max(res,getRes(i));
        }
        System.out.println(res);
    }

    private static int getRes(int n){
        int res=0;
        int i=Integer.lowestOneBit(n);//整数的最大位置
        for(int j=0;j<32;j++){
            if(((i>>j)&1)==1){ //判断这里的位置是否为1
                res=j;
                break;
            }
        }
        return res;
    }
}

• 复杂度分析：

  • 时间复杂度：$O((r-l+1)log_2r)$

    • 首先，主函数中的 for 循环会执行 (r−l+1) 次，每次调用 getRes 函数，因此 getRes 函数的时间复杂度需要分析。在 getRes 函数中，首先使用 Integer.lowestOneBit(n) 函数找到整数 n 的最大位置，该函数的时间复杂度为 $O(log_2n)$。

    • 接着，使用一个循环遍历 32 个二进制位，判断最大位置所在的二进制位，循环次数为常数级别，即 $O(1)$。因此，getRes 函数的总时间复杂度为 $O(log_2n)$。

  • 空间复杂度：$O(1)$

    空间复杂度上，只使用了常数个变量，因此为 $O(1)$。

    ​

1025.T2

1. 题目说明

小红有一个数组a，每次可以进行以下两种操作：

1. 选择一个下标i，将ai加二，即ai =ai+2。

2. 选择一个下标i，如果ai=ai+1，将ai和ai+1加1，即ai=ai+1，ai +1 =ai+1 +1;否则不能进行 操作。

小红可以进行若千次操作，小红想知道能否通过若干次操作使得数组 a中所有元素相等。

输入描述

第一行一个整数t，表示数据组数。

接下来t组数据，每组数据第一行一个整数 n，表示数组长度。 接下来一行n个整数 a1，a2，… ,an，表示数组 a 的初始值。

1≤t≤10 1≤n≤10^5 1≤ai≤10^9

输出描述

输出t行，每行一个字符串，如果能使得数组 a 中所有元素相等，输出“YES"，否则输出“NO"。

示例

输入

3 
3
1 2 3
3
1 1 3
3
2  2 3

输出

NO
YES
YES

说明

• 第一组，无法通过操作使得数组 a 中所有元素相等。

• 第二组，对i= 1，2 各执行一次操作一，即可使得数组a中所有元素相等

• 第三组，对i=1各执行一次操作二，即可使得数组a中所有元素相等。

  ​

2. 解答分析

• 对于单独的一个数，可以实现+2的处理，换句话说，也就是不改变该数字的奇偶性，单纯地增加而已。

• 对于连续相等的两个数，可以各自都+1，相当于改变这两个数的奇偶性。

• 同时注意找到连续相等的区间序列的奇偶性：

  • 如果区间的长度是偶数，那么他们是一定可以变成任意数的；

  • 如果区间的长度是奇数，那么所有为奇数的区间的数的奇偶性一定要相同，否则构造不出来。

    ​

3. 具体代码

import java.util.Scanner;

public class title2 {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int t=in.nextInt(); //组数
        while(t-->0){
            int n= in.nextInt(); //每组中的元素
            int[] a=new int[n]; //给出每组的数组定义
            for(int i=0;i<n;i++){
                a[i]=in.nextInt(); //数组
            }
            int odd=0,even=0; //确定输入的数组中的奇数和偶数
            for(int i=0;i<n;){
                int j=i;
                while(j<n && a[j]%2==a[i]%2){
                    j++;//找到连续的相同奇偶性的序列
                }
                if((j-i)%2==1){// 序列的长度的是奇数的话，区间内的奇数偶数性一定要相同才可以。
                    if(a[i]%2==0){
                        even++; //偶数个数
                    }else{
                        odd++; //奇数个数
                    }
                }
                i=j; //将i更新为j，以便跳过已经处理过的子数组
            }
            if(even!=0 && odd!=0){
                System.out.println("NO");
            }else{
                System.out.println("YES");
            }
        }
    }
}

• 复杂度分析：

  • 时间复杂度：$O(t*n)$，(外层循环+内层循环)

  • 空间复杂度：$O(1)$

    ​

1026. T3

1. 题目说明

题目：小红有一个长度为n的数组a，记子区间[l,r]的权值为al|al+1|…|ar，即区间内所有数的按位或运算的结果.一共有 nx(n+ 1)/2 个子区间，小红想知道对应的n(n +1)/2 个权值中，有多少个不同的取值。

输入描述:

第一行一个整数 n，表示数组长度。 第二行n个整数 a1,a2，… ,an，表示数组a的元素 1≤n≤10^5 1 ≤ ai≤10^9

输出描述：输出一个整数，表示不同的取值个数。

示例：

输入

3
1 2 4

输出

6

说明：

[1,1]的权值为 1
[1,2] 的权值为 3
[1,3]的权值为 7
[2,2]的权值为 2
[2,3]的权值为6
[3,3]的权值为4
权值两两不同，共有6种取值。

​

2. 解答分析

• 相当于是寻找不同的数字元素的集合，这里直接想到的方法是使用HashSet，确保存储的数字的唯一性。

• 同时，每当进行或的时候，出现新的组合的时候，可以在Set中返回存储新的数字。

• 我们可以发现或的过程中二进制表示中的1是不会减少的，因此我们就暴力就行了。

  ​

3. 具体代码

import java.util.HashSet;
import java.util.Scanner;

public class title3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashSet<Integer> st = new HashSet<>();
        HashSet<Integer> tot = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            HashSet<Integer> nst = new HashSet<>();
            nst.add(a);
            for (int b : st) {
                nst.add(b | a);
            }
            st = nst;
            for (int b : st) {
                tot.add(b);
            }
        }
        System.out.println(tot.size());
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n^2log_2a)$

    • n是数组的长度，a代表的是当前循环中迭代中的整数值。

    • 具体来说，外层循环遍历了数组中的每个元素，内层循环遍历了之前所有元素的按位或结果，因此内外层循环的总次数是 $O(n^2)$。

    • 对于每个元素，内层循环需要将当前元素与之前所有元素的按位或结果进行按位或操作，因此内层循环的时间复杂度为 $O(nlog_2a)$，其中 $log_2a$ 是计算按位或的时间复杂度。 因此总时间复杂度为$O(n^2log_2a)$。

  • 空间复杂度：$O(n^2log_2a)$

    y由于使用了HashSet的数据结构来实现去重的效果，空间复杂度如上。

    ​

在上班期间摸鱼写的hhh，继续努力吧~

END~