湖南师范大学2018年大学生程序设计竞赛新生赛（部分题解）

2023-11-08 11:10
文章标签 竞赛 部分 大学生 程序设计 2018 题解 新生 湖南师范大学

本文主要是介绍湖南师范大学2018年大学生程序设计竞赛新生赛（部分题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.齐神与新美的游戏

题目描述

某一天齐木楠雄和照桥心美一起玩找数字的游戏,游戏规则是这样的,桌子上有n个的卡片，每一张卡片上都有一个独一无二的数字,心美从中选择三次(可以重复选择同一张卡片),然后得到一个数为三张卡片上数字之和,如果卡片上的数字之和恰好为k,那么心美获胜,否则齐神获胜。如果心美获胜了，齐神只能乖乖的听从心美的要求说出"哦呼了"。但是众所周知的是，心美是神的女儿，只要如果场面上存在任意一种使得和为k的方案，那么心美一定能选中这三张牌。

输入描述:

对于每一个案例,我们第一行包括两个整数n,k(1<=n<=3000,1<=k<=3e5),表示有n个数字,目标和为k。第二行输入n个整数(c1 c2...cn),(1<=ci<=1e5),表示每一张卡片上的数字。

输出描述:

如果心美能够顺利的抽出三张牌使得和恰好为k，那么输出“o hu~”,否则输出“wo yo wo yo~”。
示例1

输入

4 7
1 2 3 4

输出

o hu~
示例2

输入

5 16
1 2 3 4 5

输出

wo yo wo yo~
思路：最好想的肯定是暴力，但暴力大概要9*10^9这么大，肯定是会爆掉的，所以使用小小的优化，在三重枚举上的优化是有局限性的，所以用一个比较常用的优化最后一层枚举。

代码如下：

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int p[100005],vis[100005];
int main()
{int n,k,i,j;scanf("%d%d",&n,&k);for(i=0;i<n;i++){scanf("%d",&p[i]);vis[p[i]]=1;}for(i=0;i<n;i++){for(j=0;j<n;j++){if(p[i]+p[j]>=k)continue;if(vis[k-p[i]-p[j]]==1){printf("o hu~\n");return 0;}} }printf("wo yo wo yo~\n");return 0;
}

B.齐神与心美的游戏2

题目描述

某一天齐木楠雄和照桥心美又在一起玩找数字的游戏,游戏规则是这样的,桌子上有n个的卡片，每一张卡片上都有一个数字( 划重点，这里没有说明每个数字必须独一无二),心美从中选择三次(可以重复选择同一张卡片),然后得到一个数为三张卡片上数字之和,如果卡片上的数字之和恰好为k,那么心美获胜,否则齐神获胜。如果心美获胜了，齐神只能乖乖的听从心美的要求说出"哦呼"了。心美从桌上随机选了三张牌（每一张卡片被心美照顾的概率相同）。燃堂想要知道齐木说出哦呼的概率有多大，因为如果齐神说了"哦呼"，那么可能今天就不能和哥们一起吃拉面了。

输入描述:

对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k。第二行输入n个整数(c1 c2...cn),(1<=ci<=2e5),表示每一张卡片上的数字。

输出描述:

输出一个形为a/b的最简分数,表示齐神说出"哦呼"的几率的概率(如果概率为0,输出0/1)。
示例1

输入

5 9
1 2 3 4 5

输出

19/125
思路：注意数据范围，上一题是3000而该题是100，所以在这道题上可以使用不优化的暴力，然后GCD化简即可。
代码如下： 
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{int n,m;int ans=0,cnt=0;cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<n;k++){if(a[i]+a[j]+a[k]==m) ans++;cnt++;}}}int x=__gcd(ans,cnt);printf("%d/%d",ans/x,cnt/x);return 0;
}

C.小X的多边形
题解： blog.csdn.net/pleasantly1/article/details/80549143
E.愤怒的巨巨

题目描述

