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

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

1、小红的有序数组

小红有一个长度为\(n\)的数组，数组下标为\(0\)到\(n-1\)，每次可以交换下标为\(i\)和\((i+ 2)\%n\)的数，请问小红能否通过有限次交换使得数组变成一个单调不减的数组。

输入

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

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

每组数据第二行\(n\)个整数\(a_i\)，表示数组的值。

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

输出

对于每组数据，如果能够通过有限次交换使得数组变成一个单调不减的数组，输出"YES"，否则输出"NO"。

样例

输入：
2
4
1 4 3 2
4
4 3 2 1

输出：
YES
NO

提示：
第一组数据，交换下标为1和3的数，变成[1,2,3,4]单调不减。

解答

首先我们可以知道有如下性质：交换关系是有传递性的，即如果下标为\(x\)和\(y\)的元素能够进行交换，\(y\)和\(z\)的元素能够进行交换，那么\(x\)和\(z\)的元素也是能够进行交换的。

因此对于\(n\)的奇偶性，我们分两种情况进行讨论：

当\(n\)为奇数时，对于\(i<n-2\)的情况，都是同奇偶的下标进行交换。当\(i\in\{n-2,n-1\}\)时，是一个奇数下标和偶数下标元素的交换。因此按照传递性，所有元素都是直接可以交换的，因此这种情况必定成功。
当\(n\)为奇数时，对于所有\(i<n\)的下标，都是同奇偶的下标进行交换。因此，将奇数下标和偶数下标的数处理出来后，各自排序后再按照对应位置还原到原来的数组中，再判断这个数组是否有序即可。

代码

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 1:
        return 1
    b0, b1 = [], []
    for i, x in enumerate(a):
        if i % 2 == 0:
            b0.append(x)
        else:
            b1.append(x)
    b0.sort()
    b1.sort()
    for i, x in enumerate(b0):
        a[i << 1] = x
    for i, x in enumerate(b1):
        a[i << 1 | 1] = x
    return a == sorted(a)


T = int(input())
for _ in range(T):
    print("YES" if solve() else "NO")

2、小红的相似字符串

小红认为两个字符串相似，需要这两个字符串的每个字母的个数都相等。

如"abcbd"和"dbcba"相似，"abcd"和"abcd"相似。

而"abb"和"aab"不相似，"ac"和"cca"不相似。

现在小红有\(n\)个字符串，她想知道有多少对字符串是相似的？

输入

输入一个整数\(n\)。

接下来\(n\)行，每行输入一个仅包含小写字母的字符串\(s\)。

\(1 \le n \le 10^5\)
\(1 \le \text{len}(s) \le 10^5\)

输出

输出一个整数。

样例

输入：
7
abcbd
dbcba
abcd
abcd
adbc
aa
aa

输出：
5

解答

如果两个字符串的字符个数都相同，那么对各自字符串的所有字符排好序后，它们的长度必定是相等的。

因此，我们只需要将每个字符串按字符排好序后，看看排好序的字符串有多少对相等即可。

代码

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

unordered_map<string,int>mp;
int main(){
    int n;
    string s;
    ll ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        sort(s.begin(),s.end());
        ans+=mp[s];
        ++mp[s];
    }
    cout<<ans<<"\n";
}

3、子序列平均数之和

给定由\(n\)个元素组成的数组，求所有子序列的平均数之和。答案请对\(10^9+7\)取模。

子序列：原数组中选择部分元素，保持原数组的顺序形成的新数组。例如\([1,2,3,4,5]\)的子序列有\([1,2,5],[2,4]\)等，但\([2,2],[1,3,2]\)则不是它的子序列。

输入

第一行输入一个正整数\(n\)，代表数组的元素个数。

第二行输入\(n\)个正整数\(a_i\)，用来表示数组。

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

输出

所有子序列的平均数之和对\(10^9 + 7\)取模的值。可以证明，最终的答案一定是一个有理数，\(\dfrac{a}{b}\)对\(p\)取模的意义是在\([0,p-1]\)区间找到一个满足\(x\cdot b\bmod p=a\)。

样例

输入：
3
1 2 3

输出：
14

提示：
子序列共有7个：
[1]的平均数是1。
[2]的平均数是2。
[3]的平均数是3。
[1,2]的平均数是3/2。
[1,3]的平均数是2。
[2,3]的平均数是5/2。
[1,2,3]的平均数是2。
总和为14。

