度小满 秋招 2023.09.08 编程题目与题解

1、寻找字符A

现在有\(n\)个人坐成一个圈，也就是说第\(n\)个人的下一个是第\(1\)个人。每个人背上贴了一个大写字母。这个字母可能是A也可能是B。你的任务是从第一个人开始，顺次向后计数，每遇到一个贴着字母A的人就计数一次。第\(k\)次计数到A后停止。现在问你总共需要数多少个人才能停止。保证至少有一个人背上贴的是A。

输入

第一行两个整数\(n,k\)，表示共有\(n\)个人，计数A的次数为\(k\)。

第二行\(n\)个大写字母，只能是A或者B，依次表示每个人背上所贴的字母。

• \(1\le n,k\le100000\)

输出

一行，一个整数表示共需要数多少人。

样例

输入：
3 3
AAB

输出：
4

提示：
显然是数一圈后再数到第1个人时停止。总共数了4个人。

输入：
3 3
BBA

输出：
9

提示：
数三圈后停在第3个人这里。

解答

可以看出，这个数A的过程是循环进行的。假设这\(n\)个人中一共有\(a\)个人带有字母A，那么至少需要循环\(\lfloor k/a\rfloor\)轮数完每一个循环，最终只需要数到第\(k\bmod a\)个带有A的人即可。

但是有例外一种情况：如果\(k\bmod a=0\)，那么在最后一轮只需要数到最后一个带有A的人即可，而不需要数完剩下的B。

代码

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

const int N=100004;
char s[N];
int n,k;
int main(){
    scanf("%d %d %s",&n,&k,s+1);
    vector<int>a;
    for(int i=1;i<=n;i++)
        if(s[i]=='A') a.push_back(i);
    int d=k/a.size(),r=k%a.size();
    if(r==0){
        --d;r=a.size();
    }
    ll ans=1ll*d*n+a[r-1];
    printf("%lld\n",ans);
}

2、树上运算

你想对一棵奇怪的二又树进行运算。这棵树每个节点要么有两个子节点，要么没有子节点。如果一个节点没有子节点，则这个节点的值为\(1\)。如果某个节点有两个子节点，这个节点的值就是它两个子节点的值做某种运算后的结果，某种运算取决于这个节点的颜色，如果为红色则是乘法，如果为蓝色则是加法。你想知道根节点的值。

树，是一种无向无环联通图。

输入

第一行一个正整数\(n\)表示节点个数。

第二行\(n-1\)个正整数\(p[2,3,\dots,n],p_i\)表示第\(i\)个节点的父节点。\(1\)号节点是根节点

第三行\(n\)个整数\(c[1,2,\dots,n]\)，当\(c[i]=1\)时表示第\(i\)个节点是蓝色，\(c[i]=2\)则表示红色。

数据保证形成合法的树。

• \(n\le 50000\)
• \(c[i]\in \{1,2\}\)

输出

输出一行一个整数表示根节点的值。考虑到值可能很大，输出它除以\(1000000007\)的余数。

样例

输入：
3
1 1
1 1 1

输出：
2

提示：
样例如图所示。因为2号节点和3号节点都没有子节点，因此值都为1。因为1号节点的颜色是蓝色，因此1号节点的值是2号节点的值和3号节点的值的相加，即1+1=2。

该样例的图如下所示：

graph TD
  1((1));2((2));3((3));
  1---2;1---3;
  classDef red-node fill:red, color:white
  class 1,2,3,5,7,9,11,13,15,4,12 red-node;

解答

这题只需要自底向上计算出所有节点值即可。假设第\(i\)个节点的值为\(v[i]\)，那么如果\(i\)没有子节点，那么\(v[i]=1\)；否则假设其两个子节点分别为\(x_i,y_i\)，如果\(c[i]=1\)，那么就有\(v[i]=v[x_i]+v[y_i]\)，如果\(c[i]=2\)，那么就有\(v[i]=v[x_i]\cdot v[y_i]\)。使用递归即可完成所有情况的模拟。

代码

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

const int N=100004;

vector<int>g[N];
int n;
ll a[N],mod=1e9+7;
int c[N];
void dfs(int u){
    if(g[u].empty()){
        a[u]=1;
    }
    else{
        int v=g[u][0],w=g[u][1];
        dfs(v);dfs(w);
        if(c[u]==1) a[u]=(a[v]+a[w])%mod;
        else a[u]=a[v]*a[w]%mod;
    }
}
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",&c[i]);
    dfs(1);
    printf("%lld\n",a[1]);

}

3、小贝的树哈希

在判断树的同构时，树哈希常常是应用得比较广泛的一类算法。树哈希有很多变种，但小贝一个都没有记住，反而自己创造了一种新的“哈希”算法：

对干一棵有根树，设\(H_u\)表示以\(u\)为根的子树的Hash值，\(\text{son}(u)\)表示\(u\)的儿子节点集合，那么有：

\[H_u=\left(\sum_{v\in \text{son}(u)}(H_v+A^u)\cdot B\right)\bmod M\]

该式子表示对于\(u\)的每个儿子\(v\)，将\(v\)的Hash值加上\(A^u\)之后得到的值乘以\(B\)，再全部加起来，对\(M\)取模之后就是\(u\)的Hash值。具体可以参见样例。特别地，当\(u\)是叶子时，\(H_u=0\)。

现在，小贝得到了一棵\(n\)个节点的以\(1\)为根的有根树，她想知道按照自己的算法得到的\(H_1\)是多少。

输入

第一行四个正整数\(n,A,B,M\)；

第二行\(n-1\)个正整数\(p_2,p_3,\dots,p_n\)，表示节点\(i\)与\(p_i\)之间有一条边。

• \(1\le n \le 10^4\)
• \(1\le A,B,M\le 10^9\)
• \(1\le p_i <i\)

输出

输出一行一个整数，表示\(H_1\)的值。

样例

输入：
7 3 2 1000000000
1 1 2 2 3 6

输出：
6024

该样例如下图所示：

graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));
  1---2;1---3;2---4;2---5;
  3---6;6---7;

\(\begin{aligned} H_4&=H_5=H_7=0\\ H_2&=(H_4+3^2)\cdot 2 + (H_5+3^2)\cdot 2=36\\ H_6&=(H_7+3^6)\cdot 2 =1458\\ H_3&=(H_6+3^3)\cdot 2 =2970\\ H_1&=(H_2+3^1)\cdot 2 + (H_3+3^1)\cdot 2=6024\\ \end{aligned}\)

解答

这道题目只需要模拟哈希函数\(H\)的计算过程即可。整个过程大概是，首先预处理出所有\(A^u\bmod M\)的值，其中\(u\in [1,n]\)；然后按照公式，自底向上地计算出\(H_u\)的值。

代码

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

const int N=100004;

vector<int>g[N];
int n;
ll pwa[N],a,b,m;
ll h[N];
void dfs(int u){
    for(int v:g[u]){
        dfs(v);
        h[u]=(h[u]+(h[v]+pwa[u])*b)%m;
    }
}
int main(){
    scanf("%d %lld %lld %lld",&n,&a,&b,&m);
    pwa[0]=1;
    for(int i=1;i<=n;i++)
        pwa[i]=pwa[i-1]*a%m;
    int x,y;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        g[x].push_back(i);
    }
    dfs(1);
    printf("%lld\n",h[1]);
}