2020牛客寒假算法基础集训营2 J题可以回顾回顾

时间：2022-07-27 04:36:53

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

A.做游戏

这是个签到题。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 5e5 + ;

typedef long long ll;

int main(){

    ll a,b,c,x,y,z;

    cin>>a>>b>>c>>x>>y>>z;

    printf("%lld\n",min(a,y)+min(b,z)+min(x,c));

    return ;

}

A

B.排数字

这也是个签到题。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 5e5 + ;

typedef long long ll;

char s[maxn];

int main(){

    int n;

    scanf("%d%s",&n,s+);

    int num1=,num6=;

    for(int i=;i<=n;i++){

        int x=s[i]-'';

        if(x==) num1++;

        if(x==) num6++;

    }

    printf("%d\n",min(num1,num6-));

    return ;

}

B

C.算概率

这是一个概率dp。

dp[i][j] 表示前面i个题目做出了j个的概率

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

这个题目卡了我一会，很少写概率dp，不太会写。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e3 + ;

typedef long long ll;

const int mod=1e9+;

const int maxs=1e9+;

ll dp[maxn][maxn],p[maxn];

int main(){

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lld",&p[i]);

    dp[][]=;

    for(int i=;i<=n;i++){

        for(int j=;j<=i;j++){

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

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

            dp[i][j]%=mod;

        }

    }

    for(int i=;i<=n;i++){

        printf("%lld ",dp[n][i]);

    }

    return ;

}

C

D.数三角

这个就是一个余弦定理，注意判断能否构成三角形。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e3 + ;

typedef long long ll;

const int mod=1e9+;

const int maxs=1e9+;

const long double eps=1e-;

long double x[maxn],y[maxn];

long double dis(int i,int j){

    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

}

long double deal(long double a,long double b,long double c){

    return (b*b+c*c-a*a)/(*b*c);

}

int main(){

    int n,ans=;

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%Lf%Lf",&x[i],&y[i]);

    for(int i=;i<=n;i++){

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

            for(int k=j+;k<=n;k++){

                long double a=dis(i,j),b=dis(j,k),c=dis(i,k);

                long double num1=deal(a,b,c),num2=deal(b,c,a),num3=deal(c,a,b);

                if(b+c<=a) continue;

                if(a+c<=b) continue;

                if(b+a<=c) continue;

                if(num1<||num2<||num3<) ans++;

            }

        }

    }

    printf("%d\n",ans);

    return ;

}

D

E.做计数

这个平方一下就知道要满足i*j 是一个平方数才行，所以枚举所有的平方数，

然后求出每一个平方数的约数即可，这平方数的约数个数就是[i,j]的组数。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e4 + ;

typedef long long ll;

int v[maxn],isp[maxn],m;

void init1()

{

    for(int i=;i<maxn;i++){

        if(v[i]==){

            isp[m++]=i;

            v[i]=i;

        }

        for(int j=;j<m;j++){

            if(v[i]<isp[j]||i*isp[j]>maxn) break;

            v[i*isp[j]]=isp[j];

        }

    }

}

int main(){

    init1();

    int ans=,n;

    scanf("%d",&n);

    for(ll i=;i*i<=n;i++){

        ll x=i*i,res=;

        for(int j=;j<m;j++){

            int p=;

            while(x%isp[j]==) x/=isp[j],p++;

            res*=p;

        }

        ans+=res;

    }

    printf("%d\n",ans);

}

E

F.拿物品

这个是一个贪心，这个贪心把我人绕晕了，差点没有反应过来。

对于一个物品，我们不仅需要a越大越好，而且b也越大越好，所以应该按照a+b排序。

可以理解为，如果a越大自己得到的就越多，如果b越大，那么别人失去的也就越多，所以a+b越大越好。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e5 + ;

typedef long long ll;

struct node{

    ll a,b,d,id;

}w[maxn],v[maxn];

int ans1[maxn],ans2[maxn],vis[maxn];

bool cmp(node a,node b){

    return a.b+a.a>b.a+b.b;

}

int main(){

    int n,cnt1=,cnt2=;

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lld",&w[i].a),w[i].id=i;

    for(int i=;i<=n;i++) scanf("%lld",&w[i].b);

    sort(w+,w++n,cmp);

    for(int i=;i<=n;i+=){

        ans1[++cnt1]=w[i].id;

        if(i==n) break;

        ans2[++cnt2]=w[i+].id;

    }

    for(int i=;i<cnt1;i++) printf("%lld ",ans1[i]);

    printf("%lld\n",ans1[cnt1]);

    for(int i=;i<cnt2;i++) printf("%lld ",ans2[i]);

    printf("%lld\n",ans2[cnt2]);

    return ;

}

F

G.判正误

这个题目知道是哈希就很简单了。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e3 + ;

typedef long long ll;

const int mod=;

ll quick_pow(ll a,ll b,ll mod)

{

    ll ans = ;

    while(b)

    {

        if (b & ) ans = (ans*a)%mod;

        a = (a*a)%mod;

        b >>= ;

    }

    return ans;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        ll a,b,c,d,e,f,g;

        cin>>a>>b>>c>>d>>e>>f>>g;

        ll num1=quick_pow(a,d,mod),num2=quick_pow(b,e,mod),num3=quick_pow(c,f,mod);

        ll num=(num1+num2+num3)%mod;

        if(num==g%mod) printf("Yes\n");

        else printf("No\n");

    }

}

G

H.施魔法

这个题目是一个类似于线段树优化dp，但是我不太会写，因为自己想的有点复杂了。

其实写法很简单，这个是我看lj的代码写的，以后可以再看看。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 3e5 + ;

typedef long long ll;

ll mins[maxn*],a[maxn];

void build(int id,int l,int r){

    mins[id]=inf64;

    if(l==r) return ;

    int mid=(l+r)>>;

    build(id<<,l,mid);

    build(id<<|,mid+,r);

}

void push_up(int id){

    mins[id]=min(mins[id<<],mins[id<<|]);

}

ll query(int id,int l,int r,int x,int y){

    if(y<l||x>r) return inf;

    if(x<=l&&y>=r) return mins[id];

    ll ans=inf,mid=(l+r)>>;

    if(x<=mid) ans=min(ans,query(id<<,l,mid,x,y));

    if(y>mid) ans=min(ans,query(id<<|,mid+,r,x,y));

    return ans;

}

void modify(int id,int l,int r,int pos,ll val){

    if(pos<l||pos>r) return ;

    if(l==r){

        mins[id]=val;

        return ;

    }

    int mid=(l+r)>>;

    if(pos<=mid) modify(id<<,l,mid,pos,val);

    else modify(id<<|,mid+,r,pos,val);

    push_up(id);

}

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++) scanf("%lld",&a[i]);

    sort(a+,a++n);

    for(int i=;i<=n;i++){

        ll x=a[i]-a[];

        x=min(x,a[i]+query(,,n,k,i-k));

        if(i==n) printf("%lld\n",x);

        else modify(,,n,i,x-a[i+]);

    }

    return ;

}

H

I.建通道

这个可以说是一个简单题了，首先判断出数字的种类，因为如果数字相同可以0花费连在一起，

然后判断出奇偶，如果有奇数也有偶数，那么答案就是数字种类数-1

如果都是偶数，那就整体右移一位，ans*=2,这个时候有奇数有偶数的话，答案就是（种类数-1)*ans【ans的初始化为1】

J.求函数

这也是一个线段树，不过我不是很会写，后来看了题解发现就是如何合并两个区间。

这个题解说的很详细。https://ac.nowcoder.com/discuss/364961?type=101&order=0&pos=1&page=3

这个以后可以再看看。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 2e5 + ;

const int mod=1e9+;

ll sum1[maxn*],sum2[maxn*],k[maxn],b[maxn];

void push_up(int id){

    sum1[id]=sum1[id<<]*sum1[id<<|]%mod;

    sum2[id]=(sum1[id<<|]*sum2[id<<]%mod+sum2[id<<|]%mod)%mod;

}

void build(int id,int l,int r){

    if(l==r){

        sum1[id]=k[l];

        sum2[id]=b[l];

        return ;

    }

    int mid=(l+r)>>;

    build(id<<,l,mid);

    build(id<<|,mid+,r);

    push_up(id);

}

void modify(int id,int l,int r,int pos,ll k,ll b){

    if(l==r){

        sum1[id]=k%mod;

        sum2[id]=b%mod;

        return ;

    }

    int mid=(l+r)>>;

    if(pos<=mid) modify(id<<,l,mid,pos,k,b);

    else modify(id<<|,mid+,r,pos,k,b);

    push_up(id);

}

ll ans;

void query(int id,int l,int r,int x,int y){

    if(x<=l&&y>=r){

        ans=(ans*sum1[id]%mod+sum2[id])%mod;

        return ;

    }

    int mid=(l+r)>>;

    if(x<=mid) query(id<<,l,mid,x,y);

    if(y>mid) query(id<<|,mid+,r,x,y);

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%lld",&k[i]);

    for(int i=;i<=n;i++) scanf("%lld",&b[i]);

    build(,,n);

    while(m--){

        ll k1,b1;

        int opt,i,l,r;

        scanf("%d",&opt);

        if(opt==){

            scanf("%d%lld%lld",&i,&k1,&b1);

            modify(,,n,i,k1,b1);

        }

        else{

            ans=;

            scanf("%d%d",&l,&r);

            query(,,n,l,r);

            printf("%lld\n",ans);

        }

    }

    return ;

}

J

相关文章