Codeforces Round #160 (Div. 1) 题解【ABCD】

时间：2022-01-24 06:15:04

Codeforces Round #160 (Div. 1)

A - Maxim and Discounts

题意

给你n个折扣，m个物品，每个折扣都可以使用无限次，每次你使用第i个折扣的时候，你必须买q[i]个东西，然后他会送你{0,1,2}个物品，但是送的物品必须比你买的最便宜的物品还便宜，问你最少花多少钱，买完m个物品

题解

显然我选择q[i]最小的去买就好了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

int a[maxn],q[maxn],n,m;

int main()

{

    long long ans = 0;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&q[i]);

    scanf("%d",&m);

    for(int i=1;i<=m;i++)scanf("%d",&a[i]);

    sort(a+1,a+1+m);

    sort(q+1,q+1+n);

    int now=m;

    while(now>0){

        for(int j=0;j<q[1];j++){

            if(now<=0)break;

            ans+=a[now];

            now--;

        }

        now-=2;

    }

    while(now>0){

        ans+=a[now];

        now--;

    }

    cout<<ans<<endl;

}

B - Maxim and Restaurant

题意

有n个人，每个人的体积是a[i]，然后这个屋子的空间是p，然后如果人们按照顺序走进去，那么期望进去多少个人呢

题解

dp[j][k]表示j个人走进去，当前空间为j的方案数

那么答案就是 $ ans+=i! * (n-i)! * dp[i][j] $

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 52;

int a[maxn],n,p;

double dp[maxn][maxn];

double cal[maxn];

int main()

{

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    scanf("%d",&p);

    cal[0]=1;

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

        cal[i]=cal[i-1]*i;

    dp[0][0]=1;

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

        for(int j=n;j>=1;j--)

            for(int k=p;k>=a[i];k--)

                dp[j][k]+=dp[j-1][k-a[i]];

    double ans = 0;

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

        for(int j=1;j<=p;j++){

            ans+=1.0*dp[i][j]*cal[i]*cal[n-i];

        }

    }

    printf("%.12f\n",ans/cal[n]);

}

C. Maxim and Matrix

题意

题目给了一段代码，你打表打出来，就会发现，题目实际上问的是:

在[2,n+1]里面，有多少个m，满足2^m = bit__count(t)

题解

典型的排列组合，慢慢搞一搞就好了，其实就是倒着枚举，然后不断让最高位置为1

代码

#include<bits/stdc++.h>

using namespace std;

long long dp[65][65];

int main()

{

    long long n,t,ans=0;

    cin>>n>>t;

    long long num=0;

    while((1LL<<num)<t)num++;

    if((1LL<<num)!=t){

        return puts("0"),0;

    }

    num++;

    if(num==1)ans--;

    n++;

    for(int i=0;i<=60;i++)

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

        {

            if(j==0)dp[i][j]=1;

            else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];

        }

    for(int i=60;i>=0;i--){

        if(num<0)break;

        if(n>=(1LL<<i)){

            ans+=dp[i][num];

            num--;

            n-=1LL<<i;

        }

    }

    if(num==0)ans++;

    cout<<ans<<endl;

}

D - Maxim and Increasing Subsequence

题意

给你长度为n的数字，然后让他重复t次，求里面的最长上升子序列长度

题解

nt <= 1e7，用树状数组，然后暴力dp就好了。。。。

然后就TLE了，剪了个枝才过去= =

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

int n,maxb,t,k,dp[maxn],b[maxn],DP[maxn];

int lowbit(int x)

{

    return x&(-x);

}

void update(int x,int y){

    for(int i=x;i<maxn;i+=lowbit(i))

        dp[i]=max(dp[i],y);

}

int query(int x){

    int Ans=0;

    for(int i=x;i;i-=lowbit(i))

        Ans=max(Ans,dp[i]);

    return Ans;

}

int main()

{

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

    t=min(t,maxb);

    while(k--){

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

            scanf("%d",&b[i]);

        memset(dp,0,sizeof(dp));

        memset(DP,0,sizeof(DP));

        for(int i=1;i<=t;i++){

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

                int tmp = query(b[j]-1);

                if(tmp>=DP[j])

                    update(b[j],tmp+1),DP[j]=tmp+1;

            }

        }

        printf("%d\n",query(maxn-1));

    }

}

相关文章