阿里云智能 秋招 2023.09.17 编程题目与题解（研发岗）

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

1、小红的字符串

小红有一个字符串，仅包含a和b，她可以进行以下两种秀作：

  1. 找到下标\(i\)，满足\(a_i='b',a_{i+1}='a'\)，并交换这两个字符。
  2. 找到下标\(i\)，满足\(a_i='a',a_{i+1}='b'\)，并删除这两个字符。

小红可以无限次进行操作2，但只能进行\(k\)次操作1。请间小红最后可以得到的长度最小的字符串是什么，并输出这个字符串，若可以全部删除，输出\(-1\)。

输入

第一行两个整数\(n,k\)，表示字符串长度和操作1的次数。

第二行一个字符串\(a\)，表示小红的字符串。

  • \(1\le n\le 10^5\)
  • \(0\le k\le 10^5\)

输出

输出一个字符串，表示小红最后可以得到的长度最小的字符串。

若可以全部删除，输出\(-1\)。

样例

1
2
3
4
5
6
输入：
7 1
ababbaa

输出：
a

解答

由于删除ab子串次数不限，并且不会影响其它字符的相对顺序，因此我们可以贪心地删除所有子串ab，具体的删除操作可以通过栈来模拟完成。整个操作完成后，我们得到的字符串\(t\)必然是如下形态：一串连续的b再拼接上一串连续的a。

对于\(k\)次操作1，我们交换这两段边界的两个字符ba，从而得到一个子串ab，接下来就可以使用一次操作2消去一个ab子串。假设\(t\)有\(b\)个b和\(a\)个a，那么令\(k'=\min\{a,b,k\}\)，最终还可以从\(t\)删去\(k'\)个a和\(k'\)个b。

因此最终输出的字符串是\(b-k'\)个b拼接上\(a-k'\)个a。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
    int n,k;
    string s;
    cin>>n>>k>>s;
    string t;
    for(char ch:s){
        if(ch=='a') t+=ch;
        else{
            if(!t.empty()&&t.back()=='a') t.pop_back();
            else t.push_back(ch);
        }
    }
    int ca=0,cb=0;
    for(char ch:t)
        ch=='a'?++ca:++cb;
    k=min(min(k,ca),cb);
    ca-=k;cb-=k;
    string u=string(cb,'b')+string(ca,'a');
    if(u.empty()) u="-1";
    cout<<u<<endl;
}

2、小红的好数

如果一个不含前导零的正整数中，所有数位中最多有两种数字，那么这是一个好数。例如，\(23,2323,9,111,101\)都是好数。小红想知道，在\(1\)到\(n\)中，有多少个好数。

输入

一行一个正整数\(n\)。

  • \(1 \le n \le 10^9\)

输出

一行一个正整数表示答案。

样例

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

输出：
102

提示：
所有的一位数，两位数，以及三位数的100, 101, 100满足答案，一共有99+3=102个好数。

解答

这题明显是一道枚举题，直接枚举每个数进行判断是会超时的。

由于每一个好数最多由两位不同的数位不同，因此我们可以使用位运算进行完成。我们枚举两个不同的数位\(d_0,d_1(d_1\le d_0)\)，并将每个\(l\)比特数映射成一个好数：如果这个\(l\)比特数中，如果第\(i\)比特是\(b_i\)，那么将第\(i\)比特替换成\(d_{b_i}\)，这时我们得到了一个\(l\)位的好数。

因此，直接将枚举出来的好数插入集合中即可。由于这里的数据范围是\(10^k\)，其中\(k=9\)。那么加上\(10^k\)本身，我们只需要枚举其它不超过\(k\)位的整数即可。最终枚举量为\((2^1+2^2+\dots+2^{k})\cdot\dfrac{(10+1)\times11}{2}<2^{k+1}\cdot 55\)，因此实际枚举量非常小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int d[2];
    scanf("%d",&n);
    unordered_set<int>st{int(1e9)};
    for(int l=1;l<=9;l++){
        for(d[0]=0;d[0]<10;d[0]++){
            for(d[1]=0;d[1]<=d[0];d[1]++){
                for(int s=0;s<(1<<l);s++){
                    int k=0;
                    for(int i=0;i<l;i++){
                        k=k*10+d[s>>i&1];
                    }
                    st.insert(k);
                }
            }
        }
    }
    st.erase(0);
    int ans=0;
    for(int x:st){
        if(x<=n) ++ans;
    }
    printf("%d\n",ans);
}

3、小红的\(6\)

小红有一棵树，树上每个结点都有一个权值，小红很喜欢\(6\)这个数字，她想知道有多少条路径的乘积权值等于\(6\)。

输入

第一行输入一个整数\(n(1\le n \le 10^5)\) 表示树的大小。

第二行输入\(n\)个整数表示每个结点的权值\(a(1\le a_i\le 6)\)。

接下来\(n-1\)行，每行输入两个整数\(u,v(1\le u,v\le n)\)表示树上的边。

输出

输出一个整数表示答案。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入：
4
2 2 3 3
1 2
2 3
2 4

输出：
2

提示：
路径2-3和2-4的权值乘积等于6。

解答

这题明显是一道树形动态规划的题目。我们首先将整棵树定根，其跟节点为\(1\)，我们可以定义状态\(f(i,j)(1\le i\le n,1\le j\le 6)\)表示如下状态：以\(i\)为根的子树中，从根节点向下有多少条路径的权值是\(6\)？令\(\text{son(u)}\)表示节点\(u\)的所有子节点，那么\(\forall v\in\text{son}(u),\forall j\in[0,6)\)，状态可以如下自底向上地转移：

\(f(v,j)\rightarrow f(u,j\cdot a_u)\quad\text{if}\quad j\cdot a_u\le 6\)

这个转移表示以\(v\)为根的子树的所有路径都添加上其父节点\(v\)，并且权值乘上\(a_u\)，那么就变成了父节点的路径。需要注意的是，当路径权值超过\(6\)时，这些状态都将抛弃，因为它们肯定不会对答案做出任何贡献。

此外，还有如下转移，这个转移表示根节点自身也成一条路径：

\(1\rightarrow f(u,a_u)\)

接下来我们统计权值为\(6\)路径数量。具体步骤如下：当我们计算\(u\)的一个儿子\(v\)的所有\(f(v,\cdot)\)的值后，先不要立刻将它转移到\(f(u,\cdot)\)中，因为现在\(f(u,\cdot)\)只包含了已经被遍历过的所有子节点的状态之和。此时我们可以直接统计\(\displaystyle{\sum_{d\in\{1,2,3,6\}}f(u,d)\cdot f(v,6/d)}\)到答案中，因为状态\(f(u,\cdot)\)目前仍然和\(f(v,\cdot)\)仍然是没有交集的，只要将当前\(f(u,d)\)和\(f(v,6/d)\)中的所有路径拼接起来就可以得到答案。统计完答案后，再将\(f(v,\cdot)\)转移到\(f(u,\cdot)\)即可。这时我们能够不重不漏地统计出所有结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=100004;
ll f[N][7],ans=0;
int a[N],n;
vector<int>d6{1,2,3,6};
vector<int>g[N];
void dfs(int u,int fa){
    f[u][a[u]]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int x:d6){
            ans+=f[u][x]*f[v][6/x];
        }
        for(int x:d6){
            if(x*a[u]<=6){
                f[u][x*a[u]]+=f[v][x];
            }
        }
    }
}
int main(){
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    printf("%lld\n",ans);
}