ICPC World Finals 口胡

EgLund · 2022-11-11 07:48:05 · 个人记录

H: 给定 n 个不匹配的括号序列，求一个排序，使得按照这个排列连起来形成的大括号序列匹配。

Sol: 我们设一个括号序列的权值为不匹配的左括号个数。如果剩余的是右括号，那么权值为右括号个数的相反数。

考虑这个权值序列，把正值放左，负值放右，如果权值和是 0 的话可以证明它一定是匹配的。

6s 1e7，随便过。

J: 给定一个 DAG，有两种点，一种 Merge 将两个输入按 121212 的顺序合并，一种 Split 将一个输入按 121212 的顺序分解。有很多询问，可以询问某个点的某个输入。

边数是 O(n) 的，所以我们完全可以模拟。复杂度 O(n^2)。