在511没人敢惹盼成巨巨，因为盼成巨巨是我们511的学神！
周末，巨巨让乙超大佬去买一根香蕉，可你是知道的，买来的香蕉很可能是坏的，经过乙超大佬的长期调研，源源家香蕉中次品率为p，因为乙超超BYQ(too you qian)，如果买到坏香蕉，他会认栽，但他害怕巨巨愤怒，他会继续买下去，直到买到好香蕉为止！
他想知道他必须买香蕉的个数的期望值，如果注定他买不到好香蕉请输出 ”Sorrry,JuJu!”

输入描述:

输入实数p (0≤p≤1且保证p的小数位不超过6位)

输出描述:

输出一行：
如果买不到好香蕉，输出”Sorrry,JuJu!”(忽略双引号)
否则输出期望值的最简分数形式：c/d.
示例1

输入

0.5

输出

2/1
示例2

输入

1.00

输出

Sorrry,JuJu!
思路：gcd问题，需要注意数据范围，既然已经限制了数据范围，那就直接操作就好了。
代码如下： 
#include<map>
#include<stack>
#include<math.h>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
using namespace std;
typedef long long ll;
const int MAX_N=100000+50;
const int INF=0x3f3f3f3f;
int gcd(int a,int b)
{return b == 0?a:gcd(b,a%b);
}
int main()
{ios::sync_with_stdio(false);double p;cin>>p;if(p == 1.00) cout<<"Sorrry,JuJu!"<<endl;else{if(p == 0.00) cout<<"1/1"<<endl;else{int n = 1000000,ans=n*p;ans = n-ans;int t = gcd(n,ans);cout<<n/t<<"/"<<ans/t<<endl;    }     }return 0;
}


F.小名的回答

题目描述

总算到暑假了，小姐姐是非常的闲，所以想去找梅溪湖的小名玩，可是她从没去过梅溪湖，所以只能凭小名告诉她的地方走，每次只能向上下左右四个方向走1步。小姐姐的坐标为(0,0)，小名在(a,b)，小姐姐有点近视，小名也有点近视。所以到了(a,b)也不一定能和小名会面，不过还好，小姐姐最后找到了小名。小姐姐想要小名知道自己来一趟是多么不容易，所以在聊天的过程中小姐姐说自己为了到这里走了n步。小名，你觉得她说的可能是真话么。有可能就输出YES,否则输出NO(如果用random的话,小姐姐觉得你好像不在意她，明年暑假就不来了)

输入描述:

a,b,n(-1000<=a,b<=1000,a*b>0,1<=n<=2000)

输出描述:

"YES" or "NO"
示例1

输入

2 2 4

输出

YES
示例2

输入

1 9 2

输出

NO

思路：这题需要判断超出部分是否为偶数，因为偶数才能返回奇数是不可能返回的。

代码如下： 

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{long long int a,b,n;scanf("%lld%lld%lld",&a,&b,&n);a=abs(0-a);b=abs(0-b);if(n>=(a+b)&&(n-a-b)%2==0){printf("YES");}else if(n>(a+b)&&(n-a-b)%2!=0){printf("NO");}else if(n<(a+b)){printf("NO");}return 0;
}

G.第七道题

题目描述

为了确保学校新生赛的顺利举办，小X和小Y找到了相卜命妹子，请求她使用水晶球占卜一下新生赛的情况。从水晶球的预测来看，好一部分学弟学妹们会飞速解决了前六道题后，卡在了第七道题上面，为了使得学弟学妹们能够愉快的进行剩余的四个小时五十九分钟的编程而不过于无聊，于是小X灵机一动，追加了一个题目，好啦，以上就是题目背景。

题目是这样的，一张正方形卡片，上面有着9 x 9的格子，每个格子里都有一个符号。

现在我们定义7种操作:
1.将卡片顺时针旋转90°
2.将卡片顺时针旋转180°
3.将卡片顺时针旋转270°
4.将卡片沿着(5,1)->(5,9)这根轴向下翻转180°
5.将卡片沿着(1,5)->(9,5)这根轴向右翻转180°
6.将卡片沿着(1,1)->(9,9)这根对角线翻转180°
7.将卡片沿着(1,9)->(9,1)这根对角线翻转180°

卡片上有'M','W','3','E','|','-','.'一共七种符号
每次卡片通过一个操作的时候，不仅仅每个卡片格子的位置要变，对应方格上面的图形由于视角的变换也发生了相应的改变。

