阿里菜鸟秋招 2023.10.25 编程题目与题解

发表于 2023-10-30 分类于笔试阅读次数：本文字数： 2.2k 阅读时长 ≈ 2 分钟

1、小红的偶数

小红喜欢偶数，即一个数从因数分解的角度来看，其中的偶数因子越多，她就越喜欢这个数。也就是，\(x=p_1 \times p_2 \times\dots\times p_k\)，其中\(p_i\)都是偶数，那么\(k\)的最大值就是小红对这个数的喜欢程度。小红想知道区间\([l,r]\)的数中，小红对哪个数的喜欢程度最高，输出小红的喜欢程度。

输入

一行两个整数\(l,r\)，表示区间\([l,r]\)。

\(1\le l\le r \le 10^9\)

输出

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

样例

输入：
3 10

输出：
3

提示：
小红最喜欢的数是8，喜欢程度是3，因为8=2×2×2。

解答

对于一个正整数\(n\)，假设\(n\)有\(k\)个质因子\(2\)，那么存在一个题目中要求的分解，其中\(p_1=p_2=\dots=p_{k-1}=2,p_k=\dfrac{n}{2^{k-1}}\)，并且这时的\(k\)已经达到最大。

因此，为了判断区间\([l,r]\)中是否存在一个整数，其喜欢程度为\(k\)，只需要判断\(2^k\)是否能整除\([l,r]\)中的一个数即可。

基于前缀和的思想，我们可以知道，在\(1\sim n\)这\(n\)个数中，有\(\lfloor n/d\rfloor\)个数是\(d\)的倍数。

因此，如果\(2^k\)整除区间\([l,r]\)中的某一个数，那么就会有\(\lfloor r/2^k\rfloor\neq \lfloor(l-1)/2^k\rfloor\)。

代码

l, r = map(int, input().split())
ans = 0
for i in range(34):
    if (r >> i) != ((l - 1) >> i):
        ans = i
    else:
        break
print(ans)

2、小红的数组

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

选择一个下标\(i\)，将\(a_i\)加\(2\)，即\(a_i = a_i+2\)。
选择一个下标\(i\)，如果\(a_i= a_{i+1}\)，将\(a_i\)和\(a_{i+1}\)加\(1\)，即\(a_i = a_{i}+1,a_{i+1} = a_{i+1}+1\)；否则不能进行操作。

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

输入

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

接下来\(t\)组数据，每组数据第一行一个整数\(n\)，表示数组长度。

接下来一行\(n\)个整数\(a_1,a_2,\dots,a_n\)，表示数组\(a\)的初始值。

\(1\le t\le 10\)
\(1 \le n \le 10^5\)
\(1 \le a_i \le 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中所有元素相等。

解答

使用操作一，我们可以将\(a\)中的所有数全都提高到足够大的地步，得到如下数组\(a'\)：

\(\forall i\in[1,n],a'_i\)的奇偶性和\(a_i\)相同。
奇偶性相同的两个下标\(i,j\)满足\(a'_i=a'_j\)。

此时数组中元素的差不会超过\(1\)。通过更进一步可以发现，本质上操作一的存在可以随意调整数组\(a\)中的大小，只有通过操作二才能改变元素的奇偶性。因此，令\(b_i=a_i\bmod 2\)，那么操作二可以视为是对相同的\(b_i,b_{i+1}(i<n)\)都进行翻转。

接下来将\(b\)中的数按照相同的数分成一段段，计算每一个段的长度，得到一个长度为\(m\)的数组\(c\)。对于一次操作二，观察数组\(c\)的变化，可以发现，\(c\)中奇数下标的元素和和偶数下标的元素和的奇偶性总是不变的。

如果\(c\)中奇数下标的元素和和偶数下标的元素和都是奇数，那么无论通过多少次操作二，\(b\)总会存在两个相邻的段，其长度都是奇数，因此这时的数组是不满足条件的。否则，只需要一系列的操作二，\(b\)中只会剩下一个长度为奇数的段，这时只需要将其它段都执行操作二即可满足题目条件。

代码

# include <bits/stdc++.h>
using namespace std;
const int N=100004;
int a[N],c[N],n;
int d[2];
bool solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]&=1;c[i]=0;
    }
    int pre=a[1],m=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(pre==a[i]) ++cnt;
        else{
            c[++m]=cnt;
            cnt=1;
        }
        pre=a[i];
    }
    c[++m]=cnt;
    d[0]=d[1]=0;
    for(int i=1;i<=m;i++){
        if(c[i]&1) d[i&1]=1;
    }
    return (d[0]&d[1])==0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        puts(solve()?"YES":"NO");
    }
}

3、小红的子数组权值

小红有一个长度为\(n\)的数组\(a\)，记子区间\([l,r]\)的权值为\(a_l|a_{l+1}|\dots|a_r\)，即区间内所有数的按位或运算的结果。一共有\(n\times(n+1)/2\)个子区间，小红想知道对应的\(n\times(n+1)/2\)个权值中，有多少个不同的取值。

输入

第一行一个整数\(n\)，表示数组长度。

第二行\(n\)个整数\(a_1,a_2,\dots,a_n\)，表示数组\(a\)的元素。

\(1 \le n \le 10^5\)
\(1 \le a_i \le 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种取值。

解答

本题是Leetcode 898的原题。对于任意一个下标\(r\)，可以发现，以\(r\)为最后一个元素的子数组最多只有\(\log M\)个不同的权值，其中\(M\)是数组\(a\)的最大值。这是因为根据或运算的性质，对原来的或之和多或上一个数只会将原来的或之和的某些\(0\)比特置换成\(1\)比特（反之不可行）。

因此从左到右枚举下标\(r\)，我们可以维护一个集合\(R_r\)用来表示以\(r\)为终点的子数组的不同权值，这个集合可以由\(R_{r-1}\)得出，并且为\(R_r=\{x\mid a_r:x\in R_{r-1}\}\cup\{x\}\)。可以发现\(R_r\)的大小永远不会超过\(\log M\)。最终将所有\(R_r\)的集合求并集然后输出大小即可。

代码

# include <bits/stdc++.h>
using namespace std;
const int N=100004;
int a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    unordered_set<int>st,suf,t;
    for(int i=1;i<=n;i++){
        t.clear();
        t.insert(a[i]);
        for(int x:suf) t.insert(x|a[i]);
        for(int y:t) st.insert(y);
        suf=t;
    }
    printf("%d\n",st.size());
}