P10264 [GESP202403 八级] 接竹竿

题目背景

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1148

题目描述

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

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

小杨同学现在有一个长度为 $n$ 的卡牌序列 $A$，其中每张牌的点数为 $A_i$（$1\le i\le n$）。小杨同学有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨同学会给出 $l_i,r_i$ 小杨同学想知道如果用下标在 $[l_i,r_i]$ 的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

输入格式

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

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

第二行包含 $n$ 个正整数 $A_1,A_2,\dots ,A_n$，表示卡牌的点数 $A$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示一组询问。

输出格式

对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。

输入输出样例 #1

输入 #1

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

输出 #1

1
1
0
2

说明/提示

样例解释

对于第一次询问，小杨同学会按照 $1,2,2$ 的顺序放置卡牌，在放置最后一张卡牌时，两张点数为 $2$ 的卡牌会被收走，因此最后队列中只剩余一张点数为 $1$ 的卡牌。

对于第二次询问，队列变化情况为：

{ } → { 1 } → { 1 , 2 } → { 1 , 2 , 2 } → { 1 } → { 1 , 3 } → { 1 , 3 , 1 } → { } → { 3 } \{\}\to\{1\}\to\{1,2\}\to\{1,2,2\}\to\{1\}\to\{1,3\}\to\{1,3,1\}\to\{\}\to\{3\} {}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为 $3$ 的卡牌。

数据范围

子任务	分数	$T$	$n$	$q$	$\max A_i$	特殊条件
$1$	$30$	$\le 5$	$\le 100$	$\le 100$	$\le 13$
$2$	$30$	$\le 5$	$\le 1.5\times 10^4$	$\le 1.5\times 10^4$	$\le 13$	所有询问的右端点等于 $n$
$3$	$40$	$\le 5$	$\le 1.5\times 10^4$	$\le 1.5\times 10^4$	$\le 13$

对于全部数据，保证有 $1\le T\le 5$，$1\le n\le 1.5\times 10^4$，$1\le q\le 1.5\times 10^4$，$1\le A_i\le 13$。

C++实现

#include <bits/stdc++.h>
#define int register unsigned
using namespace std;
unsigned t,n,q;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		int f[15] = {0},r[150005] = {0};
		for(int i = 1,x;i <= n;i++){
			cin>>x;
			r[f[x]] = i;
			f[x] = i;
		}
		cin>>q;
		while(q--){
			int x,y;
			cin>>x>>y;
			int ans = 0;
			for(int i = x;i <= y;i++){
				if(r[i] < x || r[i] > y) ans++;//不在范围内
				else i = r[i]; //快速地跳
			}
			cout<<ans<<"\n";
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容