现在我们定义符号对应每一种操作之后的符号变换：

 (2，3操作对应的转换同多次1操作~~)

输入描述:

首先输入一个9 x 9的字母矩阵，表示刚开始卡片的形状，然后第二行输入一个字符串(只包含1-7的数字，每个数字的大小对应的相应操作)，代表一系列的操作(表示操作的字符串的长度|s|,1<=|s|<=100)。

输出描述:

输出一个9 x 9的字母矩阵,表示所有操作执行完后卡片的形状。
示例1

输入

MMMMMMMMM
WWWWWWWWW
|||||||||
---------
.........
.........
EEEEEEEEE
333333333
---------
1234567

输出

---------
EEEEEEEEE
333333333
.........
.........
---------
|||||||||
MMMMMMMMM
WWWWWWWWW
思路：赤裸裸的模拟题。
代码如下： 

#include<bits/stdc++.h>
using namespace std;
char cg[8][200];
char temp[]="MW3E|-.";
char cg2[5][10]={"3EWM-|.","WM3E|-.","MWE3|-.","E3WM-|.","3EMW-|."
};
char mp[12][12];
void init()
{for(int i=0;i<7;i++) cg[1][temp[i]]=cg2[0][i];for(int j=4;j<=7;j++){for(int i=0;i<7;i++) cg[j][temp[i]]=cg2[j-3][i];}
}
void change(int op)
{for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)mp[i][j]=cg[op][mp[i][j]];}
}
void op1()
{char t[10][10];for(int i=1;i<=9;i++){for(int j=1;j<=9;j++){t[i][j]=mp[9-j+1][i];}}for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)mp[i][j]=t[i][j];}change(1);
}
void op4()
{for(int i=1;i<=4;i++){for(int j=1;j<=9;j++)swap(mp[i][j],mp[9-i+1][j]);}change(4);
}
void op5()
{for(int i=1;i<=4;i++){for(int j=1;j<=9;j++)swap(mp[j][i],mp[j][9-i+1]);}change(5);
}
void op6()
{for(int i=1;i<=9;i++){for(int j=i;j<=9;j++)swap(mp[i][j],mp[j][i]);}change(6);
}
void op7()
{for(int i=1;i<=9;i++){for(int j=1;j<9-i+1;j++)swap(mp[i][j],mp[9-j+1][9-i+1]);}change(7);
}
int main()
{init();char op[105];for(int i=1;i<=9;i++) cin>>mp[i]+1;cin>>op;for(int i=0;op[i];i++){if(op[i]=='1') op1();else if(op[i]=='2') op1(),op1();else if(op[i]=='3') op1(),op1(),op1();else if(op[i]=='4') op4();else if(op[i]=='5') op5();else if(op[i]=='6') op6();else op7();}for(int i=1;i<=9;i++) cout<<mp[i]+1<<endl;return 0;
}

L.小小粉刷匠

题目描述

"lalala,我是一个快乐的粉刷匠",小名一边快活地唱着歌,一边开心地刷着墙",兴致突然被打断,"小名,你今天如果刷不完这一栋楼的墙，那么你就等着被炒鱿鱼吧",老板声嘶力竭的吼着。苦恼的小名因为不想被炒鱿鱼,所以希望尽量快地刷完墙,由于他本人的数学基础很差,他现在请你来帮助他计算最少完成每一堵墙需要刷多少次。每一面墙有n个段,对于每个段指定一个目标颜色ci。刚开始的时候所有的墙壁为白色,我们现在有一个刷子,刷子长度为k,刷子每次可以选择一种颜色,然后选择段数为(1～k)连续的墙段刷成选择的一种颜色。我们现在想要知道，为了把墙变成目标颜色，最少刷多少次(保证指定的目标颜色一定不为白色)。

输入描述:

对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,1<=k<=50,k<n),表示墙的长度为n,刷子的长度为k。第二行输入n个整数(c1c2...cn),(1<=ci<=256),表示对于墙的每一段指定的颜色。

输出描述:

输出一个数,表示小名最少刷多少次。
示例1

输入

3 3
1 2 1

输出

2
示例2

输入

5 4
5 4 3 3 4

输出

