美文网首页
newcoder girl 2017题解

newcoder girl 2017题解

作者: 夏liao夏天 | 来源:发表于2019-10-01 12:30 被阅读0次

    1. 勇气获得机

    image.png

    这题使用逆序的思想,按下N按钮结果是奇数,按下G按钮,结果是偶数。因此只需要从输出的结果出发,根据结果的奇偶性倒推按下的按钮类型。

    #include <iostream>
    using namespace std;
    int main(){
        int N = 1000;
        int n;
        int count = 0;
        cin >> n;
        char s[N];
        while(n != 0){
            if(n % 2 == 0){
                n = (n-2)/2;
                s[count] = 'G';
                count = count + 1;
            }
            else{
                n = (n-1)/2;
                s[count] = 'N';
                count = count + 1;
            }
        }
        for(int i=count-1;i>=0;i--){
            cout << s[i];
        }
        return 0;
    }
    

    2. 排列

    image.png

    这题就是将数组遍历一遍,将pi = i的位置与相邻位置交换一下即可。

    #include <iostream>
    #include <math.h>
    using namespace std;
    int main(){
        int N = pow(10,5);
        int n;
        cin >> n;
        int a[N];
        int count = 0;
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
       for(int i=0;i<n;i++){
           if(a[i] == i+1 && i!= n-1){
               int temp = a[I];
               a[i] = a[i+1];
               a[i+1] = temp;
               count = count + 1;
           }
           else if(a[i] == i+1 && i== n-1){
               int temp = a[I];
               a[i] = a[i-1];
               a[i-1] = temp;
               count = count + 1;
           }
       } 
        cout << count;
        return 0;
    }
    

    3. 打车

    image.png

    这题先对硬币进行排序,从小到大将硬币加起来使得它不小于车费,再从大到小遍历,看是否能去掉一个硬币还能不小于车费。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main(){
        int n,s;
        int count;
        cin >> n;
        cin >> s;
        int N = 10+1;
        int coin[N];
        int total = 0;
        count = n;
        for(int i=0;i<n;i++){
            cin >> coin[i];
            total = total + coin[I];
            if(total >= s){
                break;
            }
        }
        std::sort(coin,coin+n);
        for(int i = n-1; i>=0; i--){
            if(total - s >= coin[I]){
                total = total - coin[I];
                count = count - 1;
            }
        }
        cout << count;
        return count;    
    }
    

    4. 勇敢的妞妞

    image.png

    因为只有5个属性,当k>=5时,只需要选出拥有某个最大属性的技能即可,这时,即使是一个技能拥有多个最大属性也不要紧,因为在计算总和的过程中只会计算最大值。当k=4时,则先遍历所有技能,找到拥有两个属性之和最大的技能,再寻找剩下的三个属性中的最大值。当k<=3时,直接遍历所有技能的可能组合,寻找最强战斗力的技能组合。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main(){
        int n,k;
        int N = 10000;
        cin >> n;
        cin >> k;
        int f[N][5];
        int t[5];
        for(int i=0;i<n;i++){
            for(int j=0;j<5;j++){
                cin >> f[i][j];
            }
        }
        if(k >= 5){
            int t = 0;
            for(int i=0;i<5;i++){
                int tmp = 0;
                for(int j=0;j<n;j++){
                    if(f[j][i] > tmp){
                        tmp = f[j][i];
                    }
                }
                t = t + tmp;
            }
            cout << t << endl;
            return t;
        }
        else if(k == 4){
            int t = 0;
            for(int i=0;i<4;i++){
                for(int j=i+1;j<5;j++){
                    int tmp = 0;
                    for(int l=0;l<n;l++){
                        if(f[l][i] + f[l][j] > tmp){
                            tmp = f[l][i] + f[l][j];
                        }
                    }
                    t = t + tmp;
                    for(int p=0;p<5;p++){
                        if(p != i && p != j){
                            int tmp = 0;
                            for(int q=0;q<n;q++){
                                if(f[q][p]>tmp){
                                    tmp = f[q][p];
                                }
                            }
                            t = t + tmp;
                        }
                    }
                }
            }
            cout << t << endl;
            return t;
        }
        else if(k == 3){
            int t = 0;
            for(int i=0;i<n-2;i++){
                for(int j=i+1;j<n-1;j++){
                    for(int l=j+1;l<n;l++){
                        int tmp = 0;
                        for(int m=0;m<5;m++){
                            tmp = tmp + max(f[i][m],max(f[j][m],f[l][m]));
                        }
                        t = max(t, tmp);
                    }
                }
            }
            cout << t << endl;
            return t;
        }
        else if(k == 2){
            int t = 0;
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    int tmp = 0;
                    for(int l=0;l<5;l++){
                        tmp = tmp + max(f[i][l],f[j][l]);
                    }
                    t = max(t, tmp);
                }
            }
            cout << t << endl;
            return t;
        }
        else if(k == 1){
            int t = 0;
            for(int i=0;i<n;i++){
                int tmp = 0;
                for(int j=0;j<5;j++){
                    tmp = tmp + f[i][j];
                }
                t = max(t, tmp);
            }
            cout << t << endl;
            return t;
        }
    }
    

    5. 平方数

    image.png

    先做开方,再做平方即可。

    #include <iostream>
    #include <math.h>
    using namespace std;
    int main(){
        int n;
        cin >> n;
        int s = sqrt(n);
        int t = s * s;
        cout << t << endl;
        return t;
    }
    

    6. 美丽的项链

    image.png

    这题采用动态规划的思想,dp[i][j]中,i代表当前可使用的宝珠种类,j代表当前所有宝珠的总数,dp[i][j]代表从i种宝珠中选取j个宝珠的方案数。dp[i][j]的值为dp[i][k] ( max(0,j-a[i]) <= k <= j)的求和。即考虑当第i种宝珠取值为0至j时,i-1种宝珠的所有可能方案。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main(){
        int n,m;
        int a[21]={0};
        long long int dp[25][105];
        cin >> n;
        cin >> m;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            int l,r;
            cin >> l;
            cin >> r;
            a[i] = r - l;
        }
        for(int i=0;i<=a[1];i++){
            dp[1][i] = 1;
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int k=std::max(0,j-a[i]);k<=j;k++){
                    dp[i][j] = dp[i][j] + dp[i-1][k];
                }
            }
        }
        cout << dp[n][m]<<endl;
        return dp[n][m];
    }
    

    相关文章

      网友评论

          本文标题:newcoder girl 2017题解

          本文链接:https://www.haomeiwen.com/subject/zdkkpctx.html