网易秋招 2023.09.23 编程题目与题解

发表于 2023-09-25 分类于笔试阅读次数：本文字数： 3.1k 阅读时长 ≈ 3 分钟

1、小红的字符串查询

小红拿到了一个字符串。她有多次查询，每次查询一个区间，你需要回答该区间包含了多少个长度为\(3\)的、所有字母都相等的连续子串。

输入

第一行输入两个正整数\(n,k\)，代表字符率长度和查询次数。

第二行输入一个长度为\(n\)的、仅包含小写字母的字符串。

接下来的\(k\)行，每行输入两个正整数\(l,r\)，代表一次查询。

\(l \le n,k \le 10^5\)
\(1\le l\le r\le n\)

输出

输出\(k\)行，每行输出一个整数表示答案。

样例

输入：
8 4
aaaaabbb
1 8
2 7
3 6
4 5

输出：
4
2
1
0

解答

这题使用前缀和将会变得非常简单。令\(f_i(i\ge 3)\)表示字符串的三个字母\(s_{i-2},s_{i-1},s_{i}\)是否相等，如果相等，那么为\(1\)，否则为\(0\)，其中\(f_1=f_2=0\)。

那么，令\(t_i=\displaystyle{\sum_{j=1}^i f_j},t_0=0\)表示\(f\)的前缀和，因此对于每次询问\(l,r\)，只需要回答值\(\max\{0,t_r-t_{l+1}\}\)即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
char t[N];
int s[N],n,q,l,r;
int main(){
    scanf("%d %d %s",&n,&q,t+1);
    for(int i=3;i<=n;i++){
        if(t[i]==t[i-1]&&t[i]==t[i-2]){
            s[i]=1;
        }
        s[i]+=s[i-1];
    }
    while(q--){
        scanf("%d %d",&l,&r);
        l+=2;
        printf("%d\n",l>r?0:s[r]-s[l-1]);
    }
}

2、小红的数组构造

小红有一个数组，数组相邻元素的差值最多为\(1\)，即\(|a_i-a_{i+1}|\le 1\)，并且数组元素都是正整致，即\(a_i\ge 1\)，现在小红知道数组的长度为\(n\)，数组的和为\(m\)，小红想知道所有符合条件的数组中，\(a_p\)的最大值是多少。

输入

第一行三个整数\(n,m,p\)，表示数组的长度，数组的和，以及要求的位置。

\(1\le p\le n\le m\le 10^9\)

输出

输出一个整数，表示位置\(a_p\)的最大值。

样例

输入：
4 5 2

输出：
2

提示：
数组[1,2,1,1] 满足条件，且位置2的最大值为2。

解答

这道题可以使用二分法进行求解。接下来元素\(a_p\)是否可以取到\(x\)。

为了元素\(a_p\)是否可以取到\(x\)，那么其它元素得值尽可能低。于此同时为了维持相邻元素的绝对差不超过\(1\)这个性质，对于元素\(a_q\)，如果\(q>p\)，那么\(a_q\)就要比\(a_{q-1}\)少\(1\)；如果\(q<p\)，那么\(a_q\)就要比\(a_{q+1}\)少\(1\)，直到恰好为\(0\)。

这种情况是最节省和值的使用的，我们可以通过逐渐为其它元素加上\(1\)，直到总和达到\(m\)，如果总和达不到\(m\)，那么\(a_p\)必定不止\(x\)。因此，我们不需要考虑\(a_p\)的上界。

更一般的来说，如果第\(a_p=x\)，那么最节省和值方法的形状如下：

\[0,0,0,\dots,0,1,2\dots,x-1,x,x-1,x-2,\dots 2,1,0,\dots,0\]

注意，两端可能没有取到\(0\)就结束了。

由于两边的处理方式是一样的，因此只需要考虑其中一侧。令\(f(n,x)\)表示现在有\(n\)个数组元素，其中最后一个元素为\(x\)时，最少需要消耗的和值。按照等差数列求和公式，那么可以写出

