P10264 [GESP202403 八级]接竹竿 题解

Shadow_T · 2024-03-26 19:22:32 · 个人记录

题目大意

接竹竿游戏规则为按顺序依次加入一个牌堆，如果发现牌堆中有一对相同的牌，则将两张牌中间的牌（包含两张牌）全部拿出，求最终牌堆有多少牌。

有一个序列 a，有 q 次询问，每次询问给出 l,r，求出 [l,r] 的接竹竿结果。

题目分析

考虑直接模拟。我们先预处理出每个 a_i 的后面最近出现相同值的下标，定为 z。

对于每次询问：

• 如果 z_i \leq r，那么直接跳转到 z_i+1。

• 否则计数器加一，很明显 a_i 最近的相同位置都大于 r 了，就再也没有机会消掉了。随后跳转到 i+1。

最终输出计数器就可以了。

可算极限复杂度为 \mathcal {O}(Tqn)，极限运算次数会达到 5\times (1.5 \times 10^4)^2=1.1\times 10^9。然而由于 a_i \leq 13，所以相同会出现的很密集，在一次次的跳过中省去了很多次运算，所以可以通过。

提交记录。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int z[maxn];
int pos[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        pos[i]=0,z[i]=0; 
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            z[pos[a[i]]]=i;
            pos[a[i]]=i;
        }
        int q;
        cin>>q;
        while(q--)
        {
            int l,r,ans=0;
            scanf("%d%d",&l,&r);
            if(l>r) swap(l,r);
            for(int i=l;i<=r;i++)
            {
                if(z[i]!=0&&z[i]<=r) i=z[i];
                else ans++;
            }
            cout<<ans<<"\n";
        }
    }
}