2024.7.20 模拟赛

· · 题解

2024.7.20 模拟赛

A

设 f(x) 为 x 十进制下不同数码的个数，给定 l,r,A，求 l\le x\le r 且 f(x)=A 的 x 个数，令 n 为 l,r 位数，则 n\le 2\times 10^5，保证 l,r 位数相同。

Sol

数位 dp 一种转化：枚举得到没有值域限制的后缀（消除数码之间差异性）。

数位 DP 是 O(n\cdot 2^{10}\cdot 10) 的，难处在于 l\le x\le r，去掉这个限制。

设 l 和 r 十进制下 lcp 为 p，则 x 前 p 位已经固定，考虑枚举 x 的 p+1 位，讨论与 l 相等，与 r 相等和在两者之间的情况。

若在两者之间，则 p+2\dots n 这些位再无限制，则前 p+1 位你只关心不同数码的个数，设 f_{i,j,k} 为当前有 i 个位置可以任意填，要求这些位置数码集合与大小为 j 的数码集的并为 k，这样的方案数。

若与 l 相等，枚举首个与 l 不同的位再枚举下一位所填数码，可以转化为上述问题，与 r 相等同理，这部分的复杂度是 O(10n)，求 f 复杂度 O(10^2n)。

B

有序列 a_{1\dots n}，操作有单点修改和对一个区间求任取三个数，能构成的三角形中周长的最大值，n\le 2\times 10^5,a_i\le 5\times 10^8。

Sol

朴素做法是区间内数排序，从大到小判断连续的三个是否合法，考虑减少判断的次数。

设最大三个数从小到大分别为 a,b,c，则若其不合法，即 a+b\le c，有 a\le \frac{c}{2}。再将 a 作为下一轮判断的 c，这样至多判断 \lceil\log V\rceil 轮后必定出现合法三元组，否则询问区间内不存在。

这样对于一次询问你需要的信息只有区间中最大的 O(\log V) 个数，可以用每次找区间最大数后置 0 的方式找到这些数，复杂度 O(q(\log n+\log n\log V))。

C

给定 n,m,k 和集合 S_{1\dots m}\subseteq \{1,\dots ,n\}，保证 |S_i|\ge k。对 T\subseteq \{1,\dots ,n\}，定义 f(T)=\sum_{i=1}^m[|S_i\cap T|\ge k]，对所有 p=1,\dots, m，求使得 f(T)\ge p 的最小 |T|，k\le n\le 24,m\le 3\times 10^5。

Method1. 容斥+FWT

  • 集合问题拆贡献：枚举交/并得到的集合，再放宽限制容斥。
  • 此处求解容斥系数：考虑枚举的集合的实际意义，贡献放到子集，这部分我的理解还不彻底。

对所有 p 求解，不妨直接求出所有 f(T) 值，这样你想让不同 f(T) 之间产生联系，写作：

f(T)=\sum_{X}(\sum_{i=1}^m[S_i\cap T=X])\cdot [|X|\ge k]=\sum_{X\subseteq T,|X|\ge k}(\sum_{i=1}^m[X\subseteq S_i])\cdot a_{|X|}

其中 a_{|X|} 是容斥系数，需要满足 \forall l\ge k，有 \sum_{i=k}^l\binom{l}{i}a_i=1，具体地，最后一个式子可以写作 \sum_X(\sum_i[X\subseteq S_i]-\sum_i[X\subsetneqq T\cap S_i])，此时 X 的意义从第一次化简时的枚举 S_i\cap T 变成枚举 S_i\cap T 的子集，若 |S_i\cap T|=l，X 中会有 \binom{l}{j} 个大小为 j 的 S_i\cap T 子集，在处理到这些子集时分别有 a_j 的贡献。

对于 i\ge k，通过 a_i=1-\sum_{j=k}^{i-1}\binom{i}{j}a_j 可以 O(n^2) 求得，i<k 令 a_i=0，记 g(X)=\sum_i[X\in S_i]\cdot a_{|X|}，则 f(T)=\sum_{T_0\subseteq T}g_{T}，总复杂度 O(2^nn+n^2)。

Method2. 高维差分

拆开贡献，设 g_{T}(i)=[|S_i\cap T|\ge k]，则 f_T=\sum_{i=1}^mg_T(i)。

改变形式，对所有 g(i) 数组做高维差分得到 g'(i)，有 g'_T(i)=\sum_{T_0\subseteq T}(-1)^{|T|-|T_0|}[|S_i\cap T_0|\ge k]。

对于 T_0\nsubseteq S_i 的情况，取 x\in T_0-S_i，则 T_1=T_0-\{x\} 的贡献和 T_0 抵消，故只需要考虑 T_0\subseteq S_i 的情况，则 g'_T(i)=\sum_{T_0\subseteq T\cap S_i}(-1)^{|T|-|T_0|}[|T_0|\ge k]，再写成二项式反演的形式有：

g'_T(i)=(-1)^{|T|}\sum_{j=k}^{|T\cap S_i|}(-1)^j\binom{|T\cap S_i|}{j}

将其记作 (-1)^{|T|}h_{|T\cap S_i|} 再用 g' 来表示 f，因为 g_T(i)=\sum_{T_0\subseteq T}g'_{T_0}(i)，有 f_T=\sum_{T_0\subseteq T}(-1)^{|T_0|}\sum_{i=1}^mh_{|T_0\cap S_i|}。

现在只需要求出所有 F_T=\sum_{i=1}^mh_{|T\cap S_i|} 即可高维前缀和出 f，这个我不会，但是可以做。

D

见 图的连通性相关算法。