输入：
2
2 1

输出：
500000008

解答

由于这里考虑的是某个子序列的相同地位的元素之和，因此数组的每个贡献值都必定相等，这里只考虑其中一个元素的贡献。

对于任意一个元素\(a_k\)，它能够出现在长度为\(i\)的子序列一共有\(\dbinom{n-1}{i-1}\)个，因为元素\(i\)已经被固定选定了，在这些子序列中，它所作出的贡献是\(\dfrac{a_k}{i}\)。也就是说，\(a_k\)一共对答案做出了\(\displaystyle{a_k\cdot \sum_{i=1}^n \dfrac{1}{i}\dbinom{n-1}{i-1}}\)的贡献。可以发现，贡献的系数和数组元素本身无关。更进一步的，我们可以化简一下这个系数\(\displaystyle{\sum_{i=1}^n \dfrac{1}{i}\dbinom{n-1}{i-1}}\)，有：

\(\begin{aligned} &\sum_{i=1}^n \dfrac{1}{i}\dbinom{n-1}{i-1}\\ =&\sum_{i=1}^n \dfrac{(n-1)!}{i\cdot (i-1)!\cdot (n-i)!}\\ =&\sum_{i=1}^n\dfrac{1}{n}\cdot\dfrac{n!}{i!\cdot (n-i)!}\\ =&\dfrac{2^n-1}{n} \end{aligned}\)

因此这道题的最终答案为\(\displaystyle{\dfrac{2^n-1}{n}\cdot\sum_{i=1}^n a_i}\)。

代码

mod = 10 ** 9 + 7
n = int(input())
s1 = sum(list(map(int, input().split())))
s2 = (pow(2, n, mod) - 1) * pow(n, mod - 2, mod) % mod
ans = s1 * s2 % mod
print(ans)

4、小红的路径覆盖

小红拿到了一棵树，她有\(q\)次询问，每次会选出一个点集，小红希望你使用尽可能少的简单路径覆盖点集中的所有节点。你能帮帮她吗？

输入

第一行输入两个正整数\(n\)和\(q\)，代表树的节点数量、小红的询问次数。

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

接下来的\(2\times q\)行，每两行代表一次询问。每次询问的第一行为一个正整数\(m\)，代表点集的大小，第二行为\(m\)个正整数\(a_i\)，代表点集中的节点编号。

\(1 \le n,q\le 2\times 10^5\)
\(1 \le u,v,a_i\le n\)
所有\(m\)的总和不超过\(2\times 10^5\)

输出

输出\(q\)行，每行输出一个正整数，代表每次询问覆盖点集中所有点的最少路径数量。

样例

输入：
4 2
1 2
1 3
1 4
3
1 2 3
3
2 3 4

输出：
1
2

提示：
第一次询问可以直接选择路径：2-1-3。
第二次询问至少需要选择两条路径，例如选择路径2-1-3和路径1-4，或者选择路径2-1-4和路径3-1-4。

输入：
5 1
1 2
2 3
3 4
3 5
4
1 3 4 5

输出：
2

提示：
我们第一条路径选择1-2-3，第二条路经选择4-3-5，这两条路经即可覆盖1、3、4、5这四个点。

以下是这两棵树对应的图：

graph TD
    subgraph T1
        A((1));B((2));C((3));D((4));
        A---B;A---C;A---D;
    end
    subgraph T2
        1((1));2((2));3((3));4((4));5((5));
        1---2;2---3;3---4;3---5;
    end

解答

前置知识：dfs序是对一棵树进行深度优先搜索的时候所经过的节点顺序。我们记录每个节点\(u\)开始访问的时间戳\(l_u\)和结束访问的时间戳\(r_u\)，那么区间\([l_u,r_u]\)就包含了当前以\(u\)为根的子树的一些信息。并且，\(l_u\)是节点\(u\)的信息。假设遍历\(u\)的所有子节点\(v_1,v_2,\dots\)，那么构造出来的区间\([l_{v_1},r_{v_1}],[l_{v_2},r_{v_2}],\dots\)它们都是首尾相接的。并且，最后一个子节点的右端点的下标恰好为\(r_u\)。