3
思路：经典的区间dp问题。增加了刷子的长度限制。
代码如下： 
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#define llt long long
using namespace std;
const int Size = 1100;
int F[Size][Size];//记录墙的区间为[i,j]需要粉刷的最小次数
int c[Size];
int main(){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;++i)scanf("%d",&c[i]);for(int i=1;i<=n;++i){F[i][i]=1;F[i][i-1]=0;}for(int l=2;l<=n;++l){for(int i=1;i+l-1<=n;++i){int last = i+l-1;F[i][last] = 1+F[i+1][last];for(int j=i+1;j-i<k&&j<=last;++j)if(c[j]==c[i]) F[i][last]=min(F[i][last],F[i][j-1]+F[j+1][last]);}}cout<<F[1][n]<<endl;
}




 

 
 

 

 

 

 

 

 


                                    

                                        这篇关于湖南师范大学2018年大学生程序设计竞赛新生赛（部分题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
                                    

                                    

                                

                            

                            

                        

                    

                    

                        

                            

                            http://www.chinasem.cn/article/369450。
                            
                        

                    

                    
                    

                        
                            
                        
                    

                

                

                    相关文章
                

                    

                        

                            

                                

                                    
                                        BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin
                                    
                                

                            

                            

                                

                                    BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin
                                

                                

                                    目录    [web][极客大挑战 2019]Http 考点：Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点：弱密码字典爆破 四种方法：     [web][极客大挑战 2019]Http 考点：Referer协议、UA协议、X-Forwarded-For协议 访问环境  老规矩，我们先查看源代码
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111
                                    
                                

                            

                            

                                

                                    poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111
                                

                                

                                    poj 2976：  题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。   解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。   代码：  #include <iostream>#include <cstdio>#incl
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C++ | Leetcode C++题解之第393题UTF-8编码验证
                                    
                                

                            

                            

                                

                                    C++ | Leetcode C++题解之第393题UTF-8编码验证
                                

                                

                                    题目：  题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C语言 | Leetcode C语言题解之第393题UTF-8编码验证
                                    
                                

                            

                            

                                

                                    C语言 | Leetcode C语言题解之第393题UTF-8编码验证
                                

                                

                                    题目：  题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟
                                    
                                

                            

                            

                                

                                    每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟
                                

                                

                                    每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。    四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C - Word Ladder题解
                                    
                                

                            

                            

                                

                                    C - Word Ladder题解
                                

                                

                                    C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。   这样
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel
                                    
                                

                            

                            

                                

                                    笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel
                                

                                

                                    kernel起始与ENTRY(stext)，和uboot一样，都是从汇编阶段开始的，因为对于kernel而言，还没进行栈的维护，所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用，前面关于uboot的文章中有提到过（eg:zImage）。uboot启动是无条件的，只要代码的位置对，上电就工作，kern
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C语言程序设计(数据类型、运算符与表达式)
                                    
                                

                            

                            

                                

                                    C语言程序设计(数据类型、运算符与表达式)
                                

                                

                                    一、C的数据类型 C语言提供的数据类型：  二、常量和变量 2.1常量和符号常量 在程序运行过程中，其值不能被改变的量称为常量。 常量区分为不同的类型：   程序中用＃define（预处理器指令）命令行定义变量将代表常量，用一个标识符代表一个常量，称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元，用来存放数据，在程序运行期间，这些值是可以 改变的。 变
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        【秋招笔试】9.07米哈游秋招改编题-三语言题解
                                    
                                

                            

                            

                                

                                    【秋招笔试】9.07米哈游秋招改编题-三语言题解
                                

                                

                                    🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸  ✨ 笔试合集传送们 -> 🧷春秋招笔试合集  🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C语言程序设计(选择结构程序设计)
                                    
                                

                            

                            

                                

                                    C语言程序设计(选择结构程序设计)
                                

                                

                                    一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①＜（小于） ②＜＝（小于或等于） ③＞（大于） ④＞＝（大于或等于 ） ⑤＝＝（等于） ⑥！＝（不等于） 说明： 前4个优先级相同，后2个优先级相同，关系运算符的优先级低于算术运算符，关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式（可以是算术表达式或关系表达式，逻辑表达式，赋值表达式，字符
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2