Problem - 1635F - Codeforces 首先考虑一下如果已知一个位置 $i$ 怎么样选择 $j$ 最优，发现这个东西不是很好维护。 但是我们发现不知道怎样选择我们可以考虑有哪些 $j$ 可能成为最优解。 如果说 $x_{j1} < x_{j2} \ \cap\ w_{j1} \le w_{j2} $，那么 $j2$ 是没有必要的。 同理如果考虑已知 $j$，对于 $x_{i1} < x_{i2} \ \cap \ w_{i1} \ge w_{i2}$ 那么 $i1$ 是没有必要的。 显然这个东西是有单调性的，我们考虑维护一个单调栈。 不妨考虑从左向右扫，之后考虑加入一个元素肯定是要计算这个元素与之前元素的贡献。 考虑加入一个元素的时候一直进行更新直到找到一个没有必要更新的位置。 使用单调栈维护不合法的递增二元组即可。 这样我们加入的时候可以直接使用和当前位置不能有单调性的元素。 询问离线即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454 ...

Problem - 1453F - Codeforces 感觉按照图是不好做的，我们考虑这个序列是有特殊性质的，所以我们考虑按照序列做。 最终序列是固定的，考虑对于最终序列进行 $\tt Dp$，我们会需要记录最终序列，我们发现如果加入一个点的时候我们只需要知道当前序列的最近两个位置即可，不妨假设其为 $(u, v)$。 对于加入的点 $x$，我们肯定有 $u \le a_x + x < v$。 其次对于 $y \in [x + 1, u - 1]$，我们需要保证这些点是不能到达 $u$ 的所以需要删除贡献。 那么设 $f(u, v)$ 表示最后两个元素为 $u, v$，考虑转移到新的点 $v’$ 方程： $$f(u, v) = \min_{k = 1} ^ {u - 1} (f(k, u) + \sum_{p = k + 1} ^ {u - 1} [a_p + p\ge u])$$ 这个东西是 $O(n^3)$ 的。 我们考虑枚举 $u$ 之后，需要考虑剩下的条件也就是 $u \le a_k + k < v$，我们可以离线存下来，之后开桶按照 ...

模拟赛——lengendgod专场 题目名称 联合权值 乘积最大 点 马 题目类型 传统题 传统题 传统题 传统题 可执行文件名 link cjzd point horses 输入文件名 link.in cjzd.in point.in horses.in 输出文件名 link.out cjzd.out point.out horses.out 每个测试点时限 1s 1s 1s 1s 运行内存上限 512MB 512MB 512MB 512MB 编译命令： C++ -Wl,–stack=1073741824 -O2 -std=c++14 其它语言 rm -r -f 注意事项： 考试时间4个小时。 文件名（程序名和输入输出文件名）必须使用英文小写。 C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 若无特殊说明，结果比较方式为忽略行末空格、文末回车后的全文比较。 选手应将各题的源程序放在选手文件夹内，不要建立子文件夹。 隆重感谢 $\tt legendgod$ 对本场 ...

Problem - 1437F - Codeforces 题目比较弱智，但是我更加弱智。 首先考虑排序之后肯定是没有关系的，从小到大进行插入。 考虑插入了 $i$ 位置之后的结果 $f_i$，我们发现如果需要插入必须找到一个位置 $j$ 使得 $2a_j \le a_i$，当然对于 $\forall k \le j$ 都是可以进行转移的。 我们考虑位置 $j$ 前面满足 $2a_k \le a_j$ 的最大位置 $x_j$，那么经过 $j$ 的插入之后总共有 $x_j + 1$ 个元素。同理对于 $i$ 来说序列的长度是固定的就是 $x_i +1$。 考虑插入到了位置 $j$，也就是通过 $f_j$ 进行转移，对于只受 $i$ 影响的数我们肯定可以在 $i$ 之后任意排列，数的个数总共有 $x_i - x_j - 1$。 $j$ 也是需要算进去的。 对于位置 $i$ 可以考虑还有几个位置可以放置，显然有 $n - 1 - 1 - x_j$。 减去 $i, j, x_j$。 所以方案数就是 $A_{n - 2 - x_j}^{x_i - x_j - 1} = \df ...

整除分块就是一种可以将相同值一起计算，使得带有取上整或者取下整的式子可以在 $O(\sqrt n)$ 内计算。 我们考虑一种比较简单的式子： $$\sum_{i = 1}^ n \lfloor \frac{n}{i}\rfloor$$ 直接进行打表可以发现有一些部分是相同的，我们考虑一起计算。 不妨考虑 $\left \lfloor\dfrac{n}{i} \right\rfloor = k, n = ki + r$。 考虑会带得到 $\dfrac{n - r}{k} = i$，考虑 $r \in (0, i)$，而且我们有 $\left \lfloor\dfrac{n}{i} \right\rfloor = k$。 所以我考虑如果想要让 $i$ 最大，我们必须满足 $r = 0$，所以我们有 $max(i) = \left \lfloor \dfrac{n}{\dfrac{n}{i}} \right\rfloor$。 我们仔细思考复杂度，每次让 $\lfloor\dfrac{n}{i}\rfloor$ 不同的 ...

Codeforces - 830D 考虑这个东西可以做到 $O(k^3)$，要么是一个矩阵的形式，要么是二维状态的 $\tt Dp$。 感觉矩阵一下子想不出来有什么前途，考虑对于每个点，其儿子本质上就是子问题，我们考虑设答案为 $f_n$。 考虑转移的时候要么是直接从儿子中转移，要么是考虑儿子的一条路径经过自己得到的，注意两条路径如果要合并的时候是不能有重复节点的。 如果一个节点的祖先是自己，那么就存在连边，所以任意一条路径总是可以通过根节点的，我们考虑转移的时候需要通过若干条不相交的路径进行计算，所以设状态为 $f(n, k)$ 表示根节点为 $n$ 选择了 $k$ 条不相交路径的方案。 转移的时候考虑根节点自己作为一条路径。 两条路径不算根节点。 根节点和某条链相连接，可以连接头或者，也就是是否通过返租边。 根节点合并两条链，总共有 $K + 1$ 条链，选择两条即可，也就是钦定一条头和尾。 $$\begin{aligned}f(n, K) &= \sum_{i + j = K - 1} f(n - 1, i) \times f(n - 1, ...

$\tt bitset$ 是一个比较神奇的东西，我感觉经常用来卡常数，毕竟这个东西有 $\frac{1}{w}$ 的常数。 事实证明，如果写埃氏筛用 $\tt bitset$ 比欧拉筛要快。 定义：就是一个存了 $0/1$ 串的东西，每个位占用一个 $B$。 可以使用 unsigned long long 或者 string 进行初始化，默认值为全 $0$。 $\color{red}\text{pay attention ! }$string 最右边的那一位是被放在 bitset 的位置 $0$ 的，数字同理。 123bitset<maxn> vis;//000...000bitset<maxn> vis1(5);// 000...00101bitset<maxn> vis2("100101"); // 000...100101 $\tt Bitset$ 函数 flip() 全部取反。 filp(x) 取反下标为 $x$ 的位置。 size() 返回位数（大小）。 count() 返回 $1$ 的个数。 ...

[IOI2015]teams分组 - 题目 - 黑暗爆炸OJ 考虑对于一个点 $i$ 的区间 $[l_i, r_i]$ 不妨假设按照 $l_i$ 从小到大排列，如果一个点 $i$ 是可以取到的情况，我们可以发现对于所有可以取到的肯定是选 $r_i$ 最小的进行取走。 我们考虑对于每个询问从小到大来做，考虑将每个 $[l_i, r_i]$ 对应到二维平面的 $(x, y)$ 上，对于每个询问记录在这次询问之后没有被取走的 $y$ 的最小值，设其为 $h_i$。 那么对于一个 $k_x$ 如果 $h_i < k_x$ 显然是可以直接取的，如果出现 $h_i > k_x$ 我们需要考虑其剩下没有取的元素，这个东西可以通过单调栈来维护。 之后对于平面上二维数点，直接使用可持久化线段树即可。 考虑加入一个元素的情况，直接在线段树二分位置即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656 ...