2024.8.7 模拟赛题解

T1

过于简单，不必阐述。

T2

给定一个仅包含 \(A\) 和 \(P\) 的字符串，每次操作可以删除相邻的 \(AP\) 或者 \(PP\)，问字符串最后的最小长度。

$Sol : $ 为求最值问题，考虑贪心。先给出考场做法。

发现若干的 \(P\) 是一定能合并掉的，于是贪心策略，就是如何最小化 \(A\) 的个数。对于每个 \(A\)，只能由在后面的 \(P\) 消除掉。从后往前遍历整个序列，记录 \(cnt\)，每当遇到一个 \(P\)，\(cnt \gets cnt + 1\)，遇到 \(A\) 时，将当前的 \(A\) 与后面的 \(P\) 匹配，\(cnt \gets cnt - 1\)，若 \(cnt = 0\) 即为当前位，后面无多余的 \(P\)，那么答案个数增加。最后，判断 \(A\) 的剩余个数（刚刚记录的答案）和 \(cnt\) 的奇偶性即可。

正解。用一个栈进行维护，思维含量较少。从前往后遍历整个序列，将当前的元素，入栈。若发现，栈顶的两格元素可以消掉，那么直接合并。可以证明，一定是最优的。最终答案为栈中元素的个数。

T3

咕咕咕

T4

咕咕咕