题解：P10729 [NOISG 2023 Qualification] Dolls

· · 题解

P10729 [NOISG 2023 Qualification] Dolls 题解

前言

有点意思的思维题

题意分析

有若干个套娃，第 i 个套娃的尺寸为 a_i，一个套娃 x 可以被 套娃 y 嵌套当且仅当 a_y-a_x \geqslant 2。求对于前 i 个套娃最多可以嵌套几次。

提两个小问题：
看到 a_y-a_x \geqslant 2，你想到了什么？
遇到有点棘手的条件，第一步应该怎么做？

逐步分析

SubTask1:n\le200：最初的思考

暴力解法：每次询问对 a_i 排序并去重，记 f_i表示到第 i 个套娃时，最大嵌套次数。显然我们有

f_i= \begin{cases} f_{i-1}+1 &\text{if } a_{i-1}+1 \not= a_i\\ f_{i-2} +1 &\text{ if } a_{i-1}+1 = a_i \end{cases}

SubTask2:a_i 都是奇数：特殊情况

由于 a_i 都是奇数，所以一定有 \forall_i,a_i-a_{i-1}\ge 2 那么我们就可以直接按第一种情况转移。
但是这样是最优的吗？
显然对于每一个之前没出现过的 a_i，它都可以使答案增大 1 （可以参照样例2）。那么我们可以直接用一个数组记录一个数是否出现过，O(1) 计算贡献即可。

SubTask3:a_i 都不是 4 的倍数：提示

因为 a_i 都不是 4 的倍数，所以你记录数是否出现过的数组的值可能长这样（ 1 表示出现过)：

[0,1,1,1,0,1,1,0,0,0,1,0,0]

相当明显，若干连续的 1 形成了一组。对于每一个组，它们之间的贡献是叠加的，而且互不影响（不理解可以再看一看递推方程），它们的贡献只受它们的长度影响（因为我们并不关心这个组内 a_i 的具体值）。
所以我们可以枚举这个组的长度（显然只有 0,1,2,3 ，四种可能），并求出贡献即可。
思考一个小问题：如果有一个数出现在了两个组之间（如 6 出现在 5 和 7 之间），这个时候该怎么计算贡献呢？

正解：扩展

让我们沿着上面的思路继续思考，因为一个组的贡献只受其长度影响，那么我们只需要维护一个组的长度，而且由上面的枚举可以得知：一个长 len 的组，它对答案的贡献为 \lceil \dfrac{len}{2} \rceil。（可以在组内手动推一把验证一下）。 而这个信息可以存储在组内任意一个节点上。
那么现在我们回到了之前那个问题：当一个数出现在了两个组之间时，我们怎么计算贡献？
分析一下我们需要干什么：我们需要通过前面一个点和后面一个点分别找到它们所在组负责存储信息的点，还需要将它们合并。有查有并，这不就是并查集嘛！
通过并查集我们就可以快速进行组长的合并与维护。
到这里题目就分析完了，具体实现看代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
inline int read(){
  register int x=0,f=1;
  char c=getchar();
  while(c<'0' || '9'<c) f=(c=='-')?-1:1,c=getchar();
  while('0'<=c && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
  return x*f;
}
const int N=500010;
int n,f[N],ans,sz[N];
bool vis[N];
inline int find(int x){ return f[x]=f[x]==x?x:find(f[x]);}
inline void un(int x,int y){
  int fx=find(x),fy=find(y);
  if(fx==fy) return;
  f[fx]=fy;
  sz[fy]+=sz[fx];
}
int main()
{
  for(int i=1;i<=500000;i++) f[i]=i,sz[i]=1;
  n=read();
  for(int i=1,x;i<=n;i++){
    x=read();
    if(vis[x]) {printf("%d ",ans);continue;}
    vis[x]=true;
    //分类讨论 x 所处位置，不同情况有不同的合并方式
    if(!vis[x+1] && !vis[x-1]) ans++;
    else if(!vis[x+1]) un(x-1,x),ans+=sz[find(x)]%2;
    else if(!vis[x-1]) un(x,x+1),ans+=sz[find(x)]%2;
    else{
      int f1=find(x-1),f2=find(x+1);
      ans-=(sz[f1]+1)/2+(sz[f2]+1)/2;//消除影响
      un(x-1,x),un(x,x+1);
      ans+=(sz[find(x)]+1)/2;//再次计算贡献
    }
    printf("%d ",ans);
  }

  return 0;
}