Facebook Hacker Cup 2022 Round 2
原文约2800字，阅读约需7分钟。发表于：。https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2 Problem A. Perfectly Balanced 题意：给定一个字符串，每次询问一个子串，问是否是几乎平衡的。 几乎平衡的定义是，从子串中删除一个字符后，长度为偶数，且前半段中每个字符的出现次数与后半段相等。 A1 中字符集来自小写字符。A2 中字符集来自任意 int。 分析：再考虑弱化，如果字符集只有 {0, 1}，那么我们只要先判断下长度是否为奇数，然后枚举一下删哪个位置，然后树状数组比较一下两段 1 的个数是否一样即可。 再考虑如何不枚举删哪个位置，哪么就讨论从哪边删，然后看两边的 diff 是否是一即可。设 S(l, r) 表示 [l, r) 这个区间里 1 出现的次数，那么就是比较一下 S(ml, r) – S(l, ml) = 1 或者 S(l, mr) – S(mr, r) = 1。 因此对于 A1，我们只要开 25 棵树状数组就能通过。对于字符集任意的情况，我们把所有数字映射成一个随机 uint，然后看 diff 是否恰好是某个字符的映射即可。代码反而比 A1 更简单。 Problem B. Balance Sheet […]
问题A：判断子串是否几乎平衡。通过枚举删除位置或讨论删除哪边的字符来判断。对于字符集任意的情况，将数字映射成随机uint，判断diff是否是某个字符的映射。代码比A1更简单。问题B：dag dp，用multiset记录dp值。问题C：从n袋饼干中任取k个，问最重的一块饼干来自第一袋的概率。问题D：给定序列和修改操作，问每次修改后至少需要多少次swap操作。D1中可以贪心解决。
