篮球杯 Day2

我不是女神ヾ 2024-03-25 10:57 87阅读 0赞

**一些我不会的简单题集锦**

**感觉篮球杯很容易错啊**

**考场应该就是，先去想正解思路，想出来了就写**

**想不出来就想怎么暴力，然后按小的数据范围写暴力**

**考虑暴力的时候，先去考虑枚举的是什么，然后怎么去写for循环，然后再去考虑怎么去dfs**

**然后题面如果给了例子可以输出例子的细节去比对一下**

**填空题记得把原来的代码注释掉，直接填上答案**

**写完过了样例之后再去仔细看一遍题面，然后再去看一遍代码，检查一下，然后再交**

**在想这两样东西的时间不能超过10分钟，如果十多分钟过去了，暴力都想不出来，直接跳题，但是别忘记蒙**

**然后等所有题都写的差不多的时候，赶紧把连暴力都不会写的题写一下暴力，暴力分拿满**

**最后的时间一定要去写对拍！！**

递增三元组

[递增三元组 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

![1ff1b4865520334502dd3c15c156a6cf.png][]

思路：

一开始写了个n2的超时了两个点，只拿了部分分

正解应该是枚举b数组的指针，然后两个二分，算组合数

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    
    int n;
    int a[mxn],b[mxn],c[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=n;i++) cin>>c[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        sort(c+1,c+1+n);
        int ans=0;
        for(int i=1;i<=n;i++){
            int pos1=lower_bound(a+1,a+1+n,b[i])-a-1;
            int pos2=upper_bound(c+1,c+1+n,b[i])-c;
            ans+=pos1*(n-pos2+1);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        //p_init(1e6);
        while(__--)solve();return 0;
    }

如果不会写就这样写暴力：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    
    int n;
    int a[mxn],b[mxn],c[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=n;i++) cin>>c[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        sort(c+1,c+1+n);
        int ans=0;
        for(int i=1;i<=n;i++){
            int pos=upper_bound(b+1,b+1+n,a[i])-b;
            for(int j=pos;j<=n;j++){
                int pos2=upper_bound(c+1,c+1+n,b[j])-c;
                ans+=(n-pos2+1);
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        //p_init(1e6);
        while(__--)solve();return 0;
    }

小朋友崇拜圈

[小朋友崇拜圈 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 1]

![753ae677dbf771ed8aee5bb1eaf4b7d9.png][]

思路：

其实就是求图里的最大环有几个结点

考虑DFS，当遇到的那个结点的儿子结点是目标结点且被访问过，那就是环了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    
    
    int n,x,tot=0,ans=-1;
    int head[mxn],vis[mxn],son[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void dfs(int u,int dep,int goal){
        if(vis[son[u]]&&son[u]!=goal) return;
        if(vis[son[u]]&&son[u]==goal){
            ans=max(ans,dep);
            return;
        }
        for(int i=head[u];~i;i=edge[i].next){
            if(vis[edge[i].to]) continue;
            vis[edge[i].to]=1;
            dfs(edge[i].to,dep+1,goal);
            vis[edge[i].to]=0;
        }
    }
    void solve(){
        cin>>n;
        init();
        for(int i=1;i<=n;i++){
            cin>>x;
            add(i,x);
            son[i]=x;
        }
        for(int i=1;i<=n;i++){
            //memset(vis,0,sizeof(vis));
            vis[i]=1;
            dfs(i,1,i);
        }
        cout<<ans<<"\n";
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

斐波那契数列最大公约数

![b8335a09d5e47f2e206ca1fb778a8dba.png][]

思路：

这居然是个纯结论，那就记住就好了

结论就是：f\[gcd(a,b)\]=gcd(f\[a\],f\[b\])

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    
    int f[mxn];
    void solve(){
        f[1]=1,f[2]=1;
        for(int i=3;i<=2020;i++) f[i]=f[i-1]+f[i-2];
        cout<<f[__gcd(520,2020)]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        //p_init(1e6);
        while(__--)solve();return 0;
    }

乘积最大

[乘积最大 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 2]

题意：

![55835c51c3c19d1d8ac3ac54161d235a.png][]

思路：

根本不会，考场上肯定就直接暴力DP了

这里的暴力DP用到滚动数组，就和背包一样的做法

Code：（20分）

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+9;
    const int Inf=-1e18;
    
    int n,k;
    int dp[2][mxn],a[mxn];
    int calc(int x){
        if(x>0) return x%mod;
        return (-x)%mod;
    }
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=0;i<=1;i++){
            for(int j=1;j<=k;j++) dp[i][j]=Inf;
        }
        dp[1&1][0]=0,dp[1&1][1]=a[1];
        for(int i=2;i<=n;i++){
            for(int j=0;j<=i;j++){
                dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j]);
                dp[i&1][j]=max(dp[i&1][j],(dp[(i-1)&1][j-1]*a[i]));
            }
        }
        cout<<calc(dp[n&1][k])<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        //p_init(1e6);
        while(__--)solve();return 0;
    }

正解不想看，考场肯定不会，会也浪费时间了

等差素数列

[等差素数列 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 3]

**一次过了，只能说要大胆地去写暴力！！跑不出来就挂后台！！**

![137693b2ac71a08a9eabdf9a2eeea2ed.png][]

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+9;
    const int Inf=-1e18;
    
    
    int len=0;
    int vis[mxn],prime[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        /*int ans=1e9;
        for(int i=1;i<=len;i++){
            int p1=prime[i];
            for(int j=i+1;j<=len;j++){
                int p2=prime[j];
                int d=p2-p1;
                if(p1+9*d<=1e6&&!vis[p1+2*d]&&!vis[p1+3*d]&&!vis[p1+4*d]&&!vis[p1+5*d]&&!vis[p1+6*d]&&!vis[p1+7*d]&&!vis[p1+8*d]&&!vis[p1+9*d])  ans=min(ans,d);
            }
        }
        cout<<ans<<'\n';*/
        cout<<210<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        //p_init(1e6);
        while(__--)solve();return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/172/learning/?page=9&first_category_id=1&sort=students_count&second_category_id=3
[1ff1b4865520334502dd3c15c156a6cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a017d54171544a4eb9d19f0040f5a951.png
[- _ _lanqiao.cn 1]: https://www.lanqiao.cn/problems/182/learning/?page=6&first_category_id=1&sort=students_count&second_category_id=3&difficulty=30
[753ae677dbf771ed8aee5bb1eaf4b7d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/332f636cbba74d179b3d1a83e7a1628b.png
[b8335a09d5e47f2e206ca1fb778a8dba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d9b226513f1d44c8a8b8d484e4a32c31.png
[- _ _lanqiao.cn 2]: https://www.lanqiao.cn/problems/169/learning/?page=16&first_category_id=1&sort=students_count&second_category_id=3
[55835c51c3c19d1d8ac3ac54161d235a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4d860a74a5434283bcf4a1c23a6193f4.png
[- _ _lanqiao.cn 3]: https://www.lanqiao.cn/problems/646/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3
[137693b2ac71a08a9eabdf9a2eeea2ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4574734068474ad3b24c6fe2c3e7d593.png