赵嘉熠的博客

题目链接（计蒜客）

题目大意

给出有\(n\)个元素的序列\(a\)，现在将序列分成若干连续的段，每个段的不同元素种类数不能超过\(k\)。对于\(1\le k \le n\)的每一个正整数\(k\)，计算最少划分成多少段。

\(1\le n \le 10^5,~1 \le a_i \le n\)

……

今天16岁了！！！

题目链接（正睿）

题目大意

给定含有\(n\)个元素的数组\(a\)，现在要选择两个相邻的元素\((i,j)\)删除，那么代价为\(cost(i,j)\)（给出）。

用\(\frac{n}{2}\)轮将所有元素删完，问代价最少是多少。\(n\le 4000\)

随笔一篇

题目链接（正睿）

题目大意

有\(2^n\)个人玩剪掉石头布，每次第\(1\)个人和第\(2\)个，第\(3\)个和第\(4\)个……会决出谁是胜者，然后晋级下一轮变成第\(1,2,3...\)个人。经过\(n\)轮后最后会决出一个胜者。

这\(2^n\)个人每次出拳都固定，其中有\(r\)个石头，\(p\)个布，\(s\)个剪刀。给出一组出拳方案，用R来表示石头，P来表示布，S来表示剪刀。使得任意一轮比赛都不存在出拳相同的人，且字典序最小。

\(n\le 15\)

题目链接（洛谷）

题目大意

在数轴上有\(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\)

题目链接（洛谷） ## 题目大意

给定常数\(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\)

题目链接（洛谷）

题目大意

有\(n(n\le 10000)\)种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是购买，每次只能买一张，并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的，概率均为\(\frac{1}{n}\)。购买第\(k\)次邮票需要支付\(k\)元钱。

求得到所有种类的邮票需要花费的钱数目的期望。

题目链接（洛谷）

题目大意

给定一个长度不超过\(105\)的字符串（小写英文字母），和不超过 \(50000\)个操作。

每个操作\(L,R,K\)表示给区间\([L,R]\)的字符串排序，\(K=1\)为升序， \(K=0\)为降序。

最后输出最终的字符串。