【题解】蒜头君的项链
题目大意
给出有\(n\)个元素的序列\(a\)，现在将序列分成若干连续的段，每个段的不同元素种类数不能超过\(k\)。对于\(1\le k \le n\)的每一个正整数\(k\)，计算最少划分成多少段。
\(1\le n \le 10^5,~1 \le a_i \le n\)
【随笔】2021.10.2
今天16岁了！！！
【题解】2021提高组十连测day4 n^3过一万
题目大意
给定含有\(n\)个元素的数组\(a\)，现在要选择两个相邻的元素\((i,j)\)删除，那么代价为\(cost(i,j)\)（给出）。
用\(\frac{n}{2}\)轮将所有元素删完，问代价最少是多少。\(n\le 4000\)
【随笔】2021.9.21
随笔一篇
【题解】ZROI 2021提高组十连测day2 比赛
题目大意
有\(2^n\)个人玩剪掉石头布，每次第\(1\)个人和第\(2\)个，第\(3\)个和第\(4\)个……会决出谁是胜者，然后晋级下一轮变成第\(1,2,3...\)个人。经过\(n\)轮后最后会决出一个胜者。
这\(2^n\)个人每次出拳都固定，其中有\(r\)个石头，\(p\)个布，\(s\)个剪刀。给出一组出拳方案，用R来表示石头，P来表示布，S来表示剪刀。使得任意一轮比赛都不存在出拳相同的人，且字典序最小。
\(n\le 15\)
【题解】P1712 [NOI2016] 区间
题目大意
在数轴上有\(n\)个闭区间从\(1\)至\(n\)编号，第\(i\)个闭区间为\([l_i,r_i]\)。现在要从中选出\(m\)个区间，使得这\(m\)个区间共同包含至少一个位置。换句话说，就是使得存在一个\(x\)，对于每个被选中的区间\([l_i,r_i]\)，都有\(l_i \le x \le r_i\)。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。
区间 \([l_i,r_i ]\)的长度定义为\((r_i-l_i)\)，即等于它的右端点的值减去左端点的值。求所有合法方案中最小的花费。如果不存在合法的方案，输出\(−1\)。
\(1 \le m \le n,~1 \le n \le 5 \times 10^5,~1 \le m \le 2\times 10^5,~0\le l_i \le r_i \le 10^9\)
【题解】P7322 「PMOI-4」排列变换
题目链接（洛谷） ## 题目大意
给定常数\(k\)。对于一个长度为\(n\)的排列\(a\)，定义
$ f(a)={{1 i k} {a_i},{2 i k+1} {a_i},,_{n-k+1 i n} {a_i}} $
对于一个长度为\(n\)的序列\(a\)，定义其权值\(w(a)\)为\(a\)中不同的数的个数。
求对于长度为\(n\)的排列\(p\)，它们的\(w(f(p))\)之和。
\(1\le k \le n \le 5\times 10^5\)
【题解】P4550 收集邮票
题目大意
有\(n(n\le 10000)\)种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是购买，每次只能买一张，并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的，概率均为\(\frac{1}{n}\)。购买第\(k\)次邮票需要支付\(k\)元钱。
求得到所有种类的邮票需要花费的钱数目的期望。