ZJOI 2022 部分题解
太菜了所以只写了两题
[ZJOI2022] 树
https://www.luogu.com.cn/problem/P8329
题解
玩一玩样例可以得到这样的式子
\[ans=\sum_{ S\cup T = [n],\ S\cap T= \varnothing} f(S) g(T) \]其中 \(f(S)\) 表示第一棵树非叶子结点集合恰好是 \(S\) 的方案数
\(g(T)\) 表示第二棵树非叶子结点集合恰好是 \(T\) 的方案数
\([n]\) 表示 \(\{1,\dots,n\}\)
所以
\[ans=\sum_{ S\cup T = [n],\ S\cap T= \varnothing} f(S)g(T) \]我们想求 \(f(S)\)，很不好求，原因就在于你既要考虑 \(S\) 内的点是非叶子的限制，还要考虑 \(S\) 外的点是叶子的限制
我们只考虑后面的限制，看看能不能求（
那其实就是求第一棵树非叶子节点集合包含于 \(S\) 的方案数，记作 \(F(S)\)
看到这大家应该就想到反演了
这边简单讲一下集合反演
集合反演
\[F(S)=\sum_{S'\subseteq S} f(S') \Leftrightarrow f(S)=\sum_{S'\subseteq S} (-1)^{|S|-|S'|}F(S)\\ F(S)=\sum_{S\subseteq S'} f(S') \Leftrightarrow f(S)=\sum_{S\subseteq S'} (-1)^{|S|-|S'|}F(S) \]证明跟别的反演一样带进去就可以证了（个人感觉反演很奇妙
直接开始反演，推式子：
\[\begin{align*} F(S)&=\sum_{S'\subseteq S} f(S')\\ f(S)&=\sum_{S'\subseteq S} (-1)^{|S|-|S'|}F(S')\\ ans&=\sum_{ S\subseteq [n]} f(S)g(T) \\ &=\sum_{ S\cup T = [n],\ S\cap T= \varnothing} \sum_{S'\subseteq S} (-1)^{|S|-|S'|}F(S') \sum_{T'\subseteq S} (-1)^{|T|-|T'|}F(S')G(T') \\ &=\sum_{ S\cup T = [n],\ S\cap T= \varnothing} \sum_{S'\subseteq S} \sum_{T'\subseteq S} (-1)^{|S'|+|T'|}F(S')G(T') \\ &= \sum_{\ S'\cap T'= \varnothing} (-1)^{n-|S'|-|T'|}F(S')G(T') \sum[(S'\subseteq S) \and (T' \subseteq T) \and (S\cap T = \varnothing)] \\ &= \sum_{\ S'\cap T'= \varnothing} (-1)^{n-|S'|-|T'|}F(S')G(T') 2^{n-|S'|-|T'|} \\ &= \sum_{\ S'\cap T'= \varnothing} (-2)^{n-|S'|-|T'|}F(S')G(T') \\ \end{align*} \]于是你开始 dp
怎么 dp 呢？ dp 处理子集问题肯定是按顺序考虑每个元素加不加入子集
也就是说记一维 \(i\) 表示处理到哪一个元素
假设它在第一棵子树中这时候有 \(j\) 种选父亲的方法（父亲首先得是 \(\{1,\dots,i\}\) 里，然后必须是非叶子）
在第二棵中有 \(k\) 种选父亲的方法
那么就可以开始 dp
- \(i\) 在第一棵树内是叶子结点，第二棵内不是，也就是\(i\notin S',i\in T'\)，这样一来，\(f_{i,j,k}\) 要转移到 \(f_{i+1,j,k-1}\)，\(k-1\) 是因为 \(i\) 在第二棵树内可以选择 \(i+1\) 作为父亲，\(i+1\) 少了一个，这时候代入式子可以得到 \(f_{i+1,j,k-1} \mathrel{+}= f_{i,j,k}\)
- \(f_{i+1,j+1,k} \mathrel{+}= f_{i,j,k}\)
- \(f_{i+1,j,k} \mathrel{+}= -2f_{i,j,k}\)
这样就好了，时间复杂度 \(O(n^3)\)
需要积累的东西是推式子题可以推一推然后 dp
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505;
int P,n;
int f[2][N][N];
int main()
{
scanf("%d%d",&n,&P);
for(int i=1; i<=n; i++) f[1][1][i]=1;
for(int i=1,ib=1; i<n; i++,ib^=1)
{
int ans=0;
for(int j=1; j<=i; j++)
for(int k=1; k<=n-i; k++)
{
int t=(ll)j*k%P;
(f[ib^1][j+1][k]+=(ll)t*f[ib][j][k]%P)%=P;
(f[ib^1][j][k-1]+=(ll)t*f[ib][j][k]%P)%=P;
(f[ib^1][j][k]+=(ll)(P-2)*t%P*f[ib][j][k]%P)%=P;
if(k==1) (ans+=(ll)f[ib][j][k]*t%P)%=P;
}
memset(f[ib],0,sizeof f[ib]);
printf("%d\n",ans);
}
return 0;
}
[ZJOI2022] 众数
https://www.luogu.com.cn/problem/P8330
题解
首先一个需要积累的东西：遇到众数要考虑平衡规划
问题等价于求选一个区间，内部众数和外部众数出现次数之和的最大值，以及取到最大值外部众数的值
这个东西我们考虑分成 \(<B\) 和 \(\ge B\) 的两种数（以下叫小数和大数）
区间内部是 \(b\) ，区间外部是 \(a\)
如果大数在外面，我们先枚举 \(a,b(a\geq B)\) ，我们如果先算上 \(a\) 的出现次数，然后每一段区间对答案的贡献值就变成 \(cnt(b)-cnt(a)\)，然后可以变成一个最大子段和问题，每个 \(b\) 的位置上是 \(+1\) ，\(b\) 之间的区间上是一个 \(\leq 0\) 的数，然后直接 \(dp\) 就可以求出贡献值的最大值，\(b\) 之间的 \(a\) 个数可以前缀和预处理，效率是 \(O(\frac{n}{B}\cdot \sum{cnt(b)})\leq O(\frac{n^2}{B})\)
如果大数在里面也差不多，\(a,b(b\geq B)\)，这边注意的是因为 \(a\) 是小数，所以按 \(a\) 出现次数来分割，每个 \(a\) 的位置上是 \(-1\) ，之间的区间是 $\geq 0 $ 的数
现在要考虑的就是区间内外都是小数的贡献，不能直接枚举 \(a,b\) 怎么办呢？那我们可以来枚举众数，发现内部众数一定 \(<B\)，然后我们要快速求出满足条件的区间内 \(a\) 个数的最小值（贡献也是 \(cnt(b)-cnt(a)\) 我们固定了 \(cnt(b)\)，就要求 \(cnt(a)\) 最小值）
（诶诶怎么求好呢ww）
注意到区间的左右一定可以取到刚好顶到 \(a\) 出现的位置（或者 \(1,n\)）
那我们可以预处理一个数组 \(f_{i,j}\) 表示从 \(j\) 开始，要众数 \(i\) 次出现，最小的右端点位置
（如何求 \(f\) : 首先枚举众数，然后枚举 \(L,R\)，\(f[R-L+1][pos[L]]=pos[R]\)，接着 \(f[i][j]=\max(f[i][j+1],f[i][j])\)就好了）
我们枚举 \(a\) 的两个位置 \(pos[L],pos[R]\)，我们在这之间看看能不能找到区间，此时 \(cnt(a)=R-L-1\)，然后可以二分最大的 \(i\) 满足 \(f_{i,j}< pos[R]\) 这就是 \(cnt(b)\) 了，效率有 log 不太行
注意到可以直接利用单调性双指针就完了，效率 \(O(nB)\)
为什么是 \(O(nB)\) ？？（不应该是枚举 \(a\)：\(O(n)\) ，然后枚举 \(L,R\) ：\(O((B)^2)\)？）
这边积累一个小东西：
如果 \(a_i\leq \sqrt{n},\sum{a_i}\leq n\) ，\(\sum{a_i^2}\leq\sum{a_i\sqrt{n}}\leq n\sqrt{n}\)
所以取 \(B=\sqrt{n}\) 然后效率 \(O(n\sqrt{n})\)
具体看看代码
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5, B = 505;
int _,n,sqn,a[N],dsc[N],nd,f[B][N],lrg[B],nlrg,ans,pre[B][N],inlrg[N],res[N],nres;
//_:组数 sqn:sqrt(n) dsc:离散化 nd:dsc大小 f[i][j] min(k) 使得 [j,k] 内众数为 i
//lrg[nlrg] 出现次数 >= sqn 的数 ans 所求的众数最大出现次数 pre[i][j] [1,j] lrg[i]出现次数
//inlrg[i] [i\in lrg] res[nres] 所求的众数的值
vector<int> pos[N]; //每个数出现的位置
void update(int r, int val) //更新 ans,res
{
if(r>ans) ans=r,res[nres=1]=val;
else if(r==ans) res[++nres]=val;
}
void init()
{
//输入以及清多测
scanf("%d",&n); sqn=sqrt(n); for(int i=1; i<=n; i++) scanf("%d",&a[i]),dsc[i]=a[i];
nlrg=nres=ans=0; for(int i=1; i<=n; i++) pos[i].clear();
for(int i=1; i<=sqn+1; i++) for(int j=1; j<=n+2; j++) f[i][j]=N,pre[i][j]=0;
//离散化
sort(dsc+1,dsc+n+1); nd=unique(dsc+1,dsc+n+1)-dsc-1;
for(int i=1; i<=n; i++) a[i]=lower_bound(dsc+1,dsc+nd+1,a[i])-dsc,pos[a[i]].push_back(i);
//处理大数以及前缀和
for(int i=1; i<=nd; i++)
if((int)pos[i].size()>=sqn)
{
lrg[++nlrg]=i; inlrg[i]=1; for(auto j:pos[i]) pre[nlrg][j]=1;
for(int j=1; j<=n; j++) pre[nlrg][j]+=pre[nlrg][j-1];
}
else inlrg[i]=0;
}
//最大子段和所用的 dp 数组
int dp[N<<1],ndp;
void work1() // 大在外
{
for(int i=1; i<=nlrg; i++) for(int j=1; j<=nd; j++) if(j!=lrg[i])
{
int li=lrg[i],r=dp[ndp=0]=1;
for(int k=1; k<(int)pos[j].size(); k++) dp[++ndp]=-(pre[i][pos[j][k]-1]-pre[i][pos[j][k-1]-1]),dp[++ndp]=1;
for(int k=1; k<=ndp; k++) r=max(r,dp[k]+=max(dp[k-1],0));
update((int)pos[li].size()+r,li);
}
}
void work2() // 大在里
{
for(int i=1; i<=nd; i++) if(!inlrg[i]) for(int j=1; j<=nlrg; j++)
{
int sz=pos[i].size(),r=dp[ndp=0]=pre[j][pos[i][0]-1];
for(int k=0; k<sz-1; k++) dp[++ndp]=-1,dp[++ndp]=pre[j][pos[i][k+1]-1]-pre[j][pos[i][k]-1];
dp[++ndp]=-1; dp[++ndp]=pre[j][n]-pre[j][pos[i][sz-1]];
for(int k=1; k<=ndp; k++) r=max(r,dp[k]+=max(dp[k-1],0)); update(sz+r,i);
}
}
void work3() //小对小
{
for(int i=1; i<=nd; i++) if(!inlrg[i]) { int sz=(int)pos[i].size(); for(int l=0; l<sz; l++) for(int r=l; r<sz; r++) f[r-l+1][pos[i][l]]=pos[i][r]; }
for(int i=n; i; i--) for(int j=1; j<sqn; j++) f[j][i]=min(f[j][i],f[j][i+1]);
for(int i=1; i<=nd; i++) if(!inlrg[i])
{
int sz=pos[i].size(),r=0,md;
for(int R=0; R<sz; R++) { md=0; while(md+1<sqn and f[md+1][1]<pos[i][R]) md++; r=max(r,md-R); }
for(int L=0; L<sz; L++) { md=0; while(md+1<sqn and f[md+1][pos[i][L]+1]<=n) md++; r=max(r,md-(sz-L-1)); }
for(int L=0; L<sz; L++)
{
md=0;
for(int R=L+1; R<sz; R++)
{
while(md+1<sqn and f[md+1][pos[i][L]+1]<pos[i][R]) md++;
r=max(r,md-(R-L-1));
}
}
update(sz+r,i);
}
}
int main()
{
scanf("%d",&_);
while(_--)
{
init(); work1(); work2(); work3(); sort(res+1,res+nres+1); nres=unique(res+1,res+nres+1)-res-1;
printf("%d\n",ans); for(int i=1; i<=nres; i++) printf("%d\n",dsc[res[i]]);
}
return 0;
}