编程新星挑战赛-题解

签到题？？？

排序：先将输入的三个边长进行从小到大的排序。

三角形不等式：判断排序后的最小两个边$a$和$b$之和是否大于最大边$c$。如果不满足三角形不等式，输出“NO”并结束程序。

计算周长和面积：

• 如果满足三角形不等式，输出“YES”。
• 使用周长公式计算三角形的周长$a+b+c$。
• 使用海伦公式求面积：先计算半周长$s=(a+b+c)/2$，再计算面积$sqrt(s\ast (s-a)\ast (s-b)\ast (s-c))$，并将面积输出到小数点后两位。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){double a,b,c;cin>>a>>b>>c;//比较大小 double tmp;if(a>b){tmp=a;a=b;b=tmp;}if(b>c){tmp=b;b=c;c=tmp;}if(a+b>c){cout<<"YES"<<endl;cout<<"周长："<<a+b+c<<endl;//海伦公式double s=(a+b+c)/2;double res=sqrt(s*(s-a)*(s-b)*(s-c));printf("面积：%.2lf",res);}else cout<<"NO";return 0;
}

分糖果

博弈策略：此问题是巴什博弈问题的应用。巴什博弈的结论是，如果$n$，先手（小红）必输；否则，先手可以通过合理选择获胜。

实现：

• 输入数字$n$（糖果数量）。
• 判断$n$是否等于0，如果是，则输出“小红”（表示小红会输）；否则输出“小明”（表示小明会赢）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){int n;cin>>n;if(n%4==0)cout<<"小红";else cout<<"小明"; return 0;
}

理解字符串，成为字符串，超越字符串

输入和分段：输入字符串长度$n$，字符串内容，以及字符$x$和$y$。然后将字符串分为前半段和后半段。

不同情况的处理：

• 如果字符$x$和$y$不相同，将字符串的前半部分替换为$x$，后半部分替换为$y$。
• 如果$x$和$y$相同，则全字符串用相同字符替换。

计数：统计替换后字符不符合预期的字符数量$f$和预期字符对数$w$，输出最终结果。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define int long long
signed main()
{IOS;int n;string a;cin>>n;cin>>a;char x,y;cin>>x>>y;int f=0,w=0;if(x!=y){if(n%2==1){for(int i=0;i<n/2;i++){if(a[i]!=x)f++;}for(int i=n/2+1;i<n;i++){if(a[i]!=y)f++;}if(a[n/2]!=x||a[n/2]!=y){f++;}w=(n/2+1)*(n/2);}else{for(int i=0;i<n/2;i++){if(a[i]!=x)f++;}for(int i=n/2;i<n;i++){if(a[i]!=y)f++;}w=(n/2)*(n/2);}}else{for(int i=0;i<n;i++){if(a[i]!=x){f++;}}w=(n-1)*n/2;}cout<<w<<" "<<f;return 0;
}

来玩牌吧

输入牌组：以字符串形式输入一组牌，每张牌用三个字符表示（花色和编号）。

判断重复：对每张牌，检查是否在组内重复。若找到相同花色和编号的牌，输出“Lois”并结束程序。

