CodeForces - 1426E Rock, Paper, Scissors

题意

A出a1次石头，出a2次剪刀，出a3次布，B同理。顺序自定。求the minimum number of round Alice can win和the maximum number of rounds Alice can win。

题解

思维题

先说max。每次决策非常独立。易得A的石头最多赢 \(min(a1,b2)\) 次（其他同理），而且这样取互相不会影响（石头赢并不影响剪刀赢）。

再说min。如果要赢得最少就要输的和平的尽量多。但是输的和平的不知道怎么分配

牛客多校6 E - Sequence

题意

给定一个长度为 n的序列 a

多个询问，每次询问一段区间 l, r, k, 求是否能将这个区间分成 k个部分使得每一部分的和都是偶数

复杂度为O(n+q)

题解

“考虑从左到右扫，只要当前和为偶数就把它切开

那么我们可以得到这个区间最多能分成多少个偶数部分

这个过程可以通过记录奇偶性（奇数当成1，偶数当成0）的前缀和来维护 时间复杂度:O(n + q)”

一个简化：奇数当成1，偶数当成0

再一个通项：00100010001000100

为啥这样会没有后效性呢？试一试就知道了。

因为在[l,r]之内都必须满足，所以可以直接从前往后扫。（从l开始策略很固定）

tip:有的时候查找一段的信息可以用前缀和。

B - Distance

一个很高级的公式： \[ \sum^{min(x,y)}_{i=0}(^x_i)(^y_i) = (^{x+y}_x) \] 证明如下：

\(\because (^y_i)=(^y_{y-i})\)

发现上面加起来是x+y，下面加起来是y（这里设x>y）

注意\((^{x+y}_x)=(^{x+y}_y)\)