24h 极限编程 x
24h 极限摸鱼 ✔

长度为 $n$ 的序列 $f_n$, 从中选出若干个数, 不改变其相对顺序, 使得 $\sum\limits_{j=1}^{k-1} f_{i_j}\&f_{i_{j+1}}$ 最大. $2 \ne n \le 10^6, 0 \le f_i \le 10^{12}$.

首先很容易想到一个 $O(n^2)$ 的 dp: 设 $dp(i)$ 为前 $i$ 个中, 选的最后一个为 $i$, 能得到的最大值. 方程为 $dp(i) = \max\limits_{1 \le j < i} \{dp(j) + (f_i \& f_j)\}$. 但很显然 $O(n^2)$ 是过不了的. 并且这范围好像用个数据结构维护起来都可能 T. 这里有个位运算. 所以一个方向是按位考虑.

我们看这个方程实际上是在干什么, 他就是一个很简单的枚举. 然后我们看一般的动态规划优化是在干什么, 他是将一些一定不是可能的最优解排除掉, 不去枚举他, 而是枚举一定可能是最优解的决策点. 那么我们需要做的就是从这个方向去考虑. 结合位运算, 那么一个方向就是, 考虑每一个位, 能不能排除一些一定不是最优的解.

由于 $f_i$ 对 $dp(i)$ 多出来的贡献是每一位是 $1$ 的个数, 那么我们可以枚举第几位, 考虑"这一位是1"的所有决策. 把这些决策单独拎出来, 一定会从离 $i$ 最近的点 $k$ ($k < i$) 转移过来, 否则假设从 $l$ ($l < k$) 转移过来, 那么如果把 $k$ 加进去, 答案会更优, 因为这一位的贡献是一样的, 但是由于 dp 值是递增的, 所以从 $k$ 转移会更好. 然后考虑"这一位是0"的所有决策, 也是同理. 那么我们把每一位都这样考虑掉, 实际上就是减少了很多不必要的枚举量, 从而使复杂度降下来.

$n$ 个点, 点权为 $a_i$. 两点之间有 $\frac{a_i}{a_i + a_j}$ 的概率从点 $i$ 向点 $j$ 连一条有向边(否则即有 $\frac{a_j}{a_i + a_j}$ 的概率 $j \to i$). 即根据概率建一个竞赛图. 求能到达其他所有点的点的期望个数.

$1 \le n \le 14, 1 \le a_i \le 10^6$

点数很少, 所以尝试点集为 $S$, 事件 $f(S)$ 表示有且仅有 $S$ 中的点能到达所有点, 直接根据期望的定义去计算答案, 应该为 $\sum |S|P(f(S))$.

现在考虑 $f(S)$ 如何计算. 首先我们可以发现 $S$ 一定是一个强连通分量, 且有 $\forall x \in S, \forall y \in \overline S, x \to y$ (之后用 $S \to \overline S$ 表示). 简单考虑一下后面这个条件的必要性: 若 $\exists (y \in \overline S, x \in S), y \to x$, 若 $S$ 中有其他点, 则要么 $\exists z \in S, z \ne x, z \to y$, 这种情况 $y$ 能和 $S$ 一起组成 SCC, 与 $f(S)$ 的定义矛盾; 若 $S = \{x\}$, 反过来考虑, 也会有 $x$ 可能与 $y$ 的 SCC 组成 SCC. 与 $f(S)/f(\{x\})$ 矛盾, 若不然, 则仅有 $f(\{y\})$, 与 $f(\{x\})/f(\{x\})$ 矛盾.

2021 年 10 月 18 日晚, 我正在学 CTF, 当我对知识点有一点模糊的时候, 我去翻我博客记录, 结果…

几个月前了解了这部片子, 有幸在国庆观赏. 总的来说是一部不错的青春励志片.

$n$ 个人选 $n$ 个物品, 每个人选一个. 每个人对物品有一个喜爱值 $a_{ij}$. 从第一个人开始, 在没有被选的物品中随机选择一个物品 $j$, 概率为 $\frac{a_{ij}}{\sum_{k\in S} a_{ik}}$, 其中 $S$ 是剩余物品集合. 问每个人选到每个物品的概率, 答案对 $998244353$ 取模.

$1 \le n \le 20, 1 \le a_{ij} \le 100$

学好概率论, 走遍天下都不怕(雾)

根据全概率公式, 一个很自然的思想是: 设 $A_{ij}$ 为事件 “第 $i$ 个人选到第 $j$ 个物品”, 那么有:

$$\begin{aligned} P(A_{2j}) &= \sum_{k \ne j} P(A_{2j} | A_{1k}) \cdot P(A_{1k}) \\ P(A_{3j}) &= \sum_{k \ne l \ne j} P(A_{3j} | A_{2k}A_{1l}) \cdot P(A_{2k} | A_{1l}) \cdot P(A_{1l}) \\ \cdots \end{aligned}$$

第一次给游戏写后感. 说是游戏, 不如说是小小说.

一开始女孩的情节, 有些俗套, 我这个不看书的人都猜得到前半段剧情的走向. 但真正惊艳我的, 是随着游戏的推进, 层层拨开迷雾, 最后了解女孩, 男孩, 和第七号列车的原委……

“这是一场单程旅行, 票价昂贵, 终点有最美的风景”

女孩述说着她和男孩之间的故事, 眼角泛起泪光 — — 那也是他的眼睛. 手术很成功, 女孩睁开眼, 看见了整个世界, 看不见整个世界. 做一场梦罢, 一场现实存在的梦. 他出现过, 他没出现过. 女孩逃票, 上了这趟列车, 想追随他的脚步, 追寻自己存在, 或者不存在的意义.

我惊讶于列车, 实际上是"摆渡人". “单程”, “昂贵”, “终点”, 女孩时不时揉搓手腕. 当我不忍心将女孩赶下车时, 结局那黑白中手腕处的一抹鲜红, 我还没有发现列车的秘密. 当列车自己告诉我时, 原来处处都是伏笔.

男孩"上了车", 他爱着女孩, 不是那种世俗的爱, 而是精神上的, 灵魂上的伴侣. 男孩不想让女孩走向终点, 劝说列车赶女孩下车. 死神也有被美丽的爱情打动的时刻啊.

如果是从女孩讲完故事就结束了, 那就索然无味了. 列车这一角色, 贯穿整个故事, 也是整个故事升华的亮点. 美丽的爱情感动人, 感动天地, 甚至感动死神, 这才是惊天动地的故事. 个人觉得比梁祝化蝶更具有冲击力.

这部作品和真正的文字相比, 表现力显然是差了许多的. 原因在于场景固定在了列车上, 女孩的故事仅通过对话展开, 而且占篇幅的九成多, 没有心理描写的衬托, 也没有环境描写的渲染, 对于游戏来说, 更是没有动画或图片或声音的铺陈. 但是为何这样的"及格线作文"能够如此引人入胜? 个人认为关键在于剧情, 以及叙述手法, 完全可以掩盖这些瑕疵. 仔细想想, 只有对白, 其他一切留给读者想象, 就好像真的在听一个同行人的故事. 这一点完美契合了"列车"的主题. 好的作品不一定面面俱到, 在一个特殊的方向上取胜, 另辟蹊径, 方能扬长避短, 也是优秀至极的游戏.