计算缺失数量：若无重复，统计每种花色缺失的牌数，并输出四种花色分别还缺少多少张牌。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){char s[100];int i=0,j=0,q=0,w=0,e=0,r=0,G=0,m=0;scanf("%s",s);for(i=0;s[i]!='\0';i=i+3){for(j=i;s[j]!='\0';j=j+3){if(i!=j&&s[i]==s[j]&&s[i+1]*10+s[i+2]==s[j+1]*10+s[j+2]){	//相同条件 printf("Lois");G++;}}}for(m=0;s[m]!='\0'&&G==0;m=m+3){//统计每个花色出现个数 if(s[m]=='S')q++;if(s[m]=='H')w++;if(s[m]=='D')e++;if(s[m]=='C')r++;}
if(G==0)printf("%d %d %d %d",13-q,13-w,13-e,13-r);return 0;
}

津津能买到吗？

模拟每月花费和存款：

• 每月津津获得300元生活费，扣除当月花费后剩下的余额。
• 若余额大于100，按100的倍数存入妈妈账户，并产生20%利息，剩余部分留到下个月。

判断购买能力：

• 计算总存款（本金 + 利息），判断是否大于或等于商品价格。
• 若满足条件输出“YES”，否则输出“NO”。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){int n, sum = 0, save = 0;int cost[12];cin >> n;for (int i = 0; i < 12; i++) {cin >> cost[i];save = 300 + save - cost[i];if (save >= 0) {//sum是存在妈妈那里的整百//save是津津存完剩下的钱 sum += save / 100;save %= 100;}}//计算利息+本金 int money = sum * 100 * 1.2 + save;cout << money << endl;if (money >= n) cout << "YES";else cout << "NO";return 0;
}

乐于助人

深度优先搜索生成括号组合：用递归生成所有符合括号规则的组合，记录左括号数量ls和右括号数量rs。

递归条件：

• 当ls < rs或ls > n或rs > n时终止当前递归。
• 若ls == rs == n，则将生成的组合记录在结果集res中。

输出结果：对结果集按字典序排序并输出所有符合条件的括号组合。

	#include<bits/stdc++.h>using namespace std;#define int long longvector<string> res;int num=0;void dfs(int n,int ls,int rs,string answer){//退出条件//退出条件看左括号和右括号的个数if(ls<rs||ls>n||rs>n)return;if(ls==rs&&ls==n){//一次深搜成功，储存答案res.push_back(answer);num++;return; } dfs(n,ls+1,rs,answer+'[');dfs(n,ls,rs+1,answer+']');}signed main(){//用一个二维数组储存]int n;cin>>n;int ls=0,rs=0;dfs(n,ls,rs,""); sort(res.begin(),res.end());int cnt=0;//处理最后一位的逗号输出 cout<<num<<endl;cout<<"{";for(auto i:res){cout<<"'";cout<<i;cout<<"'";cnt++;if(cnt!=num)cout<<", ";}cout<<"}";return 0;}

学长的RPG游戏

输入属性：读取两个角色的基础伤害值（无暴击）、暴击伤害倍数和暴击率。

计算预期输出：计算期望输出值（无暴击伤害 + 暴击伤害 * 暴击率）。

比较输出强度：通过比较期望输出值，判断哪个角色的输出更高并输出胜者名称。

#include<stdio.h>
int main(){int a,b,c,d,i,j,k;scanf("%d%d%d%d",&a,&b,&c,&d);k=(100-a)+a*b;j=(100-c)+c*d;if(k<j)printf("YES");elseprintf("NO");return 0;
}

方阵

定义边界：定义初始矩阵边界top、bottom、left和right。

填充矩阵：从左上角开始顺时针填充数字。每填满一条边后调整边界，循环直至填满整个矩阵。

输出矩阵：最后输出填充后的矩阵。

#include<iostream>
using namespace std;
int shix[1010][1010];
int main(){int n,k;cin>>n>>k;int location=k-1;//起始声明，四个边界int top=1,bottom=n,left=1,right=n;int l,r,b,t;while(location<n*n+k-1){t=left;while(t<=bottom){shix[t][left]=++location;t++;}left++;l=left;while(l<=right){shix[bottom][l]=++location;l++;}bottom--;b=bottom;while(b>=top){shix[b][right]=++location;b--;}right--;l=right;while(l>=left){shix[top][l]=++location;l--;}top++;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<shix[i][j]<<" ";}cout<<endl;}
}

对称美学

判断素数：创建函数检查数字是否为素数，通过6k±1法则（即除2和3外，所有素数位于6k±1位置）提升效率。

判断回文数：将数字转成字符串，检查首尾字符是否相同，逐位比较直到中心。

统计结果：对所有小于等于$n$的数逐一判断并计数，将满足条件的数量作为结果输出。

#include<iostream>
using namespace std;
int res=0;
//判断素数
bool key1(int num){if (num <= 1) return false;if (num <= 3) return true;if (num % 2 == 0 || num % 3 == 0) return false;for (int i = 5; i * i <= num; i += 6) {if (num % i == 0 || num % (i + 2) == 0) return false;}return true;
} 
//判断回文数 
bool key2(int num){string str=to_string(num);//转化为字符串函数int l=0,r=str.length()-1;while(l<r){if(str[l]!=str[r])return false;else {l++;r--;}} return true;
}
int main(){int n;cin>>n;for(int i=2;i<=n;i++){if(key1(i)&&key2(i)){res++;}}cout<<res;
}

题目的难度

1. 结构体+排序
   • 使用结构体存储题目编号和分值，输入每道题的分值。
   • 使用排序函数sort对题目按分值从小到大排序。
2. 输出结果：按排序后顺序输出题号。

不使用结构体的解法：

1. 使用数组存储题目分值。
2. 逐步扫描题号并按分值升序输出。

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef struct q{char a;//题号 int b;//分值 
}shix;
bool cmp(shix n,shix m){return  n.b<m.b;
}
int main(){shix arr[20];char ch='A';for(int i=0;i<12;i++){arr[i].a=ch;ch++;int n;cin>>n;//分值arr[i].b=n; }sort(arr,arr+12,cmp);for(int i=0;i<12;i++){cout<<arr[i].a<<" ";}return 0;
}

不用sort和结构体的做法

#include <bits/stdc++.h>
using namespace std;
int arr[12];
int main(){for(int i=0;i<12;i++){cin>>arr[i];}for(int i=1;i<=10;i++){for(int j=0;j<12;j++){if(arr[j]==i){cout<<(char)('A'+j)<<' ';}}}return 0;
}

李华的数学作业

求约数和：对1至$n$的每个数，计算其约数之和，将每个数的约数和存储为该数的“价值”。

动态规划解决：

• 使用01背包算法计算不同物品组合下的最大价值。
• 最终输出背包容量为$n$的最大价值。

#include <bits/stdc++.h>
using namespace std;
#define int long long		//全局定义int 为long long类型
#define db double 
const int inf = 0x3f3f3f3f;
const int MOD = 1e7+7; 
const int N = 1e5+10;
int w[N];
int res[N];
void solve(){	//01背包问题int n;cin>>n;		//n相当于背包容量，for(int i=1;i<=n;i++)		//1~n每个数就相当于一个商品，数本身的大小就像当是商品的体积，for(int j=1;j<=i/j;j++)if(i%j==0){w[i]+=j;				//每个数的约数之和就是商品价值if(j!=i/j) w[i]+=i/j;}for(int i=1;i<=n;i++)for(int j=n;j>=i;j--)res[j]=max(res[j],res[j-i]+w[i]);cout<<res[n];
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
} 

Minimum number of operations

处理思路：将一个整数递减或除2，直到变为0。

实现方法：如果当前数为偶数则除2，否则减1，直到剩余数为1或2，输出最终操作次数。

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int num=0; //如果输入为0则直接输出0if(n==0){cout<<0;return 0;}//如果输出部位1或2，则一直反复迭代应该是-1还是/2while(!(n==2||n==1)){if(n&1) num++,n--;else {num++;n=n>>1;}}//从1或2到0都只需要1个操作数cout<<num+1;
}