2020牛客寒假算法基础集训营2

这场就最后一题有点水平吧

9题打铁

简单题  就不写题解了

题目链接

C 算概率

经典概率dp

dp[i][j] 前i道题做对j个的概率

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=3e3+10;
int n;
const ll mod=1e9+7;
ll p[N],dp[N][N];
int main()
{
	cin>>n;
	rep(i,1,n) scanf("%lld",&p[i]);


	dp[0][0]=1;

	for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){

            dp[i][j+1]=(dp[i][j+1]+(dp[i-1][j]*p[i])%mod)%mod;

            dp[i][j]=(dp[i][j]+dp[i-1][j]*(1-p[i]+mod)%mod)%mod;
        }
	}

	for(int i=0;i<=n;++i) printf("%lld ",dp[n][i]);
}

D-数三角

几何做到差点崩了这盘

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
//ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=5e2+10;
const double esp=1e-6;
int n;
 
ll x[N],y[N];
 
struct Vector2
{
    ll x,y;
 
};
ll Distance(Vector2 a,Vector2 b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int Calculate(Vector2 p1, Vector2 p2, Vector2 p3)
{
    if((p1.y-p2.y)*(p1.x-p3.x)==(p1.y-p3.y)*(p1.x-p2.x))return 0;
     
    ll a = Distance(p2, p3);
    ll b = Distance(p1, p3);
    ll c = Distance(p1, p2);
 
    ll x[5];
    x[1]=a,x[2]=b,x[3]=c;
    sort(x+1,x+1+3);
    a=x[3],b=x[2],c=x[1];
 
    ll A=b+c-a;
    if(A<0) return 1;
    return 0;
}
int main()
{
    cin>>n;
    rep(i,1,n) cin>>x[i]>>y[i];
    ll ans=0;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            //if(j==i) continue;
            for(int k=j+1;k<=n;++k){
                if(Calculate({x[i],y[i]},{x[j],y[j]},{x[k],y[k]})) ans++;
            }
        }
    }
 
    cout<<ans<<endl;
}

E-做计数

做数学 题 做的差点崩盘

贴题解：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=4e7+10;
ll cal(ll x)
{
    ll ans=0;
    for(int i=1;i*i<=x;++i){
        if(x%i==0){
            ans++;
            ll d=x/i;
            if(d!=i) ans++;
        }
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    ll ans=0;
	for(int i=1;i*i<=n;++i){
        ans+=cal(i*i);
	}
	printf("%lldn",ans);
}

G-判正误

想到hash 模质数很重要，没想到这种题这么多人A，厉害了群友

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const ll mod=1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=mod;
for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int main()
{
    int _;cin>>_;while(_--)
    {
        ll a,b,c,d,e,f,g;
        cin>>a>>b>>c>>d>>e>>f>>g;
        ll ans=(powmod(a,d)+powmod(b,e))+powmod(c,f);
        //ans%=mod;
        if(ans==g) puts("Yes");
        else puts("No");
    }
}

H-施魔法

线性dp，线段树维护区间最小值即可

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=3e5+10;
const ll inf=1<<63;
int n,k;
ll dp[N];
ll a[N];
struct tree
{
    int id;
    ll mx;
}tr[N*4];
tree maxx(tree a,tree b)
{
    if(a.mx<b.mx) return a;
    return b;
}
void up(int id,int l,int r,ll val,int pos)
{
    if(l==r){
        tr[id].id=pos;
        tr[id].mx=val;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) up(id<<1,l,mid,val,pos);
    else up(id<<1|1,mid+1,r,val,pos);
    tr[id]=maxx(tr[id<<1],tr[id<<1|1]);
}
tree qu(int id,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return tr[id];
    }
    int mid=l+r>>1;
    tree t={0,inf};
    if(ql<=mid) t=qu(id<<1,l,mid,ql,qr);
    if(qr>mid) t=maxx(t,qu(id<<1|1,mid+1,r,ql,qr));
    return t;
}
int main()
{
    cin>>n>>k;
    rep(i,1,n) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<k;++i){
        up(1,1,n,inf,i);
    }
 
    for(int i=k;i<2*k-1&&i<=n;++i){
        dp[i]=a[i]-a[1];
        dp[i]-=a[i+1];
        //printf("i:%d dp:%lldn",i,dp[i]);
        up(1,1,n,dp[i],i);
    }
 
    for(int i=2*k;i<=n;++i){
        //printf("iin");
        tree now=qu(1,1,n,1,i-k);
        dp[i]=now.mx+a[i];
        dp[i]-=a[i+1];
        up(1,1,n,dp[i],i);
    }
    //rep(i,1,n) printf("dp:%lldn",dp[i]);
 
    printf("%lldn",dp[n]);
}

I-建通道

根据题意 随便分析  容易得到   将所有的数按二进制化简，按二进制 从最低位开始枚举，当某一位的0 和 1 都出现过，那么将所有的其他点就能 产生  这个位置上的答案，因为是异或。但是记得去重

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=2e5+10;
int a[N],b[N];
int vis[35][2];
int main()
{
	int n;
	cin>>n;
	rep(i,1,n) {
        cin>>a[i];
        b[i]=a[i];
	}
	sort(a+1,a+1+n);
	int len=unique(a+1,a+1+n)-a-1;
	if(len==1){
        printf("0n");
        return 0;
	}

	rep(i,1,n){
        for(int j=0;j<=30;++j)
        {
            if((a[i]&(1<<j))) vis[j][1]=1;
            else vis[j][0]=1;
        }
    }

    for(int i=0;i<=30;++i){
        if(vis[i][0]&&vis[i][1]){
            ll ans=(1ll<<i);
            printf("%lldn",ans*(len-1));
            return 0;
        }
    }
}
/*
3
3 5 7
*/

 J-求函数

这题没思路，看了题解，嗯。。很妙

贴题解：

线段树搞一搞就完事了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=2e5+10;
ll s1[4*N],s2[4*N];
ll k[N],b[N];
int n,m;
void build1(int id,int l,int r)
{
    if(l==r){
        scanf("%lld",&k[l]);
        s1[id]=k[l];
        return ;
    }
    int mid=l+r>>1;
    build1(id<<1,l,mid);
    build1(id<<1|1,mid+1,r);
    s1[id]=s1[id<<1]*s1[id<<1|1]%mod;
}
void build2(int id,int l,int r)
{
    if(l==r){
        scanf("%lld",&b[l]);
        s2[id]=b[l];
        return ;
    }
    int mid=l+r>>1;
    build2(id<<1,l,mid);
    build2(id<<1|1,mid+1,r);
    s2[id]=(s2[id<<1]*s1[id<<1|1]%mod+s2[id<<1|1])%mod;
}
void up(int id,int l,int r,int pos,ll K,ll B)
{
    if(l==r){
        k[l]=K,b[l]=B;
        s1[id]=k[l];
        s2[id]=b[l];
        //printf("更新2:s1[id]:%lld k:%lldn",s1[id],k);
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) up(id<<1,l,mid,pos,K,B);
    else up(id<<1|1,mid+1,r,pos,K,B);
    s1[id]=s1[id<<1]*s1[id<<1|1]%mod;
    s2[id]=(s2[id<<1]*s1[id<<1|1]%mod+s2[id<<1|1])%mod;
    printf("upda:s2[1]:%lld s2[id<<1]:%lld s1[id<<1|1]:%lldn",s2[1],s2[id<<1],s1[id<<1|1]);
}
ll qu1(int id,int l,int r,int ql,int qr)//查询区间乘法
{
    if(ql<=l&&r<=qr){
        return s1[id];
    }
    int mid=l+r>>1;
    ll res=1;
    if(ql<=mid) res=res*qu1(id<<1,l,mid,ql,qr)%mod;
    if(qr>mid) res=res*qu1(id<<1|1,mid+1,r,ql,qr)%mod;
    return res;
}
ll qu2(int id,int l,int r,int ql,int qr)//查询区间加法
{
    ///printf("id:%d l:%d r:%dn",id,l,r);
    if(ql<=l&&r<=qr){
        return s2[id];
    }
    int mid=l+r>>1;
    if(qr<=mid) return qu2(id<<1,l,mid,ql,qr);
    else if(ql>mid) return qu2(id<<1|1,mid+1,r,ql,qr);
    else{
        ll t1=qu2(id<<1,l,mid,ql,qr);
        ll t2=qu2(id<<1|1,mid+1,r,ql,qr);
        ll t3=qu1(id<<1|1,mid+1,r,ql,qr);
        return (t1*t3%mod+t2)%mod;
    }
    ll res=0;
    if(ql<=mid) res=res+qu2(id<<1,l,mid,ql,qr);
    res%=mod;
    if(qr>mid) res=res+qu2(id<<1|1,mid+1,r,ql,qr);
    return res%mod;
}
int main()
{
    scanf("%d%d",&n,&m);
    build1(1,1,n);
    build2(1,1,n);

    int l,r,ty,I;
    ll K,B;
    while(m--)
    {
        scanf("%d",&ty);
        if(ty==1){
            //printf("跟新n");
            scanf("%d%lld%lld",&I,&K,&B);
            up(1,1,n,I,K,B);
            //printf("s2[1]:%lldn",s2[1]);
        }
        else{
            scanf("%lld%lld",&l,&r);
            printf("%lldn",(qu1(1,1,n,l,r)+qu2(1,1,n,l,r))%mod);
        }
    }
}

最后

以上就是明亮小熊猫为你收集整理的2020牛客寒假算法基础集训营2的全部内容，希望文章能够帮你解决2020牛客寒假算法基础集训营2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。