2020年8月月赛——上海市计算机学会竞赛平台
T1
促销筛子
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c ;
if (a == 6) {
if (b == 6) {
if (c == 6) {
cout << "1000";
} else {
cout << "100";
}
} else {
cout << "10";
}
} else {
cout << "0";
}
return 0;
}T2
汽水兑奖
#include <bits/stdc++.h>
using namespace std;
int cnt;
int main() {
int a,b,c;
cin>>a>>b>>c;
int qa=a,qb=a;
cnt=a;
while (qa>0&&qb>0){
if (qa<b&&qb<c)break;
if (qa>=b){
qa-=b;
cnt++,qa++,qb++;
}
if (qb>=c){
qb-=c;
cnt++,qa++,qb++;
}
}
cout<<cnt;
return 0;
}T3
古董鉴定
本题思路：【用所有古董的最高属性，当作判定的依据，可以减少重复计算的次数】
输入古董属性时，一并求出三种属性的最大值。然后遍历古董，如果古董的三个属性均满足差值不超过100（小于等于100），则它不是赝品。用一个数组记录真品的序号。只需要一次遍历就可以求出所有的真品。时间复杂度O(n).
#include<bits/stdc++.h>
using namespace std;
int maxa=-1,maxb=-1,maxc=-1,k=0;
struct f{
string name;
int a,b,c;
}cnt[1000100];
string ans[1000100];//真品
int main(){
int n;
cin>>n;
for (int i=0;i<n;i++){
cin>>cnt[i].name>>cnt[i].a>>cnt[i].b>>cnt[i].c;
maxa=max(maxa,cnt[i].a);
maxb=max(maxb,cnt[i].b);
maxc=max(maxc,cnt[i].c);
}
for (int i=0;i<n;i++){
if (maxa-cnt[i].a<100&&maxb-cnt[i].b<100&&maxc-cnt[i].c<100){
ans[k]=cnt[i].name;
k++;
}
}
if (k==0)cout<<"There is no winner.";
else {
cout<<"Winning list:"<<endl;
for (int i=0;i<k;i++){
cout<<ans[i]<<endl;
}
}
return 0;
}T4
魔法球
本题思路：求最少改色次数，那么我们可以优先修改出现颜色次数少的球，这样可以花费最小的代价，减少颜色的种类数。
创建一个计数数组，统计每种颜色的数量，排序计数数组。从左往右遍历值非0的项目，计算将颜色修改为k种的数量即可。
#include<bits/stdc++.h>
using namespace std;
int a[201000],cnt[200100],sum=0,cmp=0;
int main(){
int n,k;
cin>>n>>k;
for (int i=0;i<n;i++){
cin>>a[i];
cnt[a[i]]++;
}
sort(cnt+1,cnt+n+1);
for (int i=1;i<=n;i++){
if (cnt[i]!=0)cmp++;
}
k=cmp-k;
for (int i=1;i<=n;i++){
if (k==0)break;
if (cnt[i]!=0){
sum+=cnt[i];
k--;
}
}
cout<<sum;
return 0;
}
T5
分形三角
本题思路：假定有一个能绘制分形三角的函数。dfs(int k, int x, int y) 。k为层数x,y为顶点坐标。
【分解方式】一个分形三角可以由三个分形三角构成。
【边界条件】 当k == 1时，不能再分解。
综上，利用递归求出分形三角的形状，存储到二维数组中，最后打印值。
#include <bits/stdc++.h>
using namespace std;
char a[5000][5000];
void dfs(int k, int x, int y) {//第k层
if (k == 1) {
a[y][x] = '/';
a[y][x + 1] = '\\';//有斜杠需要打两个
a[y + 1][x - 1] = '/';
a[y + 1][x] = '_';
a[y + 1][x + 1] = '_';
a[y + 1][x + 2] = '\\';
} else {
dfs(k - 1, x, y);//递归上边的三角形
dfs(k - 1, x - pow(2, k - 1), y + pow(2, k - 1));//递归左下的三角形
dfs(k - 1, x + pow(2, k - 1), y + pow(2, k - 1));//递归右下的三角形
}
}
int main() {
int n;
cin >> n;
dfs(n, pow(2, n), 1);
int h = pow(2, n),w = pow(2, n + 1);
for (int i=1;i<=h;i++) {
for (int j=1; j<=w;j++) {
if (a[i][j]==0) {
cout<<" ";
} else {
cout << a[i][j];
}
}
cout << endl;
}
return 0;
}感谢陈厚节老师提供思路
看了这么久，作者也写了这么久，能不能点一个赞，在收藏一下呢？最好的话在点个关注吧
谢谢啦！
原文地址：https://blog.csdn.net/CylMK/article/details/136531019
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！