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