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];
}