蚂蚁笔试 2023-04-04场

蚂蚁笔试 2023-04-04场

第一题

有$n$个人，分别是正直者H和欺诈者L，正直者只说真话而欺诈者只说假话。现在向其中一人$x$询问另一人$y$的身份，若是正直者则输出honester，否则输出liar，共计$q$次询问。

• $1 \le n,q \le 10^4$
• $1 \le x,y \le n$
• $x \ne y$

样例输入：

5
HLHHL
3
1 2
2 3
3 4

输出：

liar
liar
honester

思路

开一个布尔数组存每个人的身份，然后将$x$和$y$，取异或输出：

if id[x] == id[y] {
    fmt.Println("honester")
} else {
    fmt.Println("liar")
}

• 时间复杂度：$O(\max(n,q))$
• 空间复杂度：$O(n)$

代码

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scan(&n)

	var str string
	fmt.Scan(&str)

	id := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		if str[i-1] == 'H' {
			id[i] = true
		}
	}

	fmt.Scan(&q)

	var x, y int

	for i := 0; i < q; i++ {
		fmt.Scan(&x, &y)
		if id[x] == id[y] {
			fmt.Println("honester")
		} else {
			fmt.Println("liar")
		}
	}
}

第二题

节点个数为$n$树的节点被选择性地染了色$R$（$W$表示节点$i$未染色），求有多少棵子树（包括整棵树）的所有节点都是染了色的。

• 树的根节点为$1$
• $1 \le n \le 10^5$
• $1 \le x,y \le n$

样例输入：

3
WRR
1 2
1 3

样例输出：

2

思路

很简单的递归回溯，返回子树是否是全染色的。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码

package main

import "fmt"

func main() {
	var n int
	var color string
	fmt.Scan(&n)
	fmt.Scan(&color)

	list := make([][]int, n+1)

	var x, y int
	for i := 1; i < n; i++ {
		fmt.Scan(&x, &y)
		list[x] = append(list[x], y)
		list[y] = append(list[y], x)
	}

	ans := 0
	var dfs func(fa, cur int) bool
	dfs = func(fa, cur int) (res bool) {
		if color[cur-1] == 'R' {
			res = true
		}
		for _, next := range list[cur] {
			if next != fa {
				res = dfs(cur, next) && res
			}
		}
		if res {
			ans++
		}
		return
	}

	dfs(0, 1)
	fmt.Println(ans)
}

写的时候有个小坑：

res = dfs(cur, next) && res

这一行写的时候长这样：

res = res && dfs(cur, next)

发现什么问题了吗？dfs(cur, nexrt)是可能会不执行的，这样就不能正常统计了。

第三题

定义k-好数：当且仅当这个数可以表示成若干个不同的k的幂之和。

例如：$17$是4-好数，因为$17=1 \times 4^2 + 0 \times 4^1 + 1 \times 4^0$；而$8$不是，因为$8=2 \times 4^1 + 0 \times 4^0$。

每次查询想知道区间$[l,r]$中有多少个k-好数，共有$q$次询问，每次询问提供$l,r,k$三个参数。

• $1 \le q \le 10^3$
• $1 \le l,r \le 10^{12}$
• $2 \le k \le 10^9$

样例输入：

1
15 21 4

样例输出：

4

思路

以$k=4$，我们首先来看两段区间$[8,15]$和$[15,21]$：

\[\begin{eqnarray} 8 &=& 2 \times 4^1 + 0 \times 4^0 &= 20_{4} \\ 15 &=& 3 \times 4^1 + 3 \times 4^0 &= 33_{4}\\ 21 &=&1 \times 4^2 + 1 \times 4^1 + 1 \times 4^0 &= 111_{4}\\ \end{eqnarray}\]

那么，我们要找到区间$[15,21]$中间的4-好数，一个一个一个去找肯定是不行的，那我们能不能有什么巧妙地方法呢？我们知道了好数的定义，那么从定义出发考虑。由于好数恰好是幂之和，那么，我们观察一下四进制：

1. 好数的每一位只能出现$0$或者$1$，不是好数则会出现比$1$大的数位。
2. 如果只能出现$0$或者$1$，和二进制表示很像，那我们也可以将好数表示成“二进制”。
3. 要找到区间内的好数，我们需要确定第一个不小于$l$的好数，和最后一个不大于$r$的好数。
4. 我们可以利用二进制进行统计。

思路提点到这里，想必大家都想通了，我要找到第一个四进制上只出现$0$或$1$，同时恰好在区间靠左侧的好数。则么求这个数呢？我们观察$15=33_4$这个数：

还不明白？再来一个$8=20_4$：

• 时间复杂度：$O(q \cdot \max(\log_k r))$
• 空间复杂度：$O(max(\log_k r))$

代码

package main

import "fmt"

var tmp = make([]int64, 64)

func main() {
	var q int
	var l, r, k int64

	fmt.Scan(&q)

	for i := 0; i < q; i++ {
		fmt.Scan(&l, &r, &k)
		ll, rr := ge(l, k), le(r, k)
		if ll > rr {
			fmt.Println(0)
		} else {
			fmt.Println(rr - ll + 1)
		}
	}
}

func ge(l int64, k int64) (res int64) {
	tmp = tmp[:0]
	defer func() { tmp = tmp[:0] }()
	for l > 0 {
		tmp = append(tmp, l%k)
		l /= k
	}

	i := len(tmp) - 1
	for ; i >= 0; i-- {
		if tmp[i] > 1 {
			res = 1 + res<<1
			res++
			break
		} else {
			res = tmp[i] + res<<1
		}
	}

	if i != -1 {
		res <<= i
	}
	return res
}

func le(l int64, k int64) (res int64) {
	tmp = tmp[:0]
	defer func() { tmp = tmp[:0] }()
	for l > 0 {
		tmp = append(tmp, l%k)
		l /= k
	}

	i := len(tmp) - 1
	for ; i >= 0; i-- {
		if tmp[i] > 1 {
			res = 1 + res<<1
			break
		} else {
			res = tmp[i] + res<<1
		}
	}

	for j := 0; j < i; j++ {
		res = 1 + res<<1
	}
	return res
}