国庆题目
Maximize the Largest Component (Hard Version)
- 题意：
给定一个 \(n\times m\) 的网格，由“.”和“#”字符组成。
如果从该组中的任何单元格开始，通过仅移动到该组中共享一个共同边的另一个单元格，就可以到达该组中的任何其他单元格，则一组“#”单元格形成一个连通分量。其大小为该组中的单元格数量。
在一次操作中，选择任意一行 \(r\) 和任意一列 \(c\)，然后将行 \(r\)和列 \(c\) 中的每个单元格设置为 "#"。
问在最多执行一次操作后，可以实现的“＃”个单元格的最大连通分量的最大可能大小。
ps：保证所有测试用例中的 $ n \cdot m $ 的总和不超过 $ 10^6 $。
- 思路：
我们考虑到执行操作不会使答案更劣，所以我们一定会执行这次操作。
考虑到 \(n\times m\leq 10^6\)，那么我们可以暴力枚举选择哪行哪列。
考虑到如果在枚举内部统计答案不好做，哥们考虑预处理答案，那么可以单点算贡献。
我们看下一个点会在选哪行哪列时产生贡献。
显然如果该点在原本的图上最左边可到达 \(l1\)，最右可到达 \(r1\)，最上可到达 \(l2\)，最下 \(r2\) 的话，那么哥们会发现，只要我们选的行在 \([l2-1,r2+1]\) 的区间内或所选的列在 \([l1-1,r1+1]\) 的区间内，都可以产生贡献。
那么我们将我们的选择也抽象成一个矩阵，第 \(i\) 行 \(j\) 列记录的就是我们选第 \(i\) 行第 \(j\) 列的答案。
然后就变成一个套路的矩阵中一块的加减法，直接弄一个矩阵差分即可转为 \(O(1)\) 处理，最后再转回来即可，记得特殊处理你选的那行和那列的答案。
时间复杂度 \(O(nm)\)。
CF1984F
- 题意：
有一个长度为 \(n\) 的隐藏数组 \(a_1, a_2, \ldots, a_n\)，其元素是介于 \(-m\) 和 \(m\) 之间的整数。
给你一个长度为 \(n\) 的数组 \(b_1, b_2, \ldots, b_n\) 和一个长度为 \(n\) 的字符串 \(s\)，字符串由 \(\texttt{P}\) 、 \(\texttt{S}\) 和 \(\texttt{?}\) 组成。
对于从 \(1\) 到 \(n\) (含)的每个 \(i\)，我们必须有：
- 如果是 \(s_i = \texttt{P}\)， \(b_i\) 是 \(a_1\) 到 \(a_i\) 的和。
- 如果 \(s_i = \texttt{S}\)， \(b_i\) 是 \(a_i\) 到 \(a_n\) 的和。
输出使得数组 \(a\) 符合要求的将 \(s\) 中的所有 \(\texttt{?}\) 替换为 \(\texttt{P}\) 或 \(\texttt{S}\) 的方案个数。
由于答案可能很大，因此输出答案对 \(998244353\) 取模的结果。
ps：\(2\leq n\leq 2\times 10^3\)
- 思路：
可以先从简单入手，我们先考虑没有 \(?\) 的情况，
那么我们手玩一下会发现，我们一定能得到数列的总和，因为只要第一个是 \(S\) 或者最后一个是 \(P\) 或者 \(s\) 中有一个 \(PS\) 就一定能得到总和。
然后哥们手玩一下这些限制的关系（\(sum\) 为数列和）：
-
\(PP\) 限制了 \(b_i-b_{i-1}=a_i\)，而 \(a_i\) 是有范围的（下同）。
-
\(SP\) 限制 \(sum+b_i+b_{i-1} = a_i+a_{i-1}\)
-
\(PS\) 限制 \(sum=a_i+a_{i-1}\)
-
\(SS\) 限制 \(b_{i-1}-b_i=a_i\)
那也就是说，如果我们真的知道这个 \(sum\)，我们就可以用 dp 求出方案数。
观察到 \(n\) 的范围，我们可以直接枚举这个 \(sum\) 在那个位置出现（即上文提到的 \(sum\) 的出现方式），然后 dp 即可，时间复杂度 \(O(n^2)\)。