阿里控股秋招 2023.09.23 编程题目与题解

发表于 2023-09-28 分类于笔试阅读次数：本文字数： 1.6k 阅读时长 ≈ 1 分钟

1、小红的三元组

小红有一个长度为\(n\)的数组\(a\)，她每次操作可以删掉一个三元组\((x,y,z)\)，要求\(x<y<z\)，\(y\)是\(x\)的倍数，\(z\)是\(y\)的倍数。小红想知道最多可以执行多少次操作。

输入

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

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

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

输出

输出一个整数，表示最多可以执行的操作次数。

样例

输入：
7
1 1 2 3 4 5 6

输出：
2

提示：
先删除(1,2,4)，再删除(1,3,6)。

解答

可见，满足题意的三元组只有可能是如下三种情况：\((1,2,4),(1,2,6),(1,3,6)\)。

由于\(3,4\)都在这些组合都出现了一次，因此我们优先取走\((1,2,4),(1,3,6)\)这些组合，再取走\((1,2,6)\)这种组合。

代码

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

const int N=14;
int a[N];
vector<vector<int>>v{{1,2,4},{1,3,6},{1,2,6}};
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ++a[x];
    }
    int ans=0;
    for(auto u:v){
        int t=min(a[u[0]],min(a[u[1]],a[u[2]]));
        ans+=t;
        a[u[0]]-=t;
        a[u[1]]-=t;
        a[u[2]]-=t;
    }
    printf("%d\n",ans);
}

2、小红的连续字符串

小红有一个字符串\(s\)，只包含小写字母。如果一个字符串中，不包含连续的三个相同的字母，并且不存在两个相同的字母紧挨着两个相同的字母，那么这个字符串就是合法的。例如，字符串"aaa"是不合法的，字符串"aabb"也是不合法的。字符串"aab"是合法的。

小红想知道，最少需要删除多少个字符，才能使得字符串变成合法的。

输入

第一行一个字符串\(s\)，长度不超过\(10^5\)，只包含小写字母。

输出

输出一个整数，表示最少需要删除的字符个数。

样例

输入：
aabbaa

输出：
1

提示：
删除一个字符b，得到aabaa，是一个合法的字符串。

输入：
aaabbb

输出：
3

提示：
删除三个字符，得到aab，是一个合法的字符串。

解答

由于不允许连续三个字母挨在一起，因此我们首先将连续多于两个字母的都删剩两个，然后再考虑下一步。

接下来每一块相同的字母不超过\(2\)个。我们接下来从前往后遍历每个连续块。如果当前连续块的字母个数为\(2\)，并且前一个连续块字母个数也为\(2\)，那么删除当前块的一个字母（因为删除前面的并不会使结果变得更优）。

因此，只需要统计两个过程删去的字符数即可。

代码

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

const int N=100004;
int a[N],m=0;
char s[N];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    int cnt=0,pre=s[1];
    for(int i=1;i<=n+1;i++){
        if(s[i]==pre) ++cnt;
        else{
            a[++m]=cnt;
            cnt=1;
        }
        pre=s[i];
    }
    int s=0;
    for(int i=1;i<=m;i++){
        a[i]=min(a[i],2);
        if(i>=2&&a[i]==2&&a[i-1]==2){
            --a[i];
        }
        s+=a[i];
    }
    printf("%d\n",n-s);
}

3、有根树无重复数的路径

小红拿到了一个有根树，根节点为\(1\)号节点，每个节点到其每个孩子有一条有向边。小红想取一条路径，满足路径上所有节点的权值都不相等。小红想知道，自己有多少种选择方案？

输入

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

第二行输入\(n-1\)个正整数\(a_i\)，代表\(2\)号节点到\(n\)号节点每个节点的父亲编号。

第三行输入\(n\)个正整数\(v_i\)，代表\(1\)号节点到\(n\)号节点每个节点的权值。

\(2\le n\le 2\times 10^5\)
\(1\le a_i< i\le 2\times10^5\)
\(1\le v_i\le 10^9\)

输出

小山选择路径的方案数。

样例

输入：
5
1 1 1 2
1 1 2 2 2

输出：
8

提示：
路径上有一个节点，有5种取法。
路径上有两个节点的取法有： 1-3、1-4、2-5

输入：
3
1 1
1 2 3

输出：
5

提示：
路径上有一个节点，有3种取法。
路径上有两个节点的取法有： 1-2、1-3

解答

假设我们现在处在节点\(u\)，现在一直向父亲节点移动。在移动的过程中，一旦发现一个节点\(u'\)的权值出现过，那么说明再往上的路径都是不符合要求的。也就是说，如果\(w\)是\(u'\)的子节点，又是\(u\)的祖先，那么从\(w\)到\(u\)的路径中，以\(u\)为终点的路径都是符合要求的，我们直接统计即可。

在实现过程中，我们并不能够直接寻找\(w\)，因为这将导致\(O(n^2)\)的时间复杂度。我们使用的做法是，假设现在遍历到了一个\(u\)节点，并且已经知道了其父亲节点所对应的\(w\)节点的深度为\(d\)，那么如果\(u\)的权值\(v_u\)已经在从根到\(u\)的路径上出现过，那么令其最深的深度为\(w_u\)（否则，令\(w_u=0\)，这里假设根节点的深度为\(1\)），那么令\(d'=\max\{d,w_u\}\)，假设\(u\)节点的深度为\(d_u\)，那么就可以直接把\(d_u-d'\)统计到答案中。

由此我们维护好\(w_u\)值，最终可以以\(O(n)\)的时间完成本题。

代码

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

const int N=200004;
vector<int>g[N];
int a[N],n;
map<int,vector<int>>v;
ll ans=0;
void dfs(int u,int np,int d){
    if(!v[a[u]].empty()){
        np=max(np,v[a[u]].back());
    }
    ans+=d-np;
    v[a[u]].push_back(d);
    for(int v:g[u]){
        dfs(v,np,d+1);
    }
    v[a[u]].pop_back();
}
int main(){
    scanf("%d",&n);
    int x;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        g[x].push_back(i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    dfs(1,0,1);
    printf("%lld\n",ans);
}