有 $n$ 个人, 有些人说真话, 有些人说假话, 每个人都知道所有人是说假话的还是说真话的, 现在问他们每一个人: 说真话的人有多少. 每个人都会给出一个答案. 说假话的人会随便给出[1,n]中的一个数, 但不会给出真实的答案. 现在, 给你两个数 $n, K$, 问你有多少种方案, 能确定恰好有 $K$ 个人说谎. 保证 $n$ 是 $2$ 的幂, 答案模 $777777777$.

$1 \le K \le n \le 2^8, n = 2^p$

假设有 $x$ 个人说真话, 那么会有正好 $x$ 个人给出答案 $x$.

但是会有同时发生的情况 $y$ 个人给出答案 $y$, 这样我们就不能确定到底是 $x$ 个人还是 $y$ 个人说谎了.

所以这种方案不能算.

也就是说, 要求仅有一个数$x$, 满足正好 $x$ 个人给出答案 $x$.

求方案数, 考虑dp.

我们可以用组合数学的思路来想, 有 $n$ 个空, 每个空需要填一个数字, 要求满足有$x$个位置填的是$x$

$dp(i, j, k)$ 表示填入了 $[1, i]$ 个数字在 $j$ 个空中, 其中 $k$ 个人说假话.

用System.Drawing.Graphics的CopyFromScreen()函数即可.

不太懂, 先记着, 大概是调用 user32.dll 里的函数, 参数看不懂

想做一个BS刷野辅助器, 但是用WPF的TopMost不能在全屏游戏下置顶. 辗转了几天, 终于找到了解决方案 —— 使用 OpenGL GLFW.

一条路上按顺序有 $n$ 瓶毒药, 对于每个 $i \in [1, n]$, 求出如下的值: 从i出发, 每个时刻都可以向左或向右, 最终可以得到一个吃毒药的排列$P$, 一个排列的伤害定义为$\sum_{j=1}^n D_j \cdot [P_{C_j} = j]$, 求可能的排列中最大的伤害值. $C$和$D$给出.

$2 \le n \le 3 \cdot 10^5$

区间DP显然.

不过这里的状态定义和平常不太一样. 因为要算从每个点走完所有的值, 如果从小区间推到大区间的话, 就要枚举起点, 复杂度$O(n^3)$, 怎么都压不下来.

设$dp(i, j)$为已经走完了区间$[i, j]$, 走完剩下的所有点还需要的最大花费. 转移从大区间推到小区间, 答案就是$dp(i, i) + D_i \cdot [C_i = 1]$.

方程很容易推得:

$$dp(i, j) = max \{ dp(i-1, j) + D_i \cdot [C_{i-1} = j-i+2], dp(i, j+1) + D_j \cdot [C_{j+1} = j-i+2] \}$$

有一个长度为$n$的数组$a$, 满足$a_i \in \{0, 1, 2\}$, 你要将其划分成一些连续的区间, 每个区间的长度在$[L, R]$之间, 每个区间的贡献是:

• $-1$: 这个区间的和小于$0$
• $0$: 这个区间的和等于$0$
• $1$: 这个区间的和大于$0$

问最后总的贡献最大是多少

$1 \le L \le R \le n \le 10^6$

显然dp. 设$dp(i)$为前$i$个划分区间的最大贡献, 有

$$ dp(i) = \max_{L \le i-j \le R} \begin{cases} dp(j) + 1, & s_i - s_j > 0 \\ dp(j), & s_i - s_j = 0 \\ dp(j) - 1, & s_i - s_j < 0 \end{cases} $$

($s_i$ 表示$a_i$的前缀和)

朴素转移是$O(n^2)$的, 考虑优化.

从长度为$n$的序列$a$中取一些数, 要求两两满足倍数关系. 问最多取多少个数.

$1 \le n \le 2 \cdot 10^5, 1 \le a_i \le 10^7$

考虑dp, $dp(x)$表示取出来的数不超过$x$ 且一定取$x$, 最多能取的数量. ($10^7$的数组能开)

方程

$$dp(x) = cnt(x) + \max_{y | x} dp(y)$$

其中$cnt(x)$是$x$在$a$中出现的次数.

这可能就是一个"倍数关系转移"的思想吧, 这种题碰到的少, 要牢记.

$O(MAXA\log MAXA)$比较极限.

用类似埃筛的方法转移: