DE_aemmprty

摘要： \(\mathbf{Part. -1}\) 翻译自 ROI 2023 D1T3。 如果对于所有 \(1 \le j < i\)，都有 \(a_j < a_i\)，则称 \(a_i\) 为峰值。 如果对于所有 \(1 \le j < i\)，都有 \(a_j > a_i\)，则称 \(a_i\) 为反 阅读全文

摘要： FFT 准备自己写一个高精度的板子，但是不会 FFT 于是学一学 QaQ 。窝还是太菜了，这都不会 。 明确问题 首先，来明确一下我们需要解决的问题：给定一个 \(n\) 次多项式 \(F(x)\)，和一个 \(m\) 次多项式 \(G(x)\)。请求出 \(F(x)\) 和 \(G(x)\) 的卷 阅读全文

摘要： FFT 学习笔记 \(\mathbf{Preview}\) 前置知识。 多项式表示法 系数表示法：就是正常的多项式表示方法。\(f(x) = \sum\limits_{i = 0}^{n - 1} a_i \times x^i\)。 点值表示法：如果我们知道 \(n\) 个数 \(b_1, \cdo 阅读全文

摘要： \(\mathbf{Part.-1}\) 给定一个由字符 A 和 B 组成的字符串 \(S\) 。 在这根绳子上，您可以反复执行以下操作： 在字符串 \(S\) 中选择三个连续且相等的字符，这些字符要么是 AAB 要么是 BAA，然后将这三个字符从 \(S\) 中删除（删除后，剩余的字符会连接在一起 阅读全文

摘要： 8.1 T1 \(n = 40\)，考虑 meet in the middle，分成两个大小为 \(\dfrac{n}{2}\) 的集合 \(A, B\)，内部是好判断的，考虑如何合并。我们发现固定集合 \(A\) 后相当于在 \(B\) 中钦定一些 \(0, 1\)，剩下位任选，但只能做到 \(\ 阅读全文

摘要： 对于一些操作类的计数问题，可以考虑操作到无法操作之后对不满足条件的剩余情况进行计数。 遇到不会的计数或不会优化的 dp，可以考虑容斥。 容斥复杂度太高时，可以考虑将情况划分为等价类。 对于树的 constructive，考虑从叶子开始。 \(\dbinom{n}{\lfloor \frac{n}{2 阅读全文

摘要： \(\mathbf{Part. -1}\) 这是一道交互题。 hehe 蚤决定花费几天时间，游览下山市的最著名的旅游景点 —— 吓山。 吓山，以高低纵横，崔巍秀丽，错综复杂的地形闻名。据说无论用什么地图导航，都不能保障你在山中不迷路。 之所以会出现这样的情况，是因为吓山中的路，在没有光的时候都会发生 阅读全文

摘要： \(\mathbf{Part. -1}\) 这是一个交互题。 Ayush 又想出了一个设置密码的新方法。他的锁有 \(n\) 个槽位，每个槽位可以放置任意非负整数。密码 \(P\) 是一个长度为 \(n\) 的整数序列，第 \(i\) 个元素将放入锁的第 \(i\) 个槽位。 为了设置密码，Ayus 阅读全文

摘要： \(\mathbf{Part. -1}\) 有 \(2^N\) 个人，按照满二叉树的形态进行淘汰赛，一开始的排列顺序为所有 \((2^N)!\) 个排列之一。 你是第 \(1\) 个人，已知每一对人之间的实力关系，具体地说： 给出 \(M\) 个人 \(A_1 \sim A_M\)。 这 \(M\) 阅读全文

摘要： \(\mathbf{Part. 0}\) 第一步似乎没有特别显然的直接转换，于是考虑观察和熟悉正方形棋盘的结构。 如图，我们大致可以把原图划分成这样的结构。显然，整个图大致呈显出一颗树的形态，这棵树我们一般称之为 广义笛卡尔树，每行都是完整的一行，每列都被划分为若干个区间。除此之外没有什么特别的性质 阅读全文