dyc2022's Blog

摘要： 更差的阅读体验 模拟赛搬了这个，完全不会，不理解为什么那么多人过。 唉小朋友来打不断网的模拟赛就是这样的。 读入的字符串为 \(S\)，则我们将满足条件的括号串分为两类：是 \(S\) 的前缀的字符串，以及非 \(S\) 的前缀的字符串。 对于前者，直接枚举 \(S\) 的每个前缀，判断该前缀是否为 阅读全文

摘要： 更差的阅读体验 qoj 7，非常困难！ 首先我们考虑以位置为 \(x\) 轴，时间为 \(y\) 轴建立一个二维平面。由于每个 bot 的运行速度都是 \(1\) 单位每秒，因此可以看作是若干条斜率为 \(\pm 1\) 的直线。由于老鼠的速度 \(\le 1\) 单位每秒，因此老鼠只能往右上方 \ 阅读全文

摘要： 更差的阅读体验 Lyndon Word 与 Lyndon 分解 \(\text{Lyndon}\) 串：称一个字符串 \(s\) 为 \(\text{Lyndon}\) 串，当且仅当 \(s\) 的字典序严格小于 \(s\) 的所有真后缀。这个定义同样可以描述为，\(s\) 的字典序严格小于 \(s 阅读全文

摘要： 更差的阅读体验 某一天调这道题调到了 0:22，特此记录。 首先考虑静态情形，也就是没有 \(a_i\) 被修改的情况。 那么这个问题就是 [PA 2014] Druzyny 的弱化版，可以用类似地方法解决。具体地，我们假设 \(f_i\) 表示将 \([1, i]\) 分段地方案数，有转移 \[f 阅读全文

摘要： 更差的阅读体验 这题，真厉害。这题可能可以帮助你发现，你并没有学懂 manacher 算法。 首先，我们回顾一下 manacher 算法的流程（仅考虑求奇回文串）： 记 \(d_i\) 为以 \(i\) 为中心的最大回文半径。 从左往右枚举回文中心 \(i\)，同时维护区间 \([l, r]\) 表 阅读全文

摘要： 更好的阅读体验 感觉是很考验功底的组合计数题，可以说让人眼前一亮。 线性做法还没学。 我们先考虑对于一个排列 \(p\)，如何求出 \(f(p)\) 的值。 对于一个位置 \(i\)，我们只考虑 \(p_j < p_i\) 的位置和 \(p_i\) 产生的逆序对数量。 若我们给 \(p_i\) 乘的 阅读全文

摘要： 更差的阅读体验 什么题哦。 称一个日期被安排电影，为这个日期被“选择”。 首先考虑对于单个 \(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 阅读全文