题目链接。 解析 首先第一个帖子肯定会由某一个账号发出。大力观察可以发现当第二个账号发帖之后，接下来一定可以至少两个账号交替发帖，即安全系数不再会有损失。我们仅需要解决第二个账号第一次发帖在哪一个位置即可。 假设我们确定了第二个账号第一次发帖的位置 $i$，那么剩下的 $k-2$ 个账号一定会在 $[i+1,n]$ 中选择 $k-2$ 的最大值进行…

题意 题目链接。 数轴上有 $n$ 个虫洞，有 $q$ 个按坐标升序给出的飞船，保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格，对于每个飞船，求到达任意一个虫洞的期望时间。 解析 记 $f_i$ 为位置在 $i$ 的飞船的期望时间，只要 $i$ 位置没有虫洞（有虫洞期望时间显然为 $0$），就有 $f_…

题意 题目链接。 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，每次操作选择 $k$ 个数，将这 $k$ 个数减去他们的与（二进制运算中的与）的和。求哪些 $k$ 可以在有限次操作内使所有数变成 $0$。 解析 蛮有趣的。把所有数化成二进制后，你考虑每一位。如果共有 $x$ 个数在某一位上为 $1$，那么考虑如果指定了一个 …

fhq_treap（无旋 treap） 参考：远航之曲的博客。 感觉比较意识流。 核心思想是平衡树分裂和合并。 类似于 Splay 把区间分离出来，fhq_treap 可以把平衡树进行分裂来提取需要的区间，再通过合并平衡树来维持树高（即堆性质）。这样不仅可以做到维护区间，还免去了旋转操作，代码较为简单。 split & merge &…

在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法，更推荐类似于 Dinic 的 spfa+dfs 的写法，详见最下方的“附加代码”部分。 MCMF（基于 spfa 实现） 模板题：Luogu3381。 即给定一张网络，每条边都有一个权值和流量限度，这条边上每有一个流量，总费用就加上这个权值，你需要在…

题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放，计算出每张纸片有多少种放法，这分为三种情况： 最后局面该纸片占两格，显然只有 $1$ 种放法。 最后局面该纸片占一格，那么可能的放法有 $4$ 种，去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片，那么可能的放法为所有未被覆盖的位置的放…

题意 题目链接。 给你一个序列 $a$，让你输出一个序列 $b$ ，这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。 解析 先考虑这么一件事情：假如你已经确定了这 $x$ 个位置是什么，那么问题转化为：你需要将若干个元素交换位置，使得与原来元素相同…

考得不好，理论上要得分 $360$ 才算差不多。 10.22 ＆ 10.23 上午 大部分时间都在颓，感觉确实是越到考试边上越不想看东西。最后强迫自己看了看版本，事实证明完全没用，没想到的还是没想到。 感觉还是平时熟练掌握有用。 CSP-S2 拿到题目先看 T1，稍微画了一下想了十分钟，感觉会做，搞个 set 一层一层搞就行了，码完大概半个小时，还…

块状链表 参考：Tak_vin 的 博客 及相关代码。 这篇可能写的巨草，主要是给我自己看的。 一种根号数据结构，支持一个区间的动态插入和随时访问。 以 Luogu4008 [NOI2003] 文本编辑器 为例。 题意： 维护一个文本编辑器，支持： Move/Prev/Next 移动光标位置 Insert 在光标处插入若干个字符 Delete 删除…

题意 在左下角是 $(0,0)$，右上角是 $(W,H)$ 的网格上，有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数，是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …