USACO 2016 Open Gold

B. Closing the Farm

题目链接

https://www.luogu.org/problem/P3144

题解

采用并查集解决这个问题。

从最后一个查询开始处理问题。每处理完一个问题，就将删除的谷仓与其相连的谷仓进行合并，并统计连通块个数。如果只有一个连通块，则整个农场都是连通的。

C. 248

题目链接

https://www.luogu.org/problem/P3146

题解

以下解法可以同时解决本题的白金组加强版，加强版的数据规模增加到了 \(2^{18}\)。

（加强版题目链接： https://www.luogu.org/problem/P3147）

用 \(f_{i,j}\) 表示以 \(j\) 为左端点，能合并出 \(i\) 这个数的右端点的位置。

可以推出以下转移方程：

$$f_{i,j}=f_{i−1,f_{i−1,j}}$$

为什么是这样一个状态转移方程？我们要考虑这个游戏的规则。

要想合并出 \(i\) 这个数字，我们需要合并两个相邻的 \(i-1\)。第一个 \(i-1\) 的位置当然就是 \(f_{i-1,j}\)。那么第二个位置呢？把第一个位置作为左端点，那么答案自然就是 \(f_{i−1,f_{i−1,j}}\)。

#include <stdio.h>
int f[60][270005];
int main()
{
 int n,ans;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  int x;
  scanf("%d",&x);
  f[x][i]=i+1;
 }
 for(int i=2;i<=58;i++)
  for(int j=1;j<=n;j++)
  {
   if(!f[i][j])f[i][j]=f[i-1][f[i-1][j]];
   if(f[i][j])ans=i;
  }
 printf("%d\n",ans);
 return 0;
}