[GESP202403八级]接竹竿

阅读量: 84 编辑

27、接竹竿

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是:每张牌上有一个点数 v,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本⾝)。

小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为Aᵢ (1≤i≤n)。小杨同学有Q次询问。第 i(1≤i≤Q )次询问时,小杨同学会给出 Lᵢ Rᵢ,小杨同学想知道如果用下标在[Lᵢ, Rᵢ]的所有卡牌按照下标顺序玩“接竹竿”的游戏,最后队列中剩余的牌数。

【输入描述】

第一行包含一个正整数T,表示测试数据组数。

对于每组测试数据,第一行包含一个正整数n,表示卡牌序列A的长度。

第二行包含N个正整数A₁ , A₂ , ..., Aₙ ,表示卡牌的点数。

第三行包含一个正整数 Q,表示询问次数。

接下来 Q 行,每行两个正整数 Lᵢ, Rᵢ,表示一组询问。

N≤1e5

【输出描述】

对于每组数据,输出Q行。第i行(1≤i≤Q )输出一个非负整数,表示第 i 次询问的答案。

【输入样例】

1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6

【输出样例】

1
1
0
2

//输出说明
对于第一次询问,小杨同学会按照1,2,2的顺序放置卡牌,在放置最后一张卡牌时,两张点数为2 的卡牌会被收⾛,因此最后队列中只剩余一张点数为 1 的卡牌。
对于第二次询问,队列变化情况为:{}->{1}->{1,2}->{1,2,3}->{1}->{1,3}->{1,3,1}->{}->{3}。因此最后队列中只剩余一张点数为 3 的卡牌。

【参考程序】

// 爱码岛编程 P10264
#include <bits/stdc++.h>
using namespace std;

int T, N, Q, L, R;
int arr[100005], pos[100005];

int main() {
    cin >> T;
    while (T--) {
        cin >> N;
        // 1 2 2 3 1 3
        for (int i = 1; i <= N; i++)
            cin >> arr[i];
        int indx[15] = {0};
        for (int i = N; i >= 1; i--) {
            // pos[i]表示第i个元素在其后第一次出现的位置
            pos[i] = indx[arr[i]];
            indx[arr[i]] = i;
        }
        
        // 5 3 0 6 0 0
        cin >> Q;
        while (Q--) {
            cin >> L >> R;
            int cnt = 0;
            for (int j = L; j <= R; j++) {
                if (pos[j] >= L && pos[j] <= R)
                    j = pos[j];
                else
                    cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}
爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司