模拟赛题讲解[11]

来自 xpp 2022-08-04 noi.ac #2731

题目描述：

xpp在玩祖玛游戏，他心血来潮想根据祖玛游戏出一个题。

给一个序列 \(a_1,a_2,\dots,a_n\) ，你每次可以选择相同且相邻的三个数删除他们，如果序列中存在这样相同且相邻的三个数，xpp将不断将他们删除，xpp想知道最后序列中还剩几个数呢？

输入格式：

第一行一个正整数 \(T(1\le T\le 10)\) 表示数据组数。

对于每组数据，第一行一个正整数 \(n\) 表示序列长度，第二行 \(n\) 个正整数表示 \(a[1\dots n]\)。

输出格式：

对于每组数据输出一行，表示答案。

输入1：

2
7
1 1 1 2 2 2 3
8
1 2 2 2 1 1 3 2

输出1：

1
2

数据规模：

对于 \(30\%\) 的数据，\(3\le n\le 10,~1\le a_i\le 10\)

对于 \(60\%\) 的数据，\(3\le n\le 10^3,~1\le a_i\le 10^3\)

对于 \(100\%\) 的数据，\(1\le a_i\le 10^9,~\sum n≤10^6\)

题解：

考虑用一个栈维护，满三个就不断的弹出

时间复杂度 \(O(\sum n)\) 大水题

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)

int stk[N],top;
void solve()
{
    top=0; int n,res; read(n); res=n;
    for(int i=1,x; i<=n; i++)
    {
        read(x);
        stk[++top]=x;
        while(top>=3 && stk[top]==stk[top-1]&&stk[top-1]==stk[top-2])
            top-=3,res-=3;
    }
    write(res); pc('\n');
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; read(Q);
    while(Q--) solve();
    return 0;
}