Codeforces Round #619


A. Three Strings

题意

对于每一个 \(i\),必须交换 \(a_i,c_i\) 或者 \(b_i,c_i\) ,问最后是否有可能使得 \(a=b\) 。

分析

显然,最后要想等,对于每一位必须有 \(a_i=c_i\) 或者 \(b_i=c_i\) 。

B. Motarack’s Birthday

题意

给一个数列,讲数列中所有的 \(-1\) 均替换成同一个数 \(x\) ,使得相邻数的绝对值的最大值最小。

分析

如果我们把所有的与 \(-1\) 相邻的数全部取出来。

显然,我们肯定会吧 \(x\) 设为最大和最小之间的中间数。

然后将所有的 \(-1\) 替换成 \(x\) 计算一遍相邻数的绝对值的最大值即可。

C. Ayoub’s function

题意

将一个长度为 \(n\) 的串中的其中 \(m\) 位设为 \(1\) ,使得包含 \(1\) 的子串数量最多。

分析

要使得包含 \(1\) 的子串最多,显然就是要使得不包含 \(1\) 的最少。

不包含 \(1\) 的比较好考虑,对于 \(1\) 的位置其实是吧字符串切成了若干段,对于连续的全 \(0\) 长度为 \(l\) 的子串,显然包含 \(\frac{l(l+1)}{2}\) 个不包含 \(1\) 的子串。

那么我们要最小化这个数量,显然是要尽可能的最小化 \(l\) ,而 \(m\) 个 \(1\) 会把字符串分成 \(m+1\) 段,于是我们肯定会尽可能平均的分配这个 \(l\) .

D. Time to Run

题意

相邻的各自之间有两条往返路,显然要求道路不重复的任意游走 \(k\) 步,求一个构造方案。

分析

显然,最多游走的步数就是道路的总数量。

于是考虑一种构造方案,能够不重复的经过所有的道路,这样比较小的 \(k\) 步从这里面截取前一部分即可。

构造还是比较显然的:

  1. 第一行一直向右走到底;
  2. 第一行向左回到起点;
  3. 然后向下一步,移到下一行;
  4. 向右走到底;
  5. 不断重复上下左,直到回到这一行的第一列;
  6. 重复第三步到第五步,直到处理完最后一行;
  7. 不断的向上走,回到第一行第一列。

不够需要注意,\(m=1\) 的情况,可能会导致循环步长 \(=0\) 的情况出现。

E. Nanosoft

题意

每次询问给出一个子矩阵,在子矩阵中找到最大的 \(l\) ,使得存在一个 \(2l\times 2l\) 的正方形子矩阵,满足题目要求的四个颜色分布。

分析

我们可以预处理每一个位置作为中心的时候,可以得到的最大 \(l\) 的大小。

可以通过枚举中心位置,二分 \(l\) 的大小,然后分别通过四种颜色的前缀和来得到一个子矩阵的和,判断是否可行。

之后,对于每次询问的子矩阵,我们也可以同样二分答案。

对于二分的答案,我们可以得到中心位置所在的范围,我们现在只需要直到中心位置所在的范围内是否存在 \(l\) 大于等于当前二分的答案,因为只要大于等于当前,显然我们可以选择当前的 \(l\) 。

而对于一个子矩阵中最大值的维护,我们用二维 ST 表即可。

F. Super Jaber

题意

给一张 \(n\times m\) 的图,每个位置有一个颜色,每次询问一个位置到另一个位置的最短距离。

可以通过下面两种方式来走:

  • 花费代价 \(1\) ,向四个相邻方向任意走一步;
  • 花费代价 \(1\) ,移动到任意一个相同颜色的位置。

分析

我们可以考虑成,颜色是一种走路的媒介,即预处理出 \(f[i][j][c]\) 表示从位置 \((i,j)\) 出发走到颜色为 \(c\) 的位置所需要的最少步数。

考虑对于每一种颜色单独处理,从每一个位置出发可以选择走四个方向,或者移动到同颜色的位置,但是每次都考虑移动到同颜色的位置,显然时间复杂度是不能接受的。

但因为每一步的代价都相同,那么显然,移动到相同颜色的位置,在发生过一次以后,之后的都没有意义了。

所以对于每一种颜色单独考虑的时候,对于每一种颜色同颜色的移动只发生最早的一次即可。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments