dyc2022's Blog

摘要： 更差的阅读体验 什么题哦。 称一个日期被安排电影，为这个日期被“选择”。 首先考虑对于单个 \(S\) 如何求 \(f(S)\)。那么有一个较为显然的贪心： 按照右端点从小到大的顺序枚举区间。如果该区间内部还有未被选择的位置，那么就找到最靠左的未被选择的位置，将这个位置选择；否则无事发生。 那么我们 阅读全文

摘要： 更差的阅读体验 我认为这个贪心策略并不显然。这篇题解的大部分篇幅都是证明。 在代码之前有太长不看版的本题结论。 既然题目要求在邻项交换的过程中序列的 LIS 长度保持不变，因此我们直接观察 LIS 在交换过程中的变化。 假设 \(f_i\) 表示以 \(i\) 开始的最长上升子序列的长度，同时记原序 阅读全文

摘要： 更差的阅读体验 到底是谁在出这种题？太魔怔了。 以下不妨设值域 \(2^m = O(n)\)。 假设数字 \(i\) 的出现次数为 \(c_i\)。\(x = 0\) 的时候显然答案是 \(\sum \left \lfloor \frac{c_i}{2}\right \rfloor\)，先提前特判掉 阅读全文

摘要： 更差的阅读体验 数论题好难。把官解复读一遍，只是把官解写得比较简略的地方说清楚了一点。 首先我们进行如下约定： 记 \(f(x) = \prod \limits_{i=0}^{n-1} \left(bx + di + c\right)\)。 记 \(G = \gcd \limits_{i=0}^n 阅读全文

摘要： 更差的阅读体验 非常具有教育意义的一个数数题！ 将区间 \([l, r]\) 赋值为 \(\frac{r(r-1)}{2} + l\) 这个操作，实际就是将每个区间 \([l, r]\) 映射成一个数字，且所有区间所代表的数字互不相同。 那么我们需要解决这样个问题：有一个二元组序列 \(a\)，初始 阅读全文

摘要： 更差的阅读体验 ？？？？？？？？？被打的措手不及。 我们需要解决这样一个问题：构造一个 \(4 \times w\) 的 01 矩阵，使得对于 \(\forall n \isin [0, 999900]\)，都存在这个矩阵的一个欧拉路径，使得路径上经过的数字组成的序列，逆序对数恰好为 \(n\)。对 阅读全文

摘要： 更差的阅读体验 这应是我第一次独立做出黑题！这应该是一个思路和实现都比其他题解简单的做法。 我们需要解决这样一个问题：给一个左右各 \(n\) 个点的完全二分图上的 \(n^2\) 条边分别确定边权，使最长上升路径的长度恰好为 \(k\)，或报告无解。 首先如果见过 arc220d 的 trick 阅读全文

摘要： 更差的阅读体验 这题太好了，arc 的题目就该这样！ 我们需要解决这样一个问题：在一个 \(n\) 点无向完全图上，找到一条边不重的路径 \(v_1 \rightsquigarrow v_k\)，使对于任意 \(i\) 有 \(|v_{i+2} - v_i| = 1\) 且 \(k \ge \fra 阅读全文

摘要： 更差的阅读体验 我们需要解决这样一个问题：找到最小的，连续 \(n\) 个 \(\bmod \space c\) 同余的数字，使这些数字的 popcount 都 \(\ge k\)。 那么可以二分。假设目前位于区间 \([l, r)\)，区间的中点是 \(mid\)。那么， 若区间 \([l, mi 阅读全文

摘要： 更差的阅读体验 打模拟赛打到的，实在是神题阿。 出于一些惯例，我们假设读入的两个字符串分别是 \(S\) 和 \(T\)。那么经过观察，我们能够发现，一定存在一种最优方案，使所有操作 1 在所有操作 2 的后面。 假设存在一种 1 在 2 前面的操作序列，比如先令 \(S_k = x\)，然后将所有 阅读全文