阿里笔试 20210326

第一题

给定一个长度为 $n$ 的数组，元素为 $0$ 或 $1$。拥有一次从其中删去一个元素的机会，求删去后连续 $1$ 的最大长度

简单动态规划题

• $dp[i][0]$ 表示前 $i$ 个元素中，以 $i$ 结尾的序列，不使用删除机会能达到的最大值
• $dp[i][1]$ 表示前 $i$ 个元素，以 $i$ 结尾的序列，使用删除机会能达到的最大值

考虑如下转移:

• 当前数是 $1$: $dp[i][1] = dp[i-1][0] + 1$，$dp[i][0] = dp[i-1][0] + 1$
• 当前数是 $0$: $dp[i][1] = dp[i-1][0]$，$dp[i][0] = 0$

def solve():
    n, = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    dp = [[0, 0] for i in range(n)]
    dp[0][0] = arr[0]
    dp[0][1] = 0
    res = max(dp[0][0], dp[0][1])
    for i in range(1, n):
        dp[i][1] = dp[i-1][0] if arr[i] == 0 else dp[i-1][1] + 1
        dp[i][0] = 0 if arr[i] == 0 else dp[i-1][0] + 1
        res = max(res, dp[i][0], dp[i][1])
    return min(n-1, res)

t, = list(map(int, input().split()))
for i in range(t):
    print(solve())

给一些本地的测试用例（输出自己数一下就行吧）

6
3
1 1 1
6
1 1 0 1 0 1
5
1 1 1 1 1
5
0 0 0 0 0
10
1 0 0 1 1 1 0 0 1 1
15
1 1 0 1 1 0 0 1 1 1 0 1 1 1 1

第二题

有 $n$ 个酒店，酒店间有 $n-1$ 条路，确保酒店之间必存在唯一路径，路径存在长度。

三个人需要选择酒店住宿，每个人都拥有一个倾向酒店，每个人住的酒店将从倾向中选择一个（概率相等）。需要选择一个集合酒店（可以是三个人某个人在的酒店，也可以是不在的酒店），作为三个人的集合点。集合点必定是三个人距离之和最短的酒店，求最短路径之和的期望。

2020 CCPC 威海 C.Codeforces

由于共有 $n$ 个联通的酒店，有 $n-1$ 的通路，故所有的酒店构成一棵树

树上任三点的集合点，距离值为两两距离和的一半。
如对下面的情况，3、6、7 为被选择的三个点，那么三个点都需要向公共祖先的方向进行移动，分别移动到 1 和 2，而后集合点应该定为 2。因为 1 2 路径必须被经过，所以选择经过一次。

      1
   /  |  \
  2    3    4
/ | \ / \  / \
5 6 7 8 9 10 11

由于题目求的是 期望值，在所有居住酒店被选择概率相等的情况下，期望值应该是
$\begin{cases} E(x) &= \sum p_i \times v_i \\ &= (\sum_{i=0}^{l_a}\sum_{j=0}^{l_b}\sum_{k=0}^{l_c}d_{a[i],b[j]} + d_{b[j],c[k]} + d_{a[i],c[k]}) \div (2 \times l_a \times l_b \times l_c) \\ &= (l_c\sum_{i=0}^{l_a}\sum_{j=0}^{l_b} d_{a[i],b[j]} + l_b\sum_{i=0}^{l_a}\sum_{k=0}^{l_c} d_{a[i],c[k]} + l_a\sum_{j=0}^{l_b}\sum_{k=0}^{l_c} d_{b[j],c[k]}) \div (2 \times l_a \times l_b \times l_c) \\ &= \frac{\sum_{i=0}^{l_a}\sum_{j=0}^{l_b} d_{a[i],b[j]}}{2 \times l_a \times l_b} + \frac{\sum_{j=0}^{l_b}\sum_{k=0}^{l_c} d_{b[j],c[k]}}{2 \times l_b \times l_c} + \frac{\sum_{i=0}^{l_a}\sum_{k=0}^{l_c} d_{a[i],c[k]}}{2 \times l_a \times l_c} \end{cases}$不考虑常数部分，实际上需要求的是 $\sum^{l_a}_{i=0}\sum^{l_b}_{j=0}d_{a[i],b[j]}$

