P9900『PG2』消除萝卜 B 题解

· · 题解

大家好，我是 rc_Wechis。

题目传送门

solution

思考

眨眼一看此题如此困难，但是只要冷静下来仔细分析，还是可以找到一些线索的。

（1）若一个萝贝下面没有萝贝，它会一掉到底。

（2）可以上移萝贝，但是这个方法代价太大，我们尽量不用。

（3）可以添加萝贝，但是必须得上移。

我们发现如果出现以下情况：

0 1
0 1
1 0

那么无论我们拿掉底层的哪个萝贝，我们都不能在第一时间使用联通块消除大量萝贝。但是，只要我们在它的右下角放一个 0 （大家可以自己画一下图）就可以就可以一次性消掉许多。

而且由于题目十分良心，每一行只有两列，而且元素互不相同，也就是说只要你在最底下放一个萝贝就一定会有元素个数 ≥2 的联通块。

记初始数据的联通块个数为 res，加上放的一个萝贝，加上 1 个代价可以消 2 个，即 \div 2，最后加上放萝贝的代价 1,得出结果 \frac{(res+1)}{2}+1。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int res,n,a[N];
int main(){
    cin>>n;
    memset(a,-1,sizeof a);
    for(int i=1;i<=n;i++)cin>>a[i]>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1])res++;
    }
    cout<<((res+1)>>1)+1<<endl;
    return 0;
}

好了，这次就先到这里。