2024年中国传媒大学程序设计大赛（同步赛）赛题记录

比赛地址:https://ac.nowcoder.com/acm/contest/77526

开错题了,赛时就出了5题;
补题顺带写一下记录

A:小苯的区间和疑惑

链接:https://ac.nowcoder.com/acm/contest/77526/A
大意:给一个数组\(a\),让你对数组中每一个数\(a_i\),求包含这个数的一个区间,要求这个区间的值的和最大;

可以直接贪心,即分别从左到右,从右到左求一次最大连续子序列和(这个不会可以看看这题:https://leetcode.cn/problems/maximum-subarray/description/),
求出左右两侧(左侧用数组\(l\)记录,右侧用数组\(r\)记录,看你喜欢怎么记)的最大子序列和后,直接\(a_i\)+\(l_{i-1}\)+\(r_{i+1}\)就可以得出答案,复杂度为\(O(n)\);

AC代码:

// author:manjuan
//
#include <bits/stdc++.h>
#define N 1001
using namespace std;
using ll = long long;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll n;
    cin>>n;
    vector<ll> v(n+2),sum(n+2),l(n+2),r(n+2);;
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=1;i<=n;i++){
        l[i]=v[i]+l[i-1];
        if(l[i]<0)l[i]=0;
        //cout<<l[i]<<" ";
    }//cout<<"\n";
    for(int i=n;i>0;i--){
        r[i]=v[i]+r[i+1];
        if(r[i]<0)r[i]=0;
    }
    for(int i=1;i<=n;i++){
        sum[i]=v[i]+l[i-1]+r[i+1];
        cout<<sum[i]<<" ";
    }
}

B:小苯的三元组

链接:https://ac.nowcoder.com/acm/contest/77526/B
大意:给你一个n和一个长度为n的数组a,让你找满足条件\(lcm\)(\(a_i\),\(a_j\))\(\leq\)\(gcd\)(\(a_j\),\(a_k\))\(的三元组(\)a_i\(,\)a_j\(,\)a_k$)的数量。

赛时没出,其实不难想到:由于值域为\(1\)到\(2\)x\(10^5\),所以可以用桶(用数组a来存,也可以用map或者unordered_map,这里开int数组可以存下,但是数据量最大到\(2\)x\(10^5\),数据设置特殊一点是可以卡爆int的,所以得开long long)去装每一个数的个数;然后对于每一个在\(1\)到\(2\)x\(10^5\)间的i都跑一个三层循环(此循环实际上复杂度为调和级数级,即约\(n\)\(logn\)),
然后对于每一个\(a_i\),找为其整数倍的\(a_j\),对于每一个\(a_j\),找为其整数倍的\(a_k\)\(a_i\)、\(a_j\)、\(a_k\)的数量之积的和即为答案;

AC代码(实际上还可以再优化,但不优化也才跑87ms)

// author:manjuan
//
#include <bits/stdc++.h>
#define N 200005
using namespace std;
using ll = long long;

ll a[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll n,ans{0};
    cin>>n;

    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<N;i++){
        for(int j=i;j<N;j+=i){
            for(int k=j;k<N;k+=j){
                //if(a[i]&&a[j]&&a[k]){
                //    cout<<i<<" "<<j<<" "<<k<<endl;
                //}
                ans+=(a[i]*a[j]*a[k]);
            }
        }
    }
    cout<<ans<<"\n";
}