标签：方案 cnt le 题解 Codeforces mid 炮击 Div dp

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 解法

标签：方案,cnt,le,题解,Codeforces,mid,炮击,Div,dp
From： https://www.cnblogs.com/cantorsort2919/p/17623839.html