A 组题
给定一个长度为 $n$ 的有正有负的数字序列，求长度 $\geq k$ 的子串平均值的最大值，输出最简分数。
$n\leq10^5$
签到题，NOIP 老套路。
二分答案，对于一个平均值通过前缀和判断是否存在符合条件的子串，并且记录分子分母。
1 |
|
##B 摘苹果
给订一张 $n$ 个点 $m$ 条边的无向图和一个正整数数列 $a$，设点 $i$ 的度数为 $d_i$，初始时随机移动到一个点上，移动到第 $i$ 个点的概率为 $$\frac{d_i}{2m}$$ . 之后还要移动 $k$ 次，每次随机选择一条与当前点连接的一条道路，移动到另一点 $i$ 上，得到 $a_i$ 的权值（多次移动到同一点上可重复得到权值）。求得到权值的期望。
$n\leq10^5,m\leq2\times10^5$
考虑第一次移动（不是初始时）到某一点的概率，某一点 $j$ 可以由所有与其联通的所有点 $i$ 到达，而初始时在点 $i$ 的概率为 $$\frac{d_i}{2m}$$ ，而本次从 $i$ 移动到 $j$ 的概率为 $\frac{1}{2m}$ ，而对于点 $j$ 来说，所有与其联通的 $d_j$ 个点都有 $\frac{1}{2m}$ 的概率到达。综上所述，第一次移动到点 $j$ 的概率为 $$\frac{d_j}{2m}$$ 。
我们发现其实每次移动在某一点上的概率并没有变化，那么答案就是 $$k\sum_{i=1}^na_i\frac{d_i}{2m}$$
1 |
|
C 分割序列
对于一长度为 $L$ 的非负整数序列 $(a_1,a_2,\dots,a_L)$ ：设 $S[l,r]$ 为 $a_l\oplus a_{l+1}\oplus\dots\oplus a_r$，定义序列的能量为 $\max\limits_{i=0}^nS[1,i]+S[i+1,L]$ .
现在给定一长度为 $n$ 的非负整数序列 $(a_1,a_2,\dots,a_n)$ ，求其每个前缀的能量。
$n\leq2\times10^5,a_i\leq10^6$
这种异或的题目一般都是按位分别处理。
先将能量值的定义转化一下：设 $s_i$ 为前缀异或和，则所谓的能量值为 $\max\limits_{i=0}^ns_i+s_i\oplus s_L$
注意到这样一个规律，对于第 $k$ 位：
- 如果 $\Large s_{L_k}$$=0$ , 那么当且仅当 $\Large s_{i_k}$$=1$ 时答案最大；
- 如果 $\Large s_{L_k}$$=0$ , 那么 $\Large s_{i_k}$ 的值对答案没有影响。
所以我们求 $a$ 的每一个前缀能量时可以从高位到低位动态规划，设 $f_S$ 为满足 $S\in s_i$ 的 $i$ 的最小值，那么对一个前缀 $x$ 的某一位决策时只要满足 $f_S\leq x$ 就可以取这一位，然后就得到了一个对于这一前缀最优的 $s_i$ ，那么这一前缀的能量就得到了。
现在问题变成了如何求 $f$ ，其实只要对于原序列进行预处理即可。
1 |
|
##D 图的价值
给定 $n,k$ , 求所有 $n$ 个点的带标号的简单无向图的价值之和。答案 $998244353$ 取模。
$n\leq10^9,k\leq2\times10^5$
显然每个点对答案的贡献相同，可以计算出 $1$ 号点的贡献然后 $\times n$ . 枚举 $1$ 号点的度数 $d$ , 则要从 $n-1$ 个点中选 $d$ 个点与它连边，并且剩下 $n-1$ 个点可以随意连边。
答案就是
$$
n2^{(n-1)(n-2)/2}\sum_{i=0}^{n-1}\binom{n-1}{i}i^k
$$
式子不难列出，问题就在于这种恐怖的数据范围下解决幂指数求和问题，一般的求法肯定不行了，我们需要继续往下推公式。
注意到这个式子与一般的幂指数求和不同，系数上有了组合数，那通常的 Bernoulli 数 求和公式就不在适用了。
不过还是有一种类似的解法，提起系数上有组合数的自然数幂指数求和，想到还有个 第二类斯特林数 。关于这个数列详见 《组合数学及其应用》读书笔记 。 $S_2$ 的定义式为 $$x^k=\sum_{i=1}^ki!\binom{x}{i}S_2(k,i)$$
那么可以用这个公式化简答案：$$n2^{(n-1)(n-2)/2}\sum_{i=0}^{n-1}\binom{n-1}{i}\sum_{j=1}^kj!\binom{i}{j}S_2(k,j)$$
交换求和顺序得： $$n2^{(n-1)(n-2)/2}\sum_{j=1}^kj!S_2(k,j)\sum_{i=0}^{n-1}\binom{n-1}{i}\binom{i}{j}$$
发现最右边的两个组合数和式变成了喜闻乐见的形式，考虑其组合意义：先选择一个集合 $A$ 的子集 $B$ ，在从 集合 $B$ 中选一个子集 $C$ 的方案数；其实也就等于：从集合 $A$ 中选出集合 $C$ ，$\complement_AC$ 中的元素自由选择是否在集合 $B$ 中的方案数。转化为公式就是：$$\sum_{i=0}^{n-1}\binom{n-1}{i}\binom{i}{j}=2^{n-1-j}\binom{n-1}{j}$$
那么原式就可以化简为：
$$
n2^{(n-1)(n-2)/2}\sum_{j=1}^kj!2^{n-1-j}\binom{n-1}{j}S_2(k,j)
$$
然后各种预处理，其中 $S_2$ 可以通过卷积形式用 NTT 求出，就可以做到 $O(k\log_2k)$ 的复杂度了。
附：$$S_2(x,y)=\sum_{i=0}^b\frac{(-1)^i}{i!}\cdot\frac{(b-i)^a}{(b-i)!}$$
1 |
|
E 硬盘检测
有 $n$ 个数字，给出从中选择 $10^4$ 个数的情况，估计 $n$ 的数量级。
可以根据输入的数字中本质不同的数判断，由于给出数的个数是固定的，可以直接在本地随机模拟。
1 |
|
##F 座位安排
有 $n$ 个人 $m$ 个座位，现在要为这 $n$ 个人分排座位，要求满足：
- 两个人不能相邻；
- 每个人不能坐在他不想坐的座位上；
- 两个人不能坐在正对面的位置上（当然 $m$ 为奇数时就不存在正对面的位置）
$n\leq10^9,k\leq2\times10^5$
1 |
|
G 删数游戏
给定两个长度为 $n$ 的数列，保证没有重复元素，在不改变各数列内顺序得情况下组合出一个新的数列，使得其最长上升长度最大。现在可以删除一些数，给出删除每个数的代价。问删除一些数使得最优情况下新序列的最长上升子序列长度变小的最小代价。
$n\leq100$
记 $\mathit{LIS}(a)$ 为 ${a}$ 的最长上升子序列长度，不难发现：对于两个数列 ${a},{b}$ 、最优情况下组合出的新数列 ${c}$ 满足 $\mathit{LIS}(c)=\mathit{LIS}(a)+\mathit{LIS}(b)$。
那么问题就变成了：对于使任意一个序列的最长上升子序列长度变小的代价。
其实这个问题很容易转化为点权的最小割用最大流算法解决。
1 |
|