Codeforces Round 878 (Div. 3) 题解

发布时间 2023-08-11 19:55:44作者: cantorsort2919

A. Cipher Shifer

从头开始扫一遍即可,扫到两个相同的表示某一个字符的解密结束

B. Binary Cafe

首先,我们不妨把题意转换为 有多少种不同的花钱方案

因为每一种咖啡就是一个二进制有 \(k\) 位的数字的其中一位,而对于不同的方案,其二进制位不完全相同,则每一个方案对应的花费一定不同,即每一个花费和方案是一一对应的,且可以相互转化

完成这样的转化后,我们可以通过判断当前位数所表示的最大花费是否超过 \(n\) 来解决这个问题

C. Ski Resorting

我们可以计数连续的低于 \(q\) 的天数,注意到大于 \(k\) 天的部分可以扩散出去,在原结果的基础上进行计算,最后得到一段长度为 \(cnt\) 的部分,对方案的贡献是 \(\frac{(cnt-k+1)(cnt-k+2)}{2}\)

D. Wooden Toy Festival

题目要求最大值的最小值,显然二分答案

check 的时候,就看模拟过程中需要的雕刻师傅会不会多于 \(3\) 个即可

E. Character Blocking

可以考虑用队列模拟“封锁”的操作以及时间的流动

判断串是否相等时,可以用变量来记录串中不同字符的数量,接着根据交换、封锁进行自增、自减操作来判断结果

F. Railguns

要是没有 \(r\) 次激光炮这玩意儿就是个简单的 BFS

为了让总时间最少,Tema 肯定遵循最优路线

所以 Tema 到达 \((i,j)\) 的时间在 \([i+j,i+j+r]\)

那么设 \(dp_{i,j,k}\) 表示在时间 \(i+j+k\) 时能否到达 \((i,j)\)(其中 \(1\le i\le n,1\le j\le m,0\le k\le r\)

有转移方程

\[\left\{\begin{array}{lc} dp_{i,j,k}=dp_{i-1,j,k}\mid dp_{i,j,k}&i>0\\ dp_{i,j,k}=dp_{i,j-1,k}\mid dp_{i,j,k}&j>0\\ dp_{i,j,k}=dp_{i,j,k-1}\mid dp_{i,j,k}&i+j+k\text{ 这个时间没有被炮击} \end{array}\right. \]

检查某个时间某行列是否被炮击,用 set 维护每行列被炮击的时间然后二分查找即可

G1. In Search of Truth (Easy Version) & G2. In Search of Truth (Hard Version)

这玩意儿有一点玄学

easy 版,因为询问次数在 \(2000\) 以内,所以可以用 BSGS 来搞

hard 版就非常玄学,据说用随机数取值的方式可以让通过概率 \(\ge1-10^{-16}\)

找不到非随机数的 AC 解法