CSP2023

CSP-J 2023 T4

感觉提高组没这个难。

暴力的做法是 \(f_{u,i}\) 表示到 \(u\) 的时间为 \(i\) 是否可行。不过发现如果 \(f_{u,i}=1\)，则 \(f_{u,i+k}=1\)，所以只需要记录 \(f_{u,i}\) 表示模 \(k\) 余 \(i\) 且可行的最小的 \(j\) 即可。

CSP-S 2023 T1

直接把所有操作一步到达的状态跑出来求个交。

CSP-S 2023 T2

考虑一个暴力：枚举左右端点，判断是贪心消栈，能消就消。

考虑求出来对于每个右端点哪些左端点是合法的。注意到如果找到最大的 \(l\) 满足 \([l,r]\) 合法，那么 \(l+1\) 形成一个子问题。所以只需要求 \(pre_r\) 表示 \(r\) 前最大的 \(l\) 满足 \([l,r]\) 合法。考虑 DP 算这个东西，从 \(r-1\) 转移过来，那么 \([l+1,r-1]\) 一定是一个空栈，且 \(s_l=s_r\)。直接暴力跳 \(pre_{r-1}\) 找到最大的 \(s_l=s_r\) 的 \(l\)，不过因为字符集只有 \(26\)，所以直接预处理 \(ch_{r-1,c}\) 表示 \(s_r=c\) 的时候的结果即可。复杂度 \(\mathcal{O}(n|\Sigma|)\)。

CSP-S 2023 T3

直接模拟。

我的写法是开一个结构体记录元素，结构题里面存名字的字符串，起始位置，类型，还有大小；开一个结构体记录类型，类型存大小，对齐要求，和里面的所有子元素，对子元素求它在当前结构体的起始位置，名字，大小。然后直接模拟就好了。

好像没什么好讲的。

CSP-S 2023 T4

二分算出来第 \(i\) 个数的 ddl。然后要求一个是否有一个拓扑序 \(p\) 使得 \(p_i\leq d_i\)，我们把 \(d_u\) 对它子树取 min，使它满足一个堆的性质，然后直接贪心每次放限制最小的就完了。

啥子，我感觉它假了啊。