题目转变为 求树上给定起点序列和终点序列所有组合的距离之和
如果保留求解，这部分的时间复杂度是 $O(n^2)$，需要进一步优化。由于任意两点路径唯一，因此可以考虑每条路径的贡献值。对于路径 $edge[u][v]$，只需要计算其左侧和右侧序列值的个数即可。
如上面的树中，如果有序列 a=[6,3,10] 和 b=[5, 7, 1, 10]，那么对于路径 1-2，可以根据 1-2 左侧有 1 个序列 a 的元素，2 个序列 b 的元素，直接计算出该路径共被计算 $1*(4-2)+(3-1)*2=6$ 次，再乘上其对应的长度，即可得到该边的贡献。这样，就可以在 $O(n)$ 的时间复杂度内计算出距离和。
该部分需要预计算每个边左侧对应序列元素的个数，也可以认为是预处理为每个节点子节点对应序列元素的个数。该预处理需要对树进行 DFS 遍历，时间复杂度也是 $O(n)$

整体思路变为:

1. 得到每个节点子节点中对应序列元素的个数
2. 计算每个边的贡献值
3. 从两个序列选择起终点所得到的距离和
4. 按照公式计算期望值

有一个需要特别注意的点是，最坏情况下树会退化成一条线，其中的递归深度将会很深（Python 会爆栈）。类似地，别的语言可能不会爆栈，但是运行速度会较慢，可以考虑将 root 设定为非 1 的值，避免被刻意卡人的数据卡死。

另一个需要特别注意的点是，虽然看上去数据量并不大，但是由于计算过程涉及大量乘法，所以中间步骤都有可能超出 int32，需要将绝大部分计算都处理为 int64（比较容易忽略的是 $l_a \times l_b$ 的计算，这里在极端条件会溢出）（一般 Go 本地 int 为 int64，但在 Codeforces 上是 int32）

整道题每一小步本质上都可以单独作为一道题，感觉除非做过，不然一个小时推出来的难度非常之大。按照这个情况，阿里笔试实际上出的并不是那么有区分度。

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200005

vector<pair<int, int>> edges[MAXN];
int prefer[3][MAXN];
int childrenCount[MAXN][3];

int read_int() {
    char c;
    int ans = 0;
    while (c = getchar(), !(c >= '0' && c <= '9'));
    while (c >= '0' && c <= '9') {
        ans *= 10;
        ans += (int)c - '0';
        c = getchar();
    }
    return ans;
}

void dfs(int t, int parent) {
    for (auto pair : edges[t]) {
        int child = pair.first;
        if (child != parent) {
            dfs(child, t);
            for (int i = 0;i < 3; ++i) {
                childrenCount[t][i] += childrenCount[child][i];
            }
        }
    }
}

long long sm = 0;

void calcDFS(int t, int parent, int a, int b) {
    for (auto pair : edges[t]) {
        int child = pair.first;
        int dis = pair.second;
        if (child != parent) {
            calcDFS(child, t, a, b);
            int ca = childrenCount[child][a];
            int cb = childrenCount[child][b];
            sm += (long long)((long long)ca * (long long)(prefer[b][0] - cb) + (long long)(prefer[a][0] - ca) * (long long)cb) * (long long)dis;
        }
    }
}

double calc(int root, int a, int b) {
    sm = 0;
    calcDFS(root, 0, a, b);
    return (double)(sm) / (double)(2 * (long long)prefer[a][0] * (long long)prefer[b][0]);
}

double solve() {
    int n = read_int();
    int root = n / 2;

    for (int i = 0;i <= n; ++i) {
        edges[i].clear();
        childrenCount[i][0] = 0;
        childrenCount[i][1] = 0;
        childrenCount[i][2] = 0;
    }

    int a, b, c;
    for (int i = 1;i < n; ++i) {
        a = read_int();
        b = read_int();
        c = read_int();
        edges[a].push_back(make_pair(b, c));
        edges[b].push_back(make_pair(a, c));
    }
    for (int i = 0;i < 3;++i) {
        prefer[i][0] = read_int();
        for (int j = 1; j <= prefer[i][0]; ++j) {
            prefer[i][j] = read_int();
        }
    }

    // 预处理树上，每个节点子节点序列个数
    for (int i = 0;i < 3;++i) {
        for (int j = 1; j <= prefer[i][0]; ++j) {
            int t = prefer[i][j];
            childrenCount[t][i] = 1;
        }
    }

    dfs(root, 0);

    double res = 0;
    res += calc(root, 0, 1);
    res += calc(root, 0, 2);
    res += calc(root, 1, 2);

    return res;
}