\(f(n,x)= \left \{\begin{aligned} &\dfrac{(2x-n+1)n}{2} & & \text{if}\quad x\ge n \\ &\dfrac{(x+1)x}{2} & & \text{if}\quad x<n \\ \end{aligned}\right.\)

因此，判断第\(x\)栋楼高度是否为至少\(h\)，只需要判断\(f(p,x)+f(n-p+1,x)-x\le m\)是否满足即可。

代码

n, m, p = map(int, input().split())


def cal2(n, x):
    if x >= n:
        return (x + x - n + 1) * n // 2
    else:
        return (x + 1) * x // 2


def cal(x):
    return cal2(p, x) + cal2(n - p + 1, x) - x


l, r = 1, m
while l < r:
    mid = (l + r + 1) >> 1
    if cal(mid) <= m:
        l = mid
    else:
        r = mid - 1
print(l)

3、小红的树上路径与

小红拿到了一棵树，她定义一条路径的权值为路径上所有节点权值按位与计算出的值。小红想知道，所有路径的权值之和等于多少？答案请对\(10^9+7\)取模。

输入

第一行输入一个正整数\(n\)，代表树的节点数量。

第二行输入\(n\)个正整数\(a_i\)，代表每个节点的权值。

接下来的\(n-1\)行，每行输入\(2\)个正整数\(u,v\)，代表节点\(u\)和节点\(v\)有一条无向边连接。

\(1\le n\le 10^5\)
\(1\le a_i\le 10^9\)

输出

一个整数，代表所有路径的权值之和。由于答案过大，请对\(10^9+7\)取模。

样例

输入：
3
3 6 4
1 2
2 3

输出：
6

提示：
路径1-2的权值为3&6，管案是2。
路径2-3的权值为6&4，答案是4。
路径1-2-3的权值为3&6&4，管案是0。
因此所有路程的权值之和是2+4=6。

解答

由于不同数位之间的比特都是相互独立的，因此我们对同一数位进行处理即可。

不失一般性，我们只讨论最低位的情况。对于\(u,v\)间的路径的与值为\(1\)，当且仅当\(u,v\)之间所有的节点值都为\(1\)。由于原图是一棵树，因此我们去除所有\(0\)节点后，可以发现这个图变成了一个森林，其中每个连通块都是一棵树。同一连通块下的任意一对节点的与值都为\(1\)，因此我们统计每个连通块的节点数\(c\)后，可以知道这里面一共有\(\dfrac{c(c+1)}{2}\)条路径可以添加到答案中。

这里使用了并查集来求取每个连通块中的节点数。

因此回到原题，假设所有数第\(i\)位做出的贡献为\(v_i\)，那么最终答案为\(\displaystyle{\sum_{i=0}^{\infty}2^i\cdot v_i}\)。

代码

#include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;

const int N=100004;
ll mod=1e9+7;
int fa[N],sz[N],n;
int a[N];
vector<pi>e;
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int u=find(x),v=find(y);
    if(u!=v){
        fa[v]=u;
        sz[u]+=sz[v];
    }
}
ll solve(vector<int>&b){
    for(int i=0;i<n;i++){
        fa[i]=i;sz[i]=1;
    }
    for(auto &[x,y]:e){
        if(b[x]&&b[y])
            merge(x,y);
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        if(b[i]&&i==find(i))
            ans+=1ll*sz[i]*(sz[i]-1)/2;
    }
    return ans%mod;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        e.push_back(pi(x-1,y-1));
    }
    ll ans=0;
    vector<int>b(n);
    for(int i=0;i<30;i++){
        for(int j=0;j<n;j++){
            b[j]=a[j]>>i&1;
        }
        ans=(ans+(solve(b)<<i))%mod;
    }
    printf("%lld\n",ans);

}

4、小红的数列

小红拿到了一个数列，该数列满足以下性质：

\(f(1)=a,f(2)=b\)
\(f(i)=f(i-1)\cdot f(i-2)\cdot c^d\)

请你计算出该数列的第\(n\)项的因子数量。由于答案过大，请对\(10^9+7\)取模。

输入

五个正整数\(a,b,c,d,n\)。

\(l\le a,b,c,d,n\le 10^{12}\)

输出

第\(n\)项的因子数量对\(10^9+7\)取模的值。

样例

输入：
1 2 3 4 3

输出：
10

提示：
第三项是162，共有10个因子。

解答

如果一个数\(n\)可以被分解成\(\displaystyle{n=\prod_{i=1}^m p_i^{e_i}}\)，那么它的因子个数为\(\displaystyle{\sigma_0(n)=\prod_{i=1}^m(e_i+1)}\)。

因此，我们可以考虑找出\(f(n)\)的因式分解，并使用上面的公式进行求解出最终答案。

假设质因子\(p\)在\(n\)的质因数分解出现的次数记为\(g(n,p)\)，令\(f_p(n)=g(f(n),p)\)，那么按照上面\(f\)的式子，我们可以得到：

\[f_p(n)=f_p(n-1)+f_p(n-2)+g(c,p)\cdot d\]

这和斐波那契数列非常像，更一般的，我们将它写成矩阵相乘的形式：

\[\begin{aligned} [f_p(n),f_p(n+1),g(c,p)\cdot d]&=[f_p(n-1),f_p(n),g(c,p)\cdot d]\cdot \begin{bmatrix} 0&1&0\\ 1&1&0\\ 0&1&1\\ \end{bmatrix}\\ &=[f_p(1),f_p(2),g(c,p)\cdot d]\cdot \begin{bmatrix} 0&1&0\\ 1&1&0\\ 0&1&1\\ \end{bmatrix}^{n-1}\\ &=[g(a,p),g(b,p),g(c,p)\cdot d]\cdot \begin{bmatrix} 0&1&0\\ 1&1&0\\ 0&1&1\\ \end{bmatrix}^{n-1} \end{aligned}\]

其中，最后一行通过矩阵快速幂即可完成。

因此，最终答案为\(\displaystyle{\prod_p (f_p(n)+1)}\)。其余的任务就是对\(a,b,c\)进行因式分解，这没有任何难度。

代码

from sympy import factorint

mod = 10 ** 9 + 7


def mul(a: list, b: list):
    return [[sum(a[i][k] * b[k][j] for k in range(len(b))) % mod for j in range(len(b[0]))] for i in range(len(a))]


a, b, c, d, n = map(int, input().split())
fa, fb, fc = dict(factorint(a).items()), dict(factorint(b).items()), dict(factorint(c).items())
mp = {x: [0, 0, 0] for x in list(fa.keys()) + list(fb.keys()) + list(fc.keys())}
for p, e in fa.items():
    mp[p][0] += e
for p, e in fb.items():
    mp[p][1] += e
for p, e in fc.items():
    mp[p][2] += e

ans = 1
for v in mp.values():
    a = [[v[0], v[1], v[2] * d]]
    b = [[0, 1, 0], [1, 1, 0], [0, 1, 1]]
    k = n - 1
    while k:
        if k & 1:
            a = mul(a, b)
        b = mul(b, b)
        k >>= 1
    ans = ans * (a[0][0] + 1) % mod
print(ans)