菜鸟笔试

前言

本场比较思维，第二题属于构造题，主要考察思维灵活度，可以想到奇偶性相同的区间如果区间的长度是偶数，那么他们是一定可以变成任意数的，如果区间的长度是奇数，那么所有为奇数的区间的数的奇偶性一定要相同，否则构造不出来。第三题属于比较经典的题目，考察或的性质， 我们可以发现或的过程中二进制表示中的1是不会减少的，因此我们就暴力就行了

第一题

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

输入描述

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

输出描述

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

示例

输入

3 10

输出

3

说明

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

思路与代码

核心思想是利用二进制位运算来寻找整数的特定位置信息，并找到给定范围内整数的最大位置。

class Main{
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);
}
public 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) {
            res = j;
            break;
        }
    }
    return res;
 }
}

第二题

小红有一个数组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中所有元素相等。

思路与代码

代码的核心思想是通过遍历数组，找到具有相同奇偶性的连续元素序列，然后根据序列的长度和元素的奇偶性来判断是否满足条件。如果所有测试用例都满足条件，输出 "YES"，否则输出 "NO"。

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        scanf("%d",&n);
        int a[n];
        for(int i = 0;i < n;++i) {
            scanf("%d",&a[i]);
        }
        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;
        }
        if(even != 0 && odd != 0) {
            cout << "NO" << endl;
        }else {
            cout << "YES" << endl;
        }
    }
}
int main(){
    solve();
}

第三题

题目：小红有一个长度为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种取值。

思路与代码

这段代码的核心思想是使用无序集合来记录不同子数组的按位或结果，通过不断地将当前元素与已有的按位或结果进行按位或操作来计算不同的按位或组合，最后统计不同按位或结果的不同元素的数量。这个方法能够高效地处理大量数据，避免了生成所有可能子数组的按位或结果。

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    unordered_set<int> st;
    unordered_set<int> tot;
    for(int i = 0;i < n;i++) {
        int a;
        cin >> a;
        unordered_set<int> nst;
        nst.emplace(a);
        for(int b : st) {
            nst.emplace(b | a);
        }
        st = nst;
        for(int b : st) {
            tot.emplace(b);
        }
    }
    cout << tot.size() << endl;
}
int main() {
    solve();
}