对于一条备选的路径，它将会穿过一些节点，这些节点有可能在\(S\)中，也有可能不在\(S\)中。此外，这些路径如果起点或者终点不在\(S\)内，并不会使得覆盖更加完善。因此，不失一般性，备选的路径的起点和终点都位于\(S\)中。

根据上面的思想，我们可以对这棵树\(T\)进行如下操作：不停地删去不在\(S\)中的叶子节点和其关联的边，直到所有叶子节点都是\(S\)中的节点。这时，我们数一下剩下的树\(T'\)中的叶子节点个数\(c\)，可以发现用\(\lceil c/2\rceil\)条这样的路径就能够覆盖剩下的整棵树。

这意味着，\(S\)中的一个节点\(w\)如果能够被\(S\)中的另外两个不相同节点\(u,v\)的简单路径覆盖，那么\(w\)肯定不是上面所提到的树\(T'\)的叶子节点。在原树\(T\)看来，对于任意一个在\(T'\)中的叶子节点\(l',S-\{l'\}\)必定都在\(l'\)的其中一棵子树当中。

那么也就是说，对于任意\(u\in S\)，我们只需要判断\(S-\{u\}\)是否在\(u\)的某一棵子树即可。统计这些节点的个数\(c\)，那么最终答案就是\(\lceil c/2\rceil\)。

这个问题可以使用dfs序和树状数组进行解决。对于每次询问的\(S\)，我们将每个节点的dfs序号在树状数组中标记上。然后枚举每个\(u\in S\)，并且枚举\(u\)的所有子节点\(v\)，如果存在\(v\)使得\(l_v\)到\(r_v\)之间的元素和为\(|S|-1\)，那么\(u\)是符合要求的。如果没有找到，我们还需要判断一种情况，即\(S-\{u\}\)是否在\(u\)所指向的父亲的那棵子树中。

但是这样子判断，如果给定\(u\)，它的子节点非常多（达到了\(n-1\)个），那么每次只询问\(u\)也是非常消耗时间的。注意到，我们是需要找到一个子节点对应的区间\([l_v,r_v]\)其区间元素之和为\(|S|-1\)，这意味着，其它子节点\(v'\)对应的区间的元素之和都为\(0\)。由于上面提到，这些子节点区间都是相邻挨着的，因此我们可以考虑使用二分，找到第一个子节点\(v\)满足\([l_u-1,r_{v}]\)的区间元素之和不为\(0\)，然后再判断这个区间的元素和是否为\(|S|-1\)即可。

因此，这题可以在\(O(n\log^2n)\)的时间内完成。

代码

#include <bits/stdc++.h>
# define lb(x) ((x) & -(x))
using namespace std;
typedef long long ll;

const int N=100004;
int s[N],n;
void add(int p,int x){
    for(int i=p;i<=n;i+=lb(i))
        s[i]+=x;
}
int que(int p){
    int ans=0;
    for(int i=p;i;i-=lb(i))
        ans+=s[i];
    return ans;
}
vector<int>g[N],h[N];
int lp[N],rp[N],tot=0;
void dfs(int u,int fa){
    lp[u]=++tot;
    for(int v:h[u]){
        if(v==fa) continue;
        g[u].push_back(v);
        dfs(v,u);
    }
    rp[u]=tot;
}
int check(int u,int sz){
    if(g[u].empty()) return 1;
    int lsum=que(lp[u]);
    if(que(rp[u])-lsum-1==sz-1) return 1;
    int l=0,r=g[u].size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        int rsum=que(rp[g[u][mid]]);
        if(rsum!=lsum) r=mid;
        else l=mid+1;
    }
    int rsum=que(rp[g[u][l]]);
    return rsum-lsum==sz-1;
}
int cal(vector<int>&q){
    for(int u:q){
        add(lp[u],1);
    }
    int cnt=0;
    for(int u:q){
        if(check(u,q.size())){
            ++cnt;
        }
    }
    for(int u:q){
        add(lp[u],-1);
    }
    return (cnt+1)/2;
}
int main(){
    int q,m,x,y;
    scanf("%d %d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        h[x].push_back(y);
        h[y].push_back(x);
    }
    dfs(1,0);
    vector<int>qu;
    while(q--){
        scanf("%d",&m);
        qu.resize(m);
        for(int j=0;j<m;j++)
            scanf("%d",&qu[j]);
        printf("%d\n",cal(qu));
    }
}