总结

• 又是笨比的一周，只做出1题。
• T1 模拟
• T2 计数模拟
• T3 坐标模拟/GPT无敌
• 

5029. 极值数量

链接: 5029. 极值数量

1. 题目描述

2. 思路分析

• 直接模拟。

3. 代码实现

def solve():n, = RI()a = RILST()ans = 0for i in range(1, n - 1):if a[i] > a[i - 1] and a[i] > a[i + 1] or a[i] < a[i - 1] and a[i] < a[i + 1]:ans += 1print(ans)

5030. 核心元素

链接: 5030. 核心元素

1. 题目描述

2. 思路分析

由于相同计数时要求最小，因此额外加个判断即可。

• 看到区间数，立刻看数据量，发现是n方，直接模拟。
• 计算每个区间的核心数是谁，贡献+1即可。
• 模拟时，固定左端点，递增右端点，可以把状态递推。

3. 代码实现

def solve():n, = RI()a = RILST()ans = [0] * (n + 1)for i in range(n):cnt = [0] * (n + 1)core = 0for j in range(i, n):v = a[j]cnt[v] += 1if cnt[v] > cnt[core]:core = velif cnt[v] == cnt[core] and v < core:core = vans[core] += 1print(*ans[1:])

5031. 矩阵扩张

链接: 5031. 矩阵扩张

1. 题目描述

2. 思路分析

傻了，想到了floyd，但没做出来。赛后写了2个代码。都应该掌握。

• 显然这题是个倒序做的题，把x从后一直加到集合里计算即可。

---

• 方法1，直观且短。把x作为k(去松弛别人的节点)，去遍历松弛。
• 由于在floyd里，k是最外层的节点，因此这么做完后，k的影响已经结束了，则可以更新当前答案。
• 实现时，松弛的话是u,v都是全部节点；计算答案只计算已添加的节点。

---

• 方法2，助于理解floyd。
• 依然倒序把x作为k，但是分别计算三种最短路:k到所有已访问的u、所有u到k、所有已访问的u到v。
• 这里注意计算顺序，由于u->v是已经计算完的最短路，所以必须用它们先去更新k相关的最短路，再返回来计算新的u->v。

3. 代码实现

def solve():n, k = RI()t = []for _ in range(n):s, = RS()t.append(s)ans = ['.']for _ in range(k):d0 = len(ans)d = d0 * nnq = [[] for _ in range(d)]for i, row in enumerate(ans):for j, c in enumerate(row):a = i * nif c == '.':for p in range(n):# print(a,p,d0,d)nq[a + p].extend(t[p])else:for p in range(n):nq[a + p].extend(['*'] * len(t))ans = nqfor row in ans:print(''.join(row))

六、参考链接

• 无