牛客周赛(Round 25)题解

题目A链接

题解:定义long long类型变量，遍历一遍出结果

#include<stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    long long a[1001];
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    char s[n];
    scanf(" %s",&s);
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]=='F'){
            if(a[i]/100>5)
                ans+=a[i]/100;
            else
                ans+=5;
        }else{
            ans+=a[i];
        }
    }
    printf("%lld",ans);
}

题解: 求两个最大乘积之和，优先使乘积最大，而不是和最大，将两个乘积其中之一最大，另一个最小就行。定义long long类型变量，遍历一遍出结果，每次循环乘积都取余一次，最后和取余一次，防止溢出。

#include<stdio.h>
int a[100000];
int b[100000];
long long yu=1000000007;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    long long ans1=1,ans2=1;
    for(int i=0;i<n;i++){
        if(a[i]<b[i]){
            ans1*=b[i];
            ans2*=a[i];
        }else{
            ans1*=a[i];
            ans2*=b[i];
        }
        ans1%=yu;
        ans2%=yu;
    }
    printf("%lld",(ans1+ans2)%yu);
}

题目C链接

?题解:定义long long类型变量，用贪心算法求解。优先使用高伤害技能攻击高血量敌人，为了最少法力值消耗，每次循环执行时，先判断敌人血量是否大于技能造成的伤害，每次计算三个敌人血量于技能伤害的倍数，取最小倍数，一次循环可以释放多次技能，提高算法效率。高伤害技能全释放过后，再执行一次循环，保证所有敌人血量清空。之所以从后往前遍历，是因为高伤害技能的伤害是递增的，倒序可以优先击败高血量敌人，节省法力值消耗。

#include<stdio.h>
long long mp;
long long a[100001];
int Min(int a,int b,int c){
    return a>b?(b>c?c:b):(a>c?c:a);
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    mp=0;
    for(int i=n-3;i>=0;i--){
        if(a[i]>=1&&a[i+1]>=2&&a[i+2]>=3){
            int ratio=Min(a[i],a[i+1]/2,a[i+2]/3);
            mp+=5*ratio;
            a[i]-=ratio;
            a[i+1]-=2*ratio;
            a[i+2]-=3*ratio;
        }
    }
    for(int i=0; i<n; i++)
        mp+=a[i];
    printf("%lld",mp);
}

题目D链接

好像用线段树模板可以AC，但是博主不会。二叉树之前学的不深，等寒假再学。