2024-03 · 8级 · 接竹竿

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1609 字

CCF 原卷官方标程 · STL、位运算、栈与队列 · 本地编译通过

2024-03
STL

正文

// GESP 2024-03 C++ 8级 编程题 2 · 接竹竿
// 原题：https://oj.yecheng.tv/p/gs2403l8p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1602047270977568.pdf
// 题意：小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。
// 知识点：STL、位运算、栈与队列
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int a[N];
int nxt[N][30],pos[20];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        memset(pos,0,sizeof pos);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=0;j<=20;j++)nxt[i][j]=n+1;
        }
        for(int i=n;i>=1;i--){
            if(!pos[a[i]]){
                nxt[a[i]][0]=n+1;
                pos[a[i]]=i;
            }else{
                nxt[i][0]=pos[a[i]];
                pos[a[i]]=i;
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=1;j<=20;j++){
                if(nxt[i][j-1]+1<=n)
                    nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
            }
        }
        int q;
        cin>>q;
        while(q--){
            int l,r;
            cin>>l>>r;
            int ii=l;
            int ans=0;
            while(ii<=r){
                while(ii<=r&&nxt[ii][0]>r){
                    ii++;
                    ans++;
                }
                if(ii>r)break;
                for(int j=20;j>=0;j--){
                    if(nxt[ii][j]<=r){
                        ii=nxt[ii][j];
                        break;
                    }
                }
                ii++;
            }
            cout<<ans<<"\n";
        }
    }
}

2024-03 · 8级 · 接竹竿

正文

GESP 标程 · 考级真题的其它内容