比赛链接

solved by nikkukun & qxforever

给一些文本串，将其中需要缩写的单词串改为首字母缩写形式。需要缩写的串满足：

1. 每个单词首字母大写，且之后有至少一个小写字母
2. 每个单词之间仅有一个空格连接

🐴力题。

idea from potassium, implemented by nikkukun

给一些 $01$ 串，每个串中最多有一个 ?，其中可以填 $0$ 或 $1$。指定一种填的方案，使得不存在一个串是另一个串的前缀，或说明无解。

字符串总长度为 $5 \times 10^5$。

把 Trie 建出来，将有问号的串分别考虑 $01$ 后都插入到树上，这样变成在树上选一些点，这些点两两之间要满足一些限制：

1. 同一个串对应的两个点恰选一种
2. 选中一个点后，其祖先不能有其他点被选
3. Trie 树的一个节点中，只能有一个点被选

这就是一个 2-SAT 问题。

限制 1 的建图：基操。

限制 2 的建图：额外设置一个辅助变量 $t_u$ 表示 $u$ 及其祖先是否有点被选，则某个点 $u$ 被选，当且仅当 $t_u$ 为真且 $t_{\mathrm{pa}(u)}$ 为假。显然 $t_i$ 变量是可以在相邻两个位置建立关系的，详见 CF1215 - Radio Stations。

限制 3 的建图：可以类似情况 2 额外设置 $O(n)$ 个辅助变量，使得一个树的节点中最多选中一个节点。也可以通过观察发现，如果某个节点超过该节点的串长度 $+ 1$，则怎么赋值都会产生无解，这时暴力两两加限制的均摊复杂度是 $O(1)$ 的。

solved by nikkukun

一个共享单车停车场会在一些时刻有人借车或还车，且同一时刻只会发生其中一种事件，若某个时候无车可借时，就会排队等待到下一次有人还车。$10^5$ 次询问停车场初始有 $b_i$（$0 \leq b \leq 10^9$）辆车时，所有人的等待时间之和，或说明根本等不到车。

时刻数不超过 $10^5$，单次借还数量不超过 $10^4$。

先假设初始时没有车，把每个时刻的总借车人数（包括等待中的）减去总归还车辆数的差按时间在坐标轴 $xOy$ 上画出，则所有人的等待时间为 $y \geq 0$ 部分的面积。而改变初始车辆数，等于一同变化整体高度，因此维护好每一个矩形块的高度和面积即可 $O(\log n)$ 计算答案。

solved by nikkukun & qxforever

给一个叠叠乐，每次抽掉其中的一块，如果有某一层之上的总重心投影超出了该层平面的凸包或在边界上，则积木倒塌。

求哪次操作之后倒塌，或说明不会倒塌。

注意到范围很小，因此对每层维护 $\sum_i m_i \times x_i$ 和 $\sum_i m_i$（$x_i$ 为某个方向的坐标轴），就可以计算出某一层之上的重心了。所有的变量都可以在一次抽掉积木后 $O(\max \{h, n\})$ 更新。