目录
显示
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; }