[Codeforces is All You Need] CR 833 ABC (1748ABC) - Solution

2022-11-13 02:30 作者:故寓诸无竟 0人读过 | 我要投稿

这是ABC的合集题解

问题简述

Problem A：给定 $n$ ，计算使用大小为 $1%5Ctimes%20%5Cleft%5Clceil%20%5Cfrac%7Bi%7D%7B2%7D%20%5Cright%5Crceil%20(1%5Cle%20i%5Cle%20n)$ （每个 $i$ 各有一个）的方块能拼出的最大的正方形。

Problem B：给定一个长度为 $n$ 的数字串 $s$ ，求其所有“多样”的子串。一个子串“多样”意味着其中所有的数字出现的次数不超过该子串中不同数字的数目。

Problem C：给定一个长度为 $n$ 的序列 $a$ ，现在可以将其中的 $0$ 变成任意整数。求变化后最多有多少个 $a$ 前缀序列之和为 $0$ 。

原比赛链接：https://codeforces.com/contest/1748

思路

Problem A：答案就是 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 。首先说明只有边长 $%5Cle%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的正方形才可行：不难发现 $%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%5Clceil%20%5Cfrac%7Bi%7D%7B2%7D%20%5Cright%5Crceil%20%3D%20%0A%5Cbegin%7Bcases%7D%0A%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%5E2%20%26%2C%20n%20%5C%262%20%3D%201%20%5C%5C%0A%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%5E2%2B%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%20%3C%20(%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%2B1)%5E2%26%20%2C%20n%20%5C%26%202%20%3D%200%0A%5Cend%7Bcases%7D$

（真的不难发现，就是简单的分类讨论，然后等差数列求和），由此可行的正方形边长不会超过 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 。也不难构造出一个边长为 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的解：取一个 $1%5Ctimes%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的方块；此外大小为 $1%5Ctimes%20u$ 和大小为 $1%5Ctimes%20(%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%20-u)$ 的方块拼一起作为一组（ $1%20%5Cle%20u%20%3C%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%2F2$ ）；总共得到恰好 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 组。证毕。

Problem B：由于一共就只有 $0%5Csim9$ 这10个数字，因此实际上符合要求的子串长度不超过 $100$ 。直接暴力判断的复杂度为 $O(10000n)$ ，略高了。可以使用前缀和优化（统计不同数字出现次数的前缀和，这样可以在 $O(1)$ 内计算每个数字出现了多少次），这样复杂度为 $O(100n)$ 。

Problem C：（贪心）对于前缀和序列 $s$ ，不难发现，（1）当我们将 $a_i(a_i%3D0)$ 调整为任意其它整数时，等价于把 $s_j%20(i%5Cle%20j%20%5Cle%20n)$ 同时增加了某个整数。另一个重要的发现是，（2）如果我们调整了 $a_i(a_i%20%3D%200)$ ，如果存在 $a_j%20%3D%200%2C%20j%20%3E%20i$ ，那么 $a_i$ 的调整对 $s_k%20(j%20%5Cle%20k%20%5Cle%20n)$ 并没有影响（因为调整是任意的）。于是，对于 $a_i%3D0$ ，我们只需要贪心地考虑 $i%5Cle%20k%20%3C%20j$ 下标对应的前缀和（其中 $j$ 是 $i$ 之后第一个为 $0$ 的元素的位置；如果 $i$ 已经是最后一个了，那么 $j%3Dn%2B1$ ）。根据（1）的结果，这时候最佳的贡献应该是该下标区间内出现最多的前缀和值。使用std::map就可以轻松地统计每个前缀和值出现的次数。总的复杂度为 $O(n%20%5Clog%20n)$ 。如果用hash表会更快一点。另外，不要忘记统计第一个 $0$ 之前的前缀和中值为 $0$ 的个数！（因为这个WA了几发。）