欢乐赛#42题解

咕咕咕

2025-03-11 17:46:11

发布于：江西

16阅读

0回复

0点赞

T1

如果最大公约数为一，必然没有次大公约数
若不为一，次大公约数必然 $\ge1$

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;
int i,j,k;

int  main ( )
{
    int T;
    cin>>T;
    while(T--){
        int a,b;
        cin>>a>>b;
        int c=__gcd(a,b);
        if(c==1) cout<<-1;
        else{
            int d=0;
            for(i=1;i<c;i++){
                if(a%i==0&&b%i==0) d=i;
            }
            cout<<d;
        }
        cout<<endl;
    }
    return  0;
}

时间复杂度: $O(T\max(a,b))$

T2

若 $x\ge4$ 必然是 $4!$ 的倍数,而 $4!=24$ ,判断即可

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;
int i,j,k;

int  main ( )
{
    int x;
    cin>>x;
    if(x>=4) cout<<"YES";
    else cout<<"NO";
    return  0;
}

时间复杂度： $O(1)$

T3

简单的循环题

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;
int i,j,k;

int  main ( )
{
    int n;
    string s;
    cin>>n>>s;
    s=' '+s;
    for(i=1;i<=n;i++){
        for(j=0;j<i;j++){
            cout<<s[i];
        }
    }
    return  0;
}

时间复杂度: $O(N^{2})$

T4

康托展开的知识点，不做过多解释

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;
int i,j,k;
int fac(int n){
    int res=1;
    for(i=1;i<=n;++i) res*=i;
    return res;
}
void rem(int arr[],int& size,int index){
    for(i=index;i<size-1;++i) arr[i]=arr[i+1];
    --size;
}
void get(int n,int m){
    int num[11];
    for(int i=0;i<n;++i) num[i]=i+1;
    int per[11];
    --m;
    int numS=n;
    for(int i=n;i>0;--i){
        int fa=fac(i-1);
        int dex=m/fa;
        per[n-i]=num[dex];
        rem(num,numS,dex);
        m%=fa;
    }
    for(i=0;i<n;++i){
        if(i>0) cout<<" ";
        cout<<per[i];
    }
}
int  main ( )
{
    int n,m;
    cin>>n>>m;
    get(n,m);
    return  0;
}

时间复杂度: $O(N^{2})$

T5

每个阶乘展开成尽可能多的阶乘,注意 $9!=7!*3!*3!*2!$ ，错的几乎都是直接 $9!=9!$ 的~~我就错了~~

# include <bits/stdc++.h>
typedef unsigned long long ull;
#define lul a[dex++]=
using  namespace  std ;
int i,j,k;
int a[1000];
bool cmp_(int x,int y){
    return x>y;
}
int  main ( )
{
    string x;
    cin>>x;
    int dex=0;
    for(i=0;x[i]!='\0';i++){
        if(x[i]=='1'&&x[i]=='0') continue;
        else if(x[i]=='9'){
            lul 7;
            lul 3;
            lul 3;
            lul 2;
        }
        else if(x[i]=='8'){
            lul 7;
            lul 2;
            lul 2;
            lul 2;
        }
        else if(x[i]=='7') lul 7;           
        else if(x[i]=='6'){
            lul 5;
            lul 3;
        }
        else if(x[i]=='5') lul 5;
        else if(x[i]=='4'){
            lul 3;
            lul 2;
            lul 2;
        }
        else if(x[i]=='3') lul 3;
        else if(x[i]=='2') lul 2;        
    }
    sort(a,a+dex,cmp_);
    for(i=0;i<dex;i++){
        cout<<a[i];
    }
    return  0;
}

时间复杂度: $O(\log(x)*\log(4\log(x)))$

T6

比较坑的题目，但能过 $O(N^{2})$
思路:最小的一个一个找比他大的,直到找完,找到的标记为 $0$
其中需要 $sort$ ,还要把 $0$ 跳过

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;
int i,j,k;
int a[1000];
int  main ( )
{
    int n,ct=0,dex=0,maxi=0,dct=0;
    cin>>n;
    for(;i<n;i++) scanf("%d ",a+i);
    sort(a,a+n);
    for(i=0;i<n;i++){
        if(a[i]==0) continue;
        int p=a[i],maxi=p;
        dex=-1,dct=0;
        for(j=0;j<n;j++){
            if(a[j]>maxi){
                maxi=a[j],dex=j,dct++;
                a[dex]=0;
            }
        }
        if(dct) ct+=dct;
    }
    cout<<min(ct,n-1);
    return  0;
}