最寻常或小意外,都欣喜去相爱
每个集合用一棵树表示，用根节点的编号表示整个集合的编号，开一个数组 \(p[x]\) ，表示编号为 \(x\) 的元素的父节点编号
while(p[x] != x) x = p[x]p[px]=py这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ，这就是路径压缩。——OI-Wiki
给定一个 n 面的骰子，每个面出现的概率相同，现在要所有的面都至少出现一次，求投掷次数的期望。
设 \(f[i]\) 表示投出 \(i\) 个面需要投掷的期望次数，投掷出现 \(i\) 个面后，当前的一次投掷，可能是投出的面原先投出过，这种情况有 \(\frac{i}{n}\) 的概率，也可能是当前投出的面未出现过，这种情况有 \(\frac{n - i}{n}\) 的概率。
对于已经投掷出 \(i\) 个面后的状态，此时的投掷，实际上是一个伯努利实验，事件即为是否投出新的一面。因此，根据几何分布的公式 \(E[X]=\frac 1 p\) ，易得投出新的一面的期望是 \(\frac n {n-i}\) ，因而可以得出 \[ f[i] = f[i - 1] + \frac n {n-i} \]
有一组数，你要把他分成若干连续段。每一段的值，定义为这一段 数中最大值与最小值的差。 求一种分法，使得这若干段的值的和最大。 \(n < 1e6, a_i < 1e9\)
在播放器的边缘，可以通过鼠标拉伸整个播放器窗口，大小随心
利用数据库的主键功能，实现了开发文档中所说的选座要求——歌单编号不得重复。
实现了开发文档中所说的选座要求——可以形成歌曲的上一首，下一首播放以及循环播放功能。
具备常规播放器具有的前进一首，后退一首，暂停，拖动进度条，调整音量的功能，并支持循环、单曲循环、随机播放的三种播放模式。
在搜索框输入内容后，会在下方显示搜索结果，包含两个信息，1）一共搜索到相关歌曲的数量，2）相关歌曲。点击歌曲名称的一行可以直接播放歌曲
在”我的歌单“右侧有一个加号的按钮，点击后会弹出添加歌单的对话框，其中歌单是必填项，简介为选填项，若无简介，歌单详情页也不会显示简介相关标签，同时会给歌单添加一张默认图片，添加完后自动加载新建的歌单。
点击歌单列表中的歌单名称，右侧详情页即会加载该歌单的相关信息。
AC自动机是基于Trie树的数据结构利用KMP的思想进行多模式匹配的算法。
具体而言，建立一个AC自动机只需要完成两件事
粗略地理解，就是把本来要和原串匹配的一堆模式串合成一棵树，让原串和一棵树去匹配，来获得平均线性的复杂度。
求出每个模式串在原串出现的次数。
对于字符串\(S\)，先复制一遍接在\(S\)尾部，然后再在任意位置插入一个字符，给定构造好的字符串\(T\)，求原字符串\(S\)。
首先设\(T\)长度为\(n\)，如果\(n\)为偶数，那么必然不存在原串，因为一个字符串长度乘二加一必然是奇数，然后，可以知道原串的长度一定是\(\frac n 2\)。
根据这两个结论，我们可以直接枚举每个位置是否是插入的字符，通过哈希去验证去除该字符后剩下的是否是两个完全相同的串，枚举复杂度为\(O(n)\)，验证复杂度为\(O(1)\)，总体复杂度为\(O(n)\)，符合题目要求。
给定一个字符串\(s\)，执行\(m\)次询问，每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为：如果\(s\)中的字符可以被替换得到\(t\)，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
给定一个长度为\(n\)的字符串\(s\)（下标从\(1\)开始），约定\(s[l,r]\)表示从\(s[l]\)开始到\(s[r]\)结束的字符串，\(s\)的 前缀函数 被定义为一个长度为\(n\)的数组\(\pi\)。其中\(\pi[i]\)为既是字符串\(s[1,i]\)的前缀同时也是该字符串的后缀的 最长 真前缀字符串（真前缀字符串指不为这个字符串本身的前缀字符串）长度。
换言之，\(\pi[i]\)只关心字符串\(s[1,i]\)，且若\(\pi[i]=j\)，则有字符串\(s[1,j]=s[i-j+1,i]\)。抽象的数学定义即为：\(π(i)=max\{j|s[1,j]=s[i−j+1,i], j≤i\}\)
根据定义可以得出两个结论来帮助我们快速求解\(\pi\)函数。
warma付钱的决策是多重背包模型，收银员找零是完全背包模型，先预处理，然后从w开始枚举S，求min即可
多重背包不开二进制优化应该会挂，开了优化可能没有推出结论也可以水过去
骗分大法直接输出-1
本题改编自USACO-The Fewest Coins，仅扩大了部分数据范围
除夕之夜，warma唱完鼠来宝之后从国正中心出来，在寒风中瑟瑟发抖，于是乎决定去金拱门奢侈一把。
吃饭全靠赚赏（sang）钱的warma兜里只有硬币，为了快点吃上饭，她想让硬币转手的次数尽可能最少，即付出去的硬币数与找零得到的硬币数之和（S）最小。
市面上流通的硬币共有n（1<=N<=10000）种，面值分别为 \(v_1,v_2,...,v_n\) （ \(1<=V_i<=120\) )。对于面值为 \(v_i\) 的硬币，warma分别有 \(c_i\) 个（ \(0<=c_i<=10000\) ）。同时，出于囊中羞涩，warma只打算购买总价值为 \(w\) （1<=w<=10000）的食物和（谢拉）小伙伴们分享。
特别要注意的是，金拱门是国际品牌，各种硬币都很充足，可以满足任意的找零方案。收银员小姐姐也很善解人意，听到warma的要求后，决定用最少的硬币为warma找零
作为只会吹灭火器的音乐（le）人，warma找到了经验丰富的你（你也要过饭？），希望你能帮她算出付出去的硬币数与找零得到的硬币数之和（S）最小是多少。