hdu2019多校2

发表于 2019-12-27 分类于 hdu ，多校

有一序列 $A$ ，$h(A)$ 表示 $A$ 的逆序对个数，设函数 $g(A)=g(B)+h(A)$，其中 $B$ 为 $A$ 的 $2^n$ 种子序列中等概率选取的一个子序列。

设 $f(n)$ 表示任意选取长度为 $n$ 的排列 $P$，$g(P)$ 的期望。

对于 $i\in[1,n]$ ，求 $f(i)$

$n\leq 3000$

考虑一个长度为 $n$ 的排列，由期望的线性性，可知长度为 $n$ 的排列的逆序对个数 $w(n)$=每对 $(i,j)$ 组成逆序对的期望之和，即 $w(n)=\frac{\binom{n}{2}}{2}$。

因此有：

$$f(i)=\frac{1}{2^i}\sum_{j=0}^{i}\binom{i}{j}f(j)+w(i)$$

将 $f(i)$ 从和式提出，移项得：

$f(i)=\frac{1}{2^i-1}\sum_{j=0}^{i-1}\binom{i}{j}f(j)+\frac{2^i}{2^i-1}w(i)$

$O(n^2)$ 求出 $f(n)$ 。

给一字符串 $s$，$\forall i\in[1,|S|]$，求有多少个长度为 $i$ 的子串满足它是回文串且该子串的前一半也是回文串。

$|S|\leq 3\times 10^5,\sum|S|\leq 4\times 10^6$

建出PAM，然后沿着 fail 边 dfs。

签到题，输出 $n!$ 。

给一个序列 $a$ ，多次询问区间 $[l_i,r_i]$ 中是否存在三个下标不同的数组成三角形。

$n,m\leq 10^5,a_i\leq10^9$

首先判断一序列能否形成三角形的方法是把序列排序，然后相邻三个判断。

不能形成三角形的最坏情况是斐波那契数列，$f_{44}$ 左右的时候就大于 $10^9$ 了。

因此一个序列长度 $>45$ 就必能形成三角形。

剩下的暴力即可。

给一个序列 $a$，代表颜色，范围是 $[1,C]$求是否存在一个区间使得在此区间内出现过的每种颜色的出现次数大于等于 $k$。

$n,C,k\leq 10^5$

每种颜色分开来考虑：对于每种颜色，假设固定了左端点，那么右端点的合法范围为两段区间。

随着左端点向左移动，这些区间可以比较容易的维护。

那么对每种颜色的合法区间+1，求最大值是否为 $C$ 即可。

这是操作可以很方便的用线段树实现。