时间戳

首页 > 技术文章 > 2020.10.16 Trating+2020.10.03天梯赛练习*3

2020.10.16 Trating+2020.10.03天梯赛练习*3

yy0826 2020-10-25 21:27 原文

B - Power Sequence

题意：给n个数，可以把这n个数任意排列，把数列变成一个等比数列，使第i个数变成c的i次方。可以把任意一个数加一或者减一操作，每次此类操作都要花费 1，问最少花费是多少

题解：因为n>=3，ai<=109,所以公比最大为sqrt(1e9),取1e5使ai不大于1e9.枚举公比

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
#define max 100010
typedef long long ll;
ll a[max]; 
int main(){
    ll n,flag=0,minn=1e18;
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(ll q=1;q<=1e5;q++){
        ll sum=0,m=1;
        bool flag=1;
        for(ll j=0;j<n;j++){
            if(sum>minn){
                flag=0;
                break;
            }
            sum+=abs(a[j]-m);
            m=m*q;
        }
        if(flag){
            minn=min(minn,sum);
        }else{
            break;
        }
    }
    cout<<minn<<endl;
    return 0;
}
View Code

 

D - Drinks Choosing

题意：有n个学生和k种饮料，给出n个学生最想喝的饮料，能取 [ n/2 ]组饮料，每组含相同饮料两杯，判断最多有多少学生能喝到他们最喜欢的饮料

题解：如果能拿一组使两杯饮料都有人喝肯定是最好的。把能凑成组的饮料放在sum1里，如果多出来一杯就放在sum2里，如果sum1里的数量大于等于[ n/ 2]*2，那么[ n/ 2]*2个人能喝到自己最喜欢的饮料；如果sum1的数量小于[ n/ 2]*2，那么sum1+（[ n/ 2]*2-sum1/2)能喝到自己最喜欢的饮料

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[1010];
int main(){
    int n,k,x,temp,sum1=0,sum2=0,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    temp=(n+1)/2;
    for(int i=k;i>=1;i--){
        if(a[i]%2==0){
            sum1+=a[i];
        }else{
            sum1+=a[i]-1;
            sum2+=1;
        }
    }
    if(sum1>=temp*2){
        ans=temp*2;
    }else{
        ans=sum1+(temp-sum1/2);
    }
    cout<<ans<<endl;
    return 0;
}
View Code

 

E - Sport Mafia

题意：给n次动作和最后的糖果数k。在n次动作里，你可以吃掉一颗或者在盒子里放糖果（放的糖果会比之前多放1块糖），使最后糖果数为k。如果盒子是空的只能在里面放糖；求被吃掉的糖果数.

题解：假设在n次里面有a次是放糖果，b次是吃糖果，则a+b=n;放入的糖果为（1+a）*a/2,吃掉的为b，即（1+a）*a/2+b=k 联立两个式子，求解（一开始没看见放的糖果会比之前多放1块糖，/(ㄒoㄒ)/~~）

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int main(){
    ll n,k,sum=0;
    cin>>n>>k;
    ll x=sqrt(2*n+2*k+2.25)-1.5;
    cout<<n-x<<endl;
    return 0;
}
View Code

 

F - Basketball Exercise

 题意：有两行身高数，每行n个，取过一个数之后，不能再取和它相邻的数（不包括对角相邻），问身高总和最大为多少

题解：可以先选择第一行队员，也可以选择第二行队员。要让第i次的身高和最大，第i-1次的也应该最大，且第i次可以选择也可以不选择

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAX 100010
typedef long long ll;
ll a[MAX],b[MAX];
ll dp[2][MAX];
int main(){
    ll n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    dp[0][0]=a[0];
    dp[1][0]=b[0];
    for(int i=1;i<n;i++){
        dp[0][i]=max(a[i]+dp[1][i-1],dp[0][i-1]);
        dp[1][i]=max(b[i]+dp[0][i-1],dp[1][i-1]);
    }
    ll end=max(dp[0][n-1],dp[1][n-1]);
    cout<<end<<endl;
    return 0; 
}
View Code

 7-9 小字辈 

题意：给出家族人口总数 N（不超过 100 000 的正整数）把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100010
int a[MAX] ,f[MAX];
int find(int x) {
    if(f[x]){
        return f[x];
    }
    f[x]=find(a[x])+1;
    return f[x];
}
int main(){
    int n,m,maxx=0,flag=1;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if (a[i]==-1){
            f[i]=1;
        }
    }
    for(int j=1;j<=n;j++) {
        int t=find(j);
        if(t>maxx){
            maxx=t;
        } 
    }
    cout<<maxx<<endl;
    for (int i=1;i<=n;i++) {
        if (f[i]==maxx){
            if(flag){
                flag=0;
            }else{
                cout<<" ";
            } 
            cout<<i;
        }
    }
        return 0;
}
View Code

 

推荐阅读