二维平面上有 $n$ 个点$(x_i, y_i)$. 有一辆电汽车, 电池容量为 $W$, 要从点 $s$ 到点 $t$. 每个点都可以充电, 充一个单位的电量需要 $c_i$ 点花费. 一个单位的电量能走一个单位距离. 两个点之间的距离是笛卡尔距离. 开始时车在 $s$ 点电量为 $0$, 问在充电次数不超过 $\Delta$ 的情况下, 到达 $t$ 点的最小花费.
$1 \le n \le 1000, 0 \le x_i, y_i \le 10^6, 1 \le c_i \le 10^4, 1 \le W \le 10^5, 1 \le \Delta \le 10$
首先想到经典贪心题. 确定一条路线, 那么一定是两种选择:
根据这两个决策, 我们设计dp.
$dp(i, x, 0)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从某个点充到刚好能过来, 即现在的电量为 $0$.
在二维平面上给出 $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.
