0. 赛后总结
感觉上一次真正的参加比赛好像已经隔了好久，这次总算是重新参加了比赛，不过名次就是很一般般啦，毕竟第四题遇到超时没能做出来，国内没能进入前5%，不过世界范围内倒是进入了前5%，唉，希望后续可以再接再厉吧……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的思路还是挺直接的，只要先找到与给定点存在至少一个坐标相同的点，然后对其按照曼哈顿距离进行排序，然后取第一个元素即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
plist = [(xx, yy, idx) for idx, (xx, yy) in enumerate(points) if x == xx or y == yy]
if plist == []:
return -1
plist = sorted(plist, key=lambda p: (abs(x-p[0])+abs(y-p[1]), p[2]))
return plist[0][2]
提交代码评测得到：耗时832ms，占用内存19.4MB。
当前最优的算法实现耗时736ms，其算法思路和我们并无本质区别，就对其进行过多展开了。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题由于同一阶的幂只能使用一次，因此，我们可以直接使用贪婪算法进行原数的分解，即如果 3 k < = n < 3 k + 1 3^k <= n < 3^{k+1} 3k<=n<3k+1，那么一定会拆解为 n = 3 k + m n = 3^k + m n=3k+m，然后进一步对m进行拆分，且显然有 m < 3 k m < 3^k m<3k。
基于此，我们就可以快速地给出该题的算法实现。
2. 代码实现
给出python代码实现如下：
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
if n <= 1:
return True
k = int(log(n, 3))
m = 3**k
if n - m < m:
return self.checkPowersOfThree(n-m)
else:
return False
提交代码评测得到：耗时28ms，占用内存14MB，为当前最优算法实现。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题坦率地说虽然比赛的时候我是做出来了，但是解法无论如何也谈不上优雅，因为是一个二层循环的暴力检索，唯一的优化点在于对字符频数统计的优化，算是将三层循环减到了二层，但是本质上来说还是感觉非常的繁琐，这里就不多展开了，估计大家看了代码也就一目了然了，后续还是想看一下别人有没有更好的思路。
2. 代码实现
给出python代码实现如下：
class Solution:
def beautySum(self, s: str) -> int:
n = len(s)
cnt = [[0 for _ in range(26)] for _ in range(n+1)]
for i in range(n):
for j in range(26):
cnt[i+1][j] = cnt[i][j]
cnt[i+1][ord(s[i])-ord('a')] += 1
res = 0
for i in range(n-1):
for j in range(i+2, n+1):
c = [x-y for x, y in zip(cnt[j], cnt[i]) if x - y != 0]
_max = max(c)
_min = min(c)
if _max != _min:
res += _max - _min
return res
提交代码评测得到：耗时7260ms，占用内存14.6MB。
看了一下目前的解法，基本都是和我一样使用二层循环的，后续有兴趣的读者可以自行考察一下是否有更为优雅的解法，这里暂时就不多做展开了。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题比赛的时候遇到了超时问题，死活搞不定，赛后想了好久也没有想出结果，原因在于一直局限于在考虑点对之间距离关系，想着是把所有点对的距离求出来之后然后用二分搜索来降低每一个query的计算复杂度，殊不知光是求一个点对的距离关系事实上就直接导致了超时。
赛后看了一下别人的解法，发现他们的思路非常巧妙，因为暴力计算点对肯定会超时，那么就针对每一个query直接计算所有的点对组合数目使得两者之后大于query，然后再遍历一下边来去除掉一些由于边的问题导致实际结果不满足query的答案。
2. 代码实现
给出python代码如下：
class Solution:
def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
pcnt = [0 for _ in range(n+1)]
ecnt = defaultdict(int)
for u, v in edges:
pcnt[u] += 1
pcnt[v] += 1
u, v = (u, v) if u < v else (v, u)
ecnt[(u, v)] += 1
plist = sorted(pcnt[1:])
def fn(q):
res = 0
for i, d in enumerate(plist):
idx = bisect.bisect_right(plist, q-d)
if idx <= i:
res += n-idx-1
else:
res += n-idx
res = res // 2
for u, v in ecnt:
if pcnt[u] + pcnt[v] > q and pcnt[u] + pcnt[v] - ecnt[(u, v)] <= q:
res -= 1
return res
return [fn(q) for q in queries]
提交代码评测得到：耗时3416ms，占用内存61.4MB。属于当前的最优算法解答。