9.9 阿里淘天笔试

第一题

题意

8×8国际象棋棋盘 有一个马和一个象，问再摆放一个旗子放在哪里不会被吃

题解

模拟即可

第二题

题意

一个王国有n个城堡，n-1条边构成一棵树，树的根是1号节点。树中有m个节点损坏，需要全部修理好。每次选择一个节点修理，会修好从该节点到树根整条路径上的全部节点。问最少需要修理几次。

题解

dp[i]表示修理好子树i需要的次数。如果子树i的儿子节点有需要修理的，则在修理好每个儿子节点的时候就会自动修理节点i，dp[i]为其子树修理次数求和；如果所有儿子节点都不需要修理，则要判断i节点自身是否需要修理。

第三题

题意

平面整数坐标系上有n个节点。每个节点可以移动到横坐标或纵坐标相同的其他节点上。问需要新增加多少个节点，才能让每个节点都可以移动到任意节点上。

题解

并查集。如果可以将所有点分割成n个子集，每个子集内的点都是满足题意的。则只需要增加n-1个节点，即可使所有点互相可达。用并查集维护这些子集。如果两个节点之间可以直达，则这两个节点所属的子集可以合并。合并完所有直接可达的节点之后，统计最终并查集的个数即可。