int main() {
    // for (int i = 0;i < 6;++i)
    printf("%.12f\n", solve());
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Pair struct {
	n int64
	d int64
}

var in = bufio.NewReader(os.Stdin)

func ReadInts() ([]int64, error) {
	line, err := in.ReadString('\n')
	if len(line) == 0 && err != nil {
		return []int64{}, err
	}

	ss := strings.Split(
		strings.TrimSpace(line),
		" ",
	)
	res := make([]int64, 0, len(ss))
	for _, s := range ss {
		num, _ := strconv.ParseInt(s, 10, 64)
		res = append(res, int64(num))
	}
	return res, nil
}

func solve() float64 {
	var nums []int64
	var n, a, b, c int64

	nums, _ = ReadInts()
	n = nums[0]
	root := n / 2

	edges := make([][]Pair, n+1)
	for i := int64(0); i <= n; i++ {
		edges[i] = make([]Pair, 0)
	}
	for i := int64(0); i < n-1; i++ {
		nums, _ = ReadInts()
		a, b, c = nums[0], nums[1], nums[2]
		edges[a] = append(edges[a], Pair{b, c})
		edges[b] = append(edges[b], Pair{a, c})
	}
	prefer := make([][]int64, 3)
	for i := 0; i < 3; i++ {
		nums, _ = ReadInts()
		prefer[i] = make([]int64, len(nums))
		for j := 0; j < len(nums); j++ {
			prefer[i][j] = nums[j]
		}
	}

	// 预处理树上，每个节点子节点序列个数
	childrenCount := make([][]int64, n+1)
	for i := int64(0); i <= n; i++ {
		childrenCount[i] = make([]int64, 3)
	}

	for i := int64(0); i < 3; i++ {
		for j := int64(1); j <= prefer[i][0]; j++ {
			t := prefer[i][j]
			childrenCount[t][i] = 1
		}
	}

	var dfs func(t, parent int64)

	dfs = func(t, parent int64) {
		// 预处理以 parent 作为父节点，t 节点子节点的各序列数目
		for _, pair := range edges[t] {
			child := pair.n
			if child != parent {
				dfs(child, t)
				for i := 0; i < 3; i++ {
					childrenCount[t][i] += childrenCount[child][i]
				}
			}
		}
	}
	dfs(root, 0)

	// 计算各个边的权重值，并套公式

	calc := func(a, b int64) float64 {
		c := a ^ b ^ 0 ^ 1 ^ 2
		// 计算序列 a 和 序列 b 对应的值
		// sum(dis[a[i]][b[j]]) * c / (2 * len(a) * len(b))
		sm := int64(0)

		var calcDFS func(t, parent, a, b, c int64)
		calcDFS = func(t, parent, a, b, c int64) {
			for _, pair := range edges[t] {
				child := pair.n
				dis := pair.d
				if child != parent {
					// t -> child 边权 dis
					calcDFS(child, t, a, b, c)
					// 子节点中 a 的个数
					ca := childrenCount[child][a]
					// 子节点中 b 的个数
					cb := childrenCount[child][b]
					sm += (ca*(prefer[b][0]-cb) + (prefer[a][0]-ca)*cb) * dis
				}
			}
		}
		calcDFS(root, 0, a, b, c)

		return float64(sm) / float64(2*prefer[a][0]*prefer[b][0])
	}

	res := float64(0)
	res += calc(0, 1)
	res += calc(0, 2)
	res += calc(1, 2)

	// fmt.Println(n)
	// fmt.Println(edges)
	// fmt.Println(prefer)
	return res
}

func main() {
	// for i := 0; i < 6; i++ {
	fmt.Printf("%.12f\n", solve())
	// }
}