社区讨论

提供一种 2025.12 GESP 8级 新解法

___Green_tick__
学术版参与者 6已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mjo8zeh5
此快照首次捕获于
2025/12/27 19:59
2 个月前
此快照最后确认于
2025/12/30 18:05
2 个月前
查看原帖

题面

给定 nn 和 mm，表示一串项链有 nn 个宝石形成一个环，共有 mm 种宝石。
给定 aia_i 为第 ii 颗宝石的种类（ai∈[1,m]a_i \in [1,m] 且 ⋃i=0nai=[1,m]\bigcup_{i=0}^{n}{a_i}=[1,m]）。
求取连续字串满足：
  • 设子串序列为 xx。
  • ⋃i=0nxi=[1,m]\bigcup_{i=0}^{n}{x_i}=[1,m]。
的最多子串数量。

正常

打了个暴力，得了前 40%40\% 的分。

震惊

发现了神奇的情况：
CPP
#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln '\n'

const var MaxN=1e5+10;
var n,m;
var a[MaxN<<1];

bool check(vector<bool> p){ // 判断 p 是否每种宝石均有
    for(var i=1;i<=m;i++){
        if(!p[i]) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(var i=1;i<=n;i++){
        cin>>a[i]; // 读入
        a[i+n]=a[i]; // 破环成链
    }
    
    vector<bool> p(m+1,0);
    var q=0;

    for(var j=1;j<=n;j++){ // 不知
        p[a[j]]=1;

        if(check(p)){
            p.clear();
            p.resize(m+1,0);
            q++;
        }
    }

    cout<<q<<ln;
    return 0;
}
有 70%70\% 的分！

从此走上骗分之路！

结合暴力：
CPP
#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln '\n'

const var MaxN=1e5+10;
var n,m;
var a[MaxN<<1];

bool check(vector<bool> p){ // 判断 p 是否每种宝石均有
    for(var i=1;i<=m;i++){
        if(!p[i]) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(var i=1;i<=n;i++){
        cin>>a[i]; // 读入
        a[i+n]=a[i]; // 破环成链
    }
    
    if(n<=1000){ // 神奇暴力 还能理解
        var ans=0;
        for(var i=1;i<=n;i++){
            vector<bool> p(m+1,0);
            var q=0;

            for(var j=i;j<=i+n-1;j++){
                p[a[j]]=1;

                if(check(p)){
                    p.clear();
                    p.resize(m+1,0);
                    q++;
                }
            }

            ans=max(ans,q);
        }

        cout<<ans<<ln;
    }else{ // 完全离谱
        vector<bool> p(m+1,0);
        var q=0;

        for(var j=1;j<=n;j++){ // 不知
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        cout<<q<<ln;
    }
    return 0;
}
有 80%80\% 的分！

尝试！骗分！

CPP
#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln '\n'

const var MaxN=1e5+10;
var n,m;
var a[MaxN<<1];

bool check(vector<bool> p){ // 判断 p 是否每种宝石均有
    for(var i=1;i<=m;i++){
        if(!p[i]) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(var i=1;i<=n;i++){
        cin>>a[i]; // 读入
        a[i+n]=a[i]; // 破环成链
    }
    
    if(n<=1000){ // 神奇暴力 还能理解
        var ans=0;
        for(var i=1;i<=n;i++){
            vector<bool> p(m+1,0);
            var q=0;

            for(var j=i;j<=i+n-1;j++){
                p[a[j]]=1;

                if(check(p)){
                    p.clear();
                    p.resize(m+1,0);
                    q++;
                }
            }

            ans=max(ans,q);
        }

        cout<<ans<<ln;
    }else{ // 完全离谱
        var ans=0;
        vector<bool> p(m+1,0);
        var q=0;

        for(var j=1;j<=n;j++){ // 不知
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        ans=max(ans,q);

        for(var j=n/2;j<=n/2+n-1;j++){ // 玄学
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        ans=max(ans,q);

        cout<<ans<<ln;
    }
    return 0;
}
90%90\% 的分！
CPP
#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln '\n'

const var MaxN=1e5+10;
var n,m;
var a[MaxN<<1];

bool check(vector<bool> p){ // 判断 p 是否每种宝石均有
    for(var i=1;i<=m;i++){
        if(!p[i]) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(var i=1;i<=n;i++){
        cin>>a[i]; // 读入
        a[i+n]=a[i]; // 破环成链
    }
    
    if(n<=1000){ // 神奇暴力 还能理解
        var ans=0;
        for(var i=1;i<=n;i++){
            vector<bool> p(m+1,0);
            var q=0;

            for(var j=i;j<=i+n-1;j++){
                p[a[j]]=1;

                if(check(p)){
                    p.clear();
                    p.resize(m+1,0);
                    q++;
                }
            }

            ans=max(ans,q);
        }

        cout<<ans<<ln;
    }else{ // 完全离谱
        var ans=0;
        vector<bool> p(m+1,0);
        var q=0;

        for(var j=1;j<=n;j++){ // 不知
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        ans=max(ans,q);

        for(var j=n/2;j<=n/2+n-1;j++){ // 玄学
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        ans=max(ans,q);

        for(var j=n/4;j<=n/4+n-1;j++){ // 魔法
            p[a[j]]=1;

            if(check(p)){
                p.clear();
                p.resize(m+1,0);
                q++;
            }
        }

        ans=max(ans,q);

        cout<<ans<<ln;
    }
    return 0;
}
于是AC了。

回复

共 7 条回复，欢迎继续交流。

正在加载回复...