寒假第二场牛客

好玩，简单题

解题思路：

这道题就是先理想状态下，每只猫的周围都是空的。然后就看是否存在两只猫挨在一起的情况，如果有的话就减一。这里判断两只猫是否挨在一起的方法是直接定一个走路方案数组，然后遍历其四周，看看其四周是否有猫。

解题思路：

直接从右边看起，按照他说的那样，如果遇到不相同的，直接步数加加后，删去后面的宝石即可。然后最终会遇到剩下前面开头连续相同的几个宝石，这时候就只能够一个一个的宝石这样删除了。而且这个版本就两种宝石颜色而已。

代码如下

// 太聪明了！！！QAQ
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
    
        for(int i=1;i<=n;i++) cin>>a[i];
        int ans = 0;
        int now = n;
        for(int i=n;i>=1;i--){
            if(a[i]!=a[now]){
                ans++;
                now = i-1;
            }
        }
        for(int i=1;i<=now;i++){
            // if(a[i]!=a[1]) break;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

困难版：

解题思路：

现在相当于宝石的颜色不再是2种了，而是有最多n种，然后先得到各种颜色的最后一次出现的下标，然后再得到这些下标中最小的那一个，作为一次删除的起点，然后后续思路都是一样的逻辑。

需要注意的是，考虑一下完成这一想法的数据结构，可以直接用vector来存数据。

代码如下：

// 太聪明了！！！QAQ
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N];
vector<int> pos[N];
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            pos[i].clear();
        }
        for(int i=1;i<=n;i++){
            pos[a[i]].push_back(i);
        }
        int mn = n;
        for(int i=1;i<=n;i++){
            if(pos[i].size()) mn = min(mn,pos[i].back());
        }
        int ans = 0;
        int now = mn;
        int pre = n;
        while(pre>=1){
            ans++;
            mn = now;
            for(int i=pre;i>=now;i--){
                pos[a[i]].pop_back();
                if(pos[a[i]].size()) mn = min(mn,pos[a[i]].back());
            }
            pre = now -1; // 逐步收缩,记住这里的顺序，先步数++，然后再进行收缩，这样就不存在步数缺了的情况了
            now = mn;  // 更新了现有颜色中各种颜色的最后下标的最小的那个下标
        }
        cout<<ans<<endl;
    }
    return 0;
}