滴滴秋招 2023.09.28 编程题目与题解

发表于 2023-09-29 分类于笔试阅读次数：本文字数： 1.7k 阅读时长 ≈ 2 分钟

1、圆木加工

一家木材厂需要加工三根圆木。这三根圆木长度分别为$a,b,c$，一共需要进行不超过$n$次加工程序。第$i$道加工程序需要选择其中一根长度严格大于$i$的圆木，将其切割，使其长度减少$i$。被切下的部分不再进入后续的加工流程。如果这三根圆木的长度能够组成一个面积大于$0$的三角形，那么就称此时的圆木长度三元组$(a',b',c')$是好的。

现在的问题是：一共可能形成多少种好的三元组？

输入

输入仅一行四个正整数$n,a,b,c$。

对于$100\%$的数据，$1\le n,a,b,c \le 100$。

输出

输出一行，一个整数，表示好的三元组的个数。

样例

输入：
5 3 4 5

输出：
10

提示：
有如下10种三元组
(1,4,4),(2,2,2),(2,4,3),(2,4,5),(3,2,4),(3,3,3),(3,3,5),(3,4,2),(3,4,4),(3,4,5)

解答

对于三种原木$(a,b,c)$是否能拼接成一个三角形，只需要判断$a+b>c,a+c>b,b+c>a$是否都成立即可。

由于第$i$次加工程序切除原木的长度只依赖于$i$本身，因此，如果从原木$(a,b,c)$经过若干道加工程序变成$(a',b',c')$后，其使用的加工轮数必定是确定的。也就是说，只要从$(a,b,c)$变成$(a',b',c')$，那么必定进行了$k$轮，并且$k$是一个常数，不依赖于现有的决策。

因此，我们使用带有记忆化的深度优先搜索即可完成本题。如果发现当前状态$(a,b,c)$被遍历过，那么就直接返回，否则进一步向下进行枚举即可。这保证了每个不同的三元组$(a,b,c)$都只被遍历一次。

代码

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

const int N=104;
int n,a,b,c;
int ans=0;
int vis[N][N][N];
void dfs(int k,int a,int b,int c){
    if(vis[a][b][c]) return;
    vis[a][b][c]=1;
    if(a+b>c&&a+c>b&&b+c>a) ++ans;
    if(k==n+1) return;
    if(a>k) dfs(k+1,a-k,b,c);
    if(b>k) dfs(k+1,a,b-k,c);
    if(c>k) dfs(k+1,a,b,c-k);
}
int main(){
    scanf("%d %d %d %d",&n,&a,&b,&c);
    dfs(1,a,b,c);
    printf("%d\n",ans);
}

2、平衡树

小明正在玩一棵树，它正在研究树的平衡性，它为了辅助研究，为树定义了一个函数$S(x)$，表示对树中节点$x$，其到树中其他所有节点的距离之和，注意树上相邻节点之间距离为$1$，而且树根为$1$号节点。现在他想让你帮他进行计算！

输入

第一行两个正整数$n,m$分别表示树上的节点数和询问数。

接下来一行$n-1个数$p_2,p_3,p_n$。表示节点$i$的父亲为$p_i$。

接下来一行$m$个数，$x_1,x_2,\dots x_m$，分别表示每次询问所使用的$x$值。

对于所有数据，$1\le n,m\le 20000,1\le p_i< n, 1 \le x_i \le n$。

输出

输出一行$m$个数，单空格隔开，分别表示每次询问的答案。

样例

输入：
3 3
1 1
1 2 3

输出：
2 3 3

解答

这道题是原题Leetcode 834。其使用的基本思想是换根动态规划，进行两次深度优先搜索即可完成，其中第二次搜索使用了动态规划的思想。

其基本思想是，首先我们先以$O(n)$的时间复杂度求出一个节点的答案值，然后再将其转移到每个节点的答案。

令$d_i$表示节点$i$的深度，$s_i$表示以节点$i$为根的子树中的节点数个数，$f_i$表示$i$到其它节点的所有距离之和。

通过第一次深度优先搜索，我们可以求出数组$d,s$。并且，我们能够利用好数组$d$给出第一个转移：

$\displaystyle{\sum_{i=1}^n d_i\rightarrow f_1}$

以上根据定义是显而易见的。令$\text{son}(u)$表示$u$的所有子节点，那么考虑$v\in \text{son}(u)$，我们可以列出如下转移：

$f_u+(n-s_v)-s_v\rightarrow f_v$

当我们已经求出了节点$u$的$f_u$值后，那么对于$u$其中的一个子节点，$f_u$值会发生什么变化呢？对于一个节点$w$，如果它在$v$的子树，那么从$u$走到$w$的距离减少了$1$，因此需要减去$s_v$；如果它不在$v$的子树，那么从$u$走到$w$的距离增加了$1$，因此可以得出如上转移。这在$O(n)$的时间内可以完成。

对于给定的每个询问$x$，直接输出$f_x$的值即可。

代码

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

const int N=20004;

int ans[N],d[N],sz[N];
vector<int>g[N];
int n,m;
void dfs1(int u,int dis){
    d[u]=dis;
    sz[u]=1;
    for(int v:g[u]){
        dfs1(v,dis+1);
        sz[u]+=sz[v];
    }
}
void dfs2(int u){
    for(int v:g[u]){
        ans[v]=ans[u]-sz[v]+(n-sz[v]);
        dfs2(v);
    }
}
int main(){
    int x;
    scanf("%d %d",&n,&m);
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        g[x].push_back(i);
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++)
        ans[1]+=d[i];
    dfs2(1);
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        printf("%d%c",ans[x]," \n"[i==m]);
    }
}