文章

另一种阅读体验 时间复杂度 时间复杂度用于描述算法的运算量随输入规模增长的增长情况，进而可以用于估计算法在某一输入下的运算次数，并据此评判出算法效率的优劣。 函数的增长规模 记 $f(n)=n^3,g(n)=n^3+10n^2+100n$， 可以得到 $f(10000)=1000000000000, 阅读更多…

考虑一个合法序列的生成过程：依次考虑 $i:[1,n]$，将 $i$ 插入序列中。因此，我们考虑如下生成方式：依次考虑 $i:[1,n]$，再考虑一个未被加入的位置集合的子集 $T$，将 $T$ 从大到小排序插入到序列 $q$ 末尾。 我们钦定 $q$ 满足如下要求：对于 $i$ 选中的 $T$ 和 阅读更多…

另一种阅读体验 字符串哈希 Trie 树 在计算机科学中，trie 树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。 与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。 一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符 阅读更多…

突然发现 WC2021 到现在还没做 .. 考虑我们要求的应该是最小的 $i$ 使得满足 $f_{i-1}a\equiv f_{i}b\pmod {p}$ 。 即满足 $p|f_{i-1}a-f_ib$，因此 $\frac{p}{\gcd(p,a,b)}|f_{i-1}\frac{a}{\gcd(p 阅读更多…

同步发表于 博客园 题目大意 给出一个二进制数 $R$，在 $[0, R-1]$ 中选 $n$ 个互不相同数，问异或和为 $0$ 的方案数。 $|R|\le 10^6,n\le 7$. 解题思路 因为限制 $n$ 个数互不相同难以实现，所以考虑允许相同怎么求方案数，然后容斥做。 记可以相同的 $n$ 阅读更多…

同步发表于 博客园 基础知识 卡特兰数的式子 $$ \begin{aligned} &h(n)=\sum_{i=0}^{n-1}h(i)\cdot h(n-i-1)\\ &h(n)=\frac{h(n-1)\cdot(4n-2)}{n+1}\\ &am 阅读更多…

前置： 1. 目前没有进行代码实现，所有内容均是口胡，如有错误或者不严谨的地方烦请指出，谢谢！ 2. 由于这篇文章中会同时出现 “线段树上的节点”，“树上的结点” 等多种点，为便于理解，维护连续段的线段树的点统称 “节点”，树的点统称 “结点”。 3. 线段树上的节点对应/表示的区间指线段树函数参数 阅读更多…

在以前的文件里翻了翻，找到了许久之前写的两篇游记。那时的文笔还是太稚嫩了，思想也有点偏激。但是不得不说，那段时间在外地比赛的经历使我的世界观受到了巨大的冲击，开始意识到自己身处的世界存在的不合理。也许这就是所谓的成长。从那时起我开始发觉自己学习的不止是一个个没有色彩的算法和数据结构，眼中的世界渐渐鲜 阅读更多…

题意 给定一棵 n 个节点的树，每个点有点权，让你找一个最大的联通块满足块内权值和不大于 m。 n,m, 点权不大于 1e5，点权互不相同。 解 点权互不相同，且点权和不大于 m，所以显然联通块的大小不会超过 $\sqrt{m}$。 令 $dp_{i,j}$表示以 i 节点为根的大小为 j 的联通块 阅读更多…

传送门 结论：当 $\binom{n}{a_1,a_2,…,a_k}$是奇数并且 $n$是偶数的时候 Alice 必败 首先我们来证明这个结论 首先当你有 $n$个字母的时候（假设上一轮还有 $n+1$个字母），那么你有两种方案，如果删掉一个字母可以让对手进入必败态，就直接删；否则如果 阅读更多…