$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}$$

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

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

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

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

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

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

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

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

咕 咕 咕 咕 咕

QAQ 两小时建站, 因为我 Nginx 的配置文件忘记打后缀了一直没配进去.

数值为 $i (0 \le i < n)$ 的数有 $c_i$ 个. 从中选取一些数 $S, |S| > 0$, 变为 $\rm{mex}\{S\}$ 放回. 最后剩一个数, 问这个数最大是多少.

$1 \le n \le 10^5, 0 \le c_i \le 10^9, \sum c_i \ge 1$

不会思考的人有难了!

一开始想的是把某点之后所有的数单独拎出来变成 $0$, 然后 $0$ 往上推. 这样就几个问题. 首先是这个点会不会在同一个数里, 然后是即使往上推, 如果有多的, 我还可以拿出来变成 $0$. 比如 $0, 1, 1, 1, 2$, 可以 $2$ 不动, 但是拿出两个 $1$ 变成 $0$. 还有一个, 不是说要"物尽其用", 有时候可以通过"放弃"来达到更好的结果. 假设有 $4, 5$ 两个数, 虽然我可以变成两个 $0$, 但是如果恰好多出来一个 $0$, 比如说最后变成了 $0, 3$, 然后再做的话答案就是 $2$; 但其实可以"丢弃"一个数, 即取出 $4, 5$, 取 $\rm{mex}$ 为 $0$. 这样就只有一个 $3$ 了.

二位平面上 $n$ 个点, 两两不重叠, 要求用两种颜色的边分别把他们连成一个连通块. 连边操作用一个 长度为 $k \ge 2$ 的序列 $s_i$ 表示, 方法如下:

1. 第一种颜色: 对所有 $1 \le i \le \left\lfloor \frac{k}{2} \right\rfloor$, $s_{2i−1}$ 和 $s_{2i}$ 连边
2. 第二种颜色: 对所有 $1 \le j \le \left\lfloor \frac{k-1}{2} \right\rfloor$, $s_{2j}$ 和 $s_{2j+1}$ 连边

求一个最短的序列 $s_i$, 满足上述条件, 且要求序列中相邻两个点不同, 对于同一种颜色, 连得边仅在端点处有相交.

$2 \le n \le 10^4$

题解

考虑最短序列, 应该为 $2n - 1$. 尝试这样是否可行. 从点数很少时手玩, 从简单的方向入手, 尝试构造两条链, 发现确实可行. 不考虑相交的话, 可以这样构造: $1, 2, \dots, n-1, n, n-1, \dots 2, 1$. 而且这两条链是一模一样的. 那么只需要考虑一条链不相交即可.

无穷大的二位网格平面上, $(0, 0)$ 处有一个障碍物. 现在有一个由 R, L, U, D 组成的长度为 $n$ 的操作序列和一个机器人. 操作序列表示控制机器人如何走(上下左右), 如果机器人的下一步是障碍物(即原点), 那么他不行动. 现在有 $Q$ 次询问, 每次询问给出机器人的起点, 问终点. 保证机器人不在 $(0, 0)$.

$1 \le n, q \le 3 \cdot 10^5$

jyz nb!

不要被"一个“给误导了, 把所有询问都放在图上, 然后同时开始执行操作, 想象一下, 是不是有种"背景在动"的感觉? 没错, 这就是 “相对运动”. 与其操作 $Q$ 个机器人, 不如反向操作一个障碍物. 假设在障碍物移动的过程中, 没有碰到任何机器人, 那么障碍物移动的轨迹反一下, 就是所有机器人移动的轨迹了. 障碍物移动的轨迹可以通过二位向量前缀和求得. 统计答案每个机器人起点对它做差即可. 于是, 对于障碍物移动过程中碰到的机器人, 我们想办法改变机器人的起点, 使得其终点不变, 但不再碰见障碍物. 这是好办的, 因为障碍物碰见机器人了的话, 就证明机器人在这个时候会去撞障碍物(相对运动), 那么让机器人"后退"一步, 再执行这个操作, 后续操作是一模一样的. 所以做法就是, 相对运动移动障碍物, 碰到机器人就"推"一下. 需要注意的是, 障碍物移动一下最多推 $n$ 个机器人, 但是这些机器人在后续操作中就等价了, 所以只用搞一个代表出来就行, 用并查集合并一下即可.