2023牛客寒假算法基础集训营4 题解

2023/6/15 C++ 算法竞赛 题解 牛客 寒假算法集训营 2023

补几道

A. 清楚姐姐学信息论

题面

非常有意思的一道题，乍一看肯定是低进制效率高，但被WA教训之后开始冷静思考

进制与 进制比较效率， 张号码牌在 进制下是 位， 进制下是 位

分别能表示的数的个数为 和

现在就是比较这两个数的大小

因为 ， 都大于 ，可以取对数，大小关系不变

即比较 与 的大小关系

即比较 与 的大小关系

同构，构造函数

, 在 上增，在 上减

所以 ，即 最大，而 ，所以可以得出全部的大小顺序

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    ll x,y;
    cin>>x>>y;
    if(x==3||y==3)
        cout<<3<<'\n';
    else
        cout<<min(x,y)<<'\n';
    return 0;
}

B. 清楚姐姐学构造

题面

由题意可知：


所以 ,

如果 ，那么可能无解，需要判断一下

如果 ，那么 ， 在模 下有逆元，找出逆元乘一下就行

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll c[N];
void Exgcd(ll a,ll b,ll &x,ll &y){
    if(!b) x=1,y=0;
    else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int inverse(ll a,ll p){
    ll x, y;
    Exgcd (a,p,x,y);
    x=(x%p+p)%p;
    return x; 
}
int main() {
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    if(m==2)
    {
        bool flag=false;
        for(int i=1,j=n;i<=j;i++,j--)
        {
            if((c[i]+c[j])%2!=0)
            {
                flag=true;
                break;
            }
        }
        if(flag)
            cout<<"No"<<'\n';
        else
        {
            cout<<"Yes"<<'\n';
            for(int i=1;i<=n;i++)
                cout<<c[i]<<' ';
            cout<<'\n';
            for(int i=1;i<=n;i++)
                cout<<0<<' ';
            cout<<'\n';
        }
    }
    else
    {
        cout<<"Yes"<<'\n';
        ll s=inverse(2,m);
        for(int i=1;i<=n;i++)
            cout<<(c[i]+c[n+1-i])%m*s%m<<' ';
        cout<<'\n';
        for(int i=1;i<=n;i++)
            cout<<(c[i]-c[n+1-i]+m)%m*s%m<<' ';
        cout<<'\n';
    }
    return 0;
}

E. 清楚姐姐打怪升级

题面

模拟一下就行

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int h[N],v[N];
ll ceil(ll x,ll y)
{
    if(x%y==0)
        return x/y;
    return x/y+1;
}
int main() {
    ios::sync_with_stdio(false);
    int n,t,a;
    cin>>n>>t>>a;
    bool flag=false;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i]>>v[i];
        if(v[i]*t>=a&&h[i]>a)
            flag=true;
    }
    if(flag)
        cout<<-1<<'\n';
    else
    {
        ll cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(h[i]>=a&&v[i]*t<a)
                cnt+=ceil(h[i]-a,a-v[i]*t)+1;
            else
                cnt++;
        }
        cout<<1+(cnt-1)*t<<'\n';
    }
    return 0;
}

L. 清楚姐姐的三角形I

题面

直接能算出来，判断一下就行

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v[3];
ll l[3];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll sum=0;
        for(int i=0;i<3;i++)
        {
            cin>>v[i];
            sum+=v[i];
        }
        if(sum%2!=0)
            cout<<"No"<<'\n';
        else
        {
            sum/=2;
            for(int i=0;i<3;i++)
                l[i]=sum-v[i];
            sort(l,l+3);
            if(l[0]+l[1]>l[2])
            {
                cout<<"Yes"<<'\n';
                for(int i=0;i<3;i++)
                    cout<<sum-v[i]<<' ';
                cout<<'\n';
            }
            else
                cout<<"No"<<'\n';
        }
    }
    return 0;
}

M. 清楚姐姐的三角形II

题面

显然有循环，构造 1,2,4,1,2,4,...这样就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int v[3]={1,2,4};
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cout<<v[(i-1)%3]<<' ';
    cout<<'\n';
    return 0;
}
img_show