在二维平面上给出 $n$ 个敌军的坐标 $A_i(x_i, y_i)$, 再进行q次强制在线询问:

每次询问将给出一个炮台坐标 $(x_m, y_m)$, 需找出所有能被坐标 $(x_m, y_m)$ 攻击到的敌军的下标. 这里定义炮台 $(x_m, y_m)$ 能攻击到的范围是 $y = y_m \pm \frac{x - x_m}{2}$ 所夹出来的右半部分, 包括边界.

接下来将这些下标按照升序排序, 记为$i_0, i_1, \dots i_k$

计算结果 $(\sum_{j=0}^{k-1} i_j \cdot 5782344^j) \mod 10^9 + 7$, 输出结果.

$1 \le x_i, y_i \le 10^9, 1 \le n, q, \le 10^5$

保证所有查询中被攻击到的敌军总数不超过 $10^6$, 保证$x_i > 0, x_m < 0$

有两种考虑方式.

第一种

施鹏飞学长讲的:

注意到每个炮台所能攻击到的范围角度是固定的, 所以为了更好地刻画炮台 攻击的覆盖范围, 我们可以将炮台的攻击范围投影到$x=0$这条线上; 类似地, 将每个敌军以同样的角度都投影到$x=0$这条线上. 如果两条线段有交集, 那么 该炮台就可以攻击到这个敌军.

$n$ 个长为 $m$ 的不同字符串, 等概率地藏起来一个字符串, 然后游戏者来猜藏起来的串是什么. 每一步游戏者等概率地询问该字符串的某个位置的字符是什么. 不断地知道该字符串的一些位置的字符后, 游戏者就可以确定藏起来的串是什么, 题目要求游戏者的期望步数.

$1 \le n \le 50, 1 \le m \le 20$

这个步数期望的贡献转化没见过, 记下来.

由于期望的线性性质, 我们可以先求猜出某一个的期望步数. 这样乘以 $\frac{1}{n}$ 就是所有的期望步数了.

然后考虑如何求猜出一个串的期望步数.这里转化一下贡献, 把步数拆开, 即变为 $$E’ = \sum_{s \in ALL, |s| = 1}P(s) \cdot 1(\text{走第一步}) + \sum_{s \in ALL, |s| = 2}P(s) \cdot 1(\text{走第二步}) + \dots$$

其中$ALL$是询问集合全集, 即每个位置都询问.

可以发现, 某个字符串对答案有贡献, 当且仅当走第 $k$ 步不能确认.

再根据线性性质, 把询问$s$不能确认的字符串个数加进去, 就有 $$E = \sum_{k=0}^{m} \sum_{s \in ALL, |s| = k}P(s) \cdot \frac{\text{#不能确定的字符串}}{n}$$

有 $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] \}$$