3月11日练习赛题解
![5]S3%XT@{1`$ED)3321E2[V](http://acm.pdsu.edu.cn/wordpress/wp-content/uploads/2017/03/5S3XT@1ED3321E2V.png)
周日下午比赛的榜单
周三晚上8点的榜单
题解
- 题目描述
- 题目链接
输入一个10进制数，将这个数转化为R进制输出。
- 考核知识点
简单的数学题，对进制运算的熟练掌握
- 常见误区
对进制转化运算的理解，字符数字之间的简单转换
- 解题思路
进制运算与2进制的转换时一样的，进制数大于10的时候会输出字母A-F，此时需要判断并且输出对应的字母，此时需要数字与字母之间的转换，最后再把转换过的数字和字符输出。
- 参考答案（附关键注释）
-
123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int main(){int n,m,j,i,x;int a[100];while(scanf("%d%d",&n,&m)!=EOF){x=n; //后续判断是否为负数，是否要加付好n=fabs(n); //题目中有可能输入的是负数，所以先按正数来算memset(a,0,sizeof(a));j=1; //j存的是位数+1while(n){a[j]=n%m;n=n/m;j++; //进制转换，去余相除循环。}if(x<0)printf("-"); //如果原数是负数，那么输出的时候要在最前面加一个负号for(i=j-1;i>=1;i--) //存的时候是从个位数开始存，输出的时候则要从最高位开始输出{if(a[i]>=10){ //A的阿斯科码是65 加55也行printf("%c",a[i]-10+'A'); //如果这个数大于等于10，那么要将这个数字转化为对应的字母}elseprintf("%d",a[i]); //如果是数字则原样输出}printf("\n");}return 0;}
- 整理者
学号姓名 ：151210104 郭旭东
院系 ：计算机学院（软件学院）
专业班级： 15计科1班
- 题目描述
- 题目链接
给2个分数，求他们的和，并要求和为最简形式。给你2个分数，求他们的和，并要求和为最简形式。
- 考核知识点
求最大公约数，且注意不能超时。
- 常见误区
利用普通的方法求最大公约数，导致超时。
- 解题思路
首先算出分子分母，再对分子分母进行约分。
- 参考答案（附关键注释）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<iostream> #include<stdio.h> using namespace std; int gongyue(int a,int b) { return (b==0)?a:gongyue(b,a%b);//函数递归求出两个数的最大公约数 } int main() { int T; scanf("%d",&T); int a,b,c,d; int sum1,sum2; while(T--) { scanf("%d%d%d%d",&a,&b,&c,&d); sum1=a*d+b*c;//分子 sum2=b*d;//分母 int c=gongyue(sum1,sum2); sum1/=c; sum2/=c; printf("%d %d\n",sum1,sum2); } return 0; } |
- 整理者
学号姓名 ：151060145 陈杨
院系 ：计算机学院（软件学院）
专业班级： 15计科2班
- 题目描述
- 题目链接、
8球是一种台球竞赛的规则。台面上有7个红球、7个黄球以及一个黑球，当然还有一个白球。对于本题，我们使用如下的简化规则：红、黄两名选手轮流用白球击打各自颜色的球，如果将该颜色的7个球全部打进，则这名选手可以打黑球，如果打进则算他胜。如果在打进自己颜色的所有球之前就把黑球打进，则算输。如果选手不慎打进了对手的球，入球依然有效。
现在给出打进的球（白球除外）的顺序，以及黑球由哪方打进，你的任务是判定哪方是胜者。
假设不会有一杆同时打进一颗黑球和其他彩球。
- 考核知识点
简单的字符串处理，可用到map。
- 常见误区
球的数量是固定的红球七个，黄球七个。
- 解题思路
统计R Y B L字符的数量，分四种情况，1.红球进七个并且红选手打进黑球，红方胜；2.红球进小于七个且红球选手打进黑球，黄方胜；3.黄球进七个并且黄选手打进黑球，黄方胜；4.黄球进小于七个且黄球选手打进黑球，红方胜。
- 参考答案（附关键注释）
-
123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <string>#include <sstream>#include <cstdio>#include <stack>#include <map>using namespace std;int main(){int n;while(cin>>n,n){string a;cin>>a;map<char,int>M;for(int i=0;i<a.size();i++)M[a[i]]++;//将当前数组中的所有的字母出现的次数保存if(M['R']==7&&M['B']==1)//只有当红球进了7个并且又进了黑球，红方才胜cout<<"Red"<<endl;if(M['Y']==7&&M['L']==1)// 只有当黄球进了7个并且又进了黑球，黄方才胜cout<<"Yellow"<<endl;if(M['R']<7){if(M['B']==1)//在没有进7个红球的情况下打进去黑球，红方输cout<<"Yellow"<<endl;}if(M['Y']<7){if(M['L']==1) //在没有进7个黄球的情况下打进去黑球，黄方输cout<<"Red"<<endl;}}return 0;}
- 整理者
学号姓名 ：151210118 黄峥
院系 ：计算机学院（软件学院）
专业班级： 15计科1班
- 题目描述
- 题目链接
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.（农民约翰被告知逃亡的牛的位置并立即想抓住她。他从一个点开始,N(0≤N≤100000)在数轴上,牛点K(0≤K≤100000)在同一数轴。农民约翰有两种运输方式:步行和传送。）
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
（行走:FJ可以从任何点X点X - 1或+ 1在一分钟）
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
（传送:FJ可以从任何点X点2×X在一分钟。）
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?。（如果牛不知道有人要追它,不动,为农民约翰检索需要多长时间吗?）
- 考核知识点
简单的广搜变形
- 常见误区
标记数组空间开的不够
- 解题思路
利用队列先进先出的特点，在基础的广搜模板上，把搜索的四个方向改为农民所能追牛的三种方式。即，从农民的起始位置开始将其入队，再将农民所能到达的位置全部入队，并做标记；边入边处，每出一个元素就先判断当前元素是不是牛的位置，如果是，就输出此时的步数。
- 参考答案（附关键注释）
-
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <queue>using namespace std;struct Node{int x,s;};int n,k;int vis[200005];//用来标记是否走过void bfs(int xx,int ss){ vis[xx]=1;queue<Node> Q;Node p,q;//p表示当前节点，q表示下一个节点q.x=xx;q.s=ss;Q.push(q);while(!Q.empty()){p=Q.front();Q.pop();if(p.x==k)//如果当前位置为牛的位置，输出走的步数，函数结束{ cout<<p.s<<endl;return; }q.x=p.x+1;//向前走一步if(q.x>=0&&q.x<=200000&&vis[q.x]==0)//判断这个位置有没有走过，如果没有，标记当前位置并入队，步数加一{vis[q.x]=1;q.s=p.s+1;Q.push(q); }q.x=p.x-1;//后退一步走if(q.x>=0&&q.x<=200000&&vis[q.x]==0) //判断这个位置有没有走过，如果没有，标记当前位置并入队，步数加一{vis[q.x]=1;q.s=p.s+1;Q.push(q); }q.x=p.x*2;//传送到当前位置的2倍if(q.x>=0&&q.x<=200000&&vis[q.x]==0) //判断这个位置有没有走过，如果没有，标记当前位置并入队，步数加一{vis[q.x]=1;q.s=p.s+1;Q.push(q); }}}int main(){while(cin>>n>>k){memset(vis,0,sizeof(vis));bfs(n,0);}return 0;}
- 整理者
学号姓名 ：151210220 胡姣
院系 ：计算机学院（软件学院）
专业班级： 15计科2班
- 题目描述
- 题目链接
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘 小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n), 现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间 都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
输入
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
输出
对于每个输入数据输出路径数，具体格式看Sample。
样例输入
1
3
12
-1
样例输出
1 1 2
2 3 10
3 12 416024
- 考核知识点
找规律
- 常见误区
数值过大，应使用long long int；
- 解题思路
要从（0，0）走最短路径到（n，n）只能从左边或者上边即从（n-1,n）或(n,n-1)点到达（n,n）否则 一定不是最短路径，所以到达（n,n）的路径条数就是到达（n-1，n）与到达（n，n-1）路径数之和;
同时，要求不过对角线，也就是说要么只能从上三角走，要么只能从下三角走，例如从(0,0)->(2,2);
(0,0)->(0,1)->(1,1)->(1,2)->(2,2)这条路径就是错误的；同时，上三角和下三角对称，应此只要求 出上三角的所有路线再乘上2就是所有的路径数。
核心代码
|
1 2 3 4 5 6 7 8 9 |
for(i=1;i<36;i++) { for(j=0;j<36;j++) { if(j>=i) a[i][j]=a[i-1][j]+a[i][j-1];//a[i][j]表示从（0，0）到（i，j）的路径数 } } |
- 参考答案（附关键注释）
-
12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<stdio.h>#include<string>#include<cstring>#include<math.h>using namespace std;int main(){long long int a[39][39]={0};//a[i][j]表示从（0，0）到（i，j）的路径数int i,j;a[0][1]=1;a[1][1]=1;//最开始的赋值for(i=0;i<36;i++){a[0][i]=1;//在最短路径时到达的棋盘的上边缘永远只有一条路径}for(i=1;i<36;i++){for(j=0;j<36;j++){if(j>=i)//不跨过对角线的约束条件a[i][j]=a[i-1][j]+a[i][j-1];}}int t=1;while(cin>>i){if(i==-1)break;printf("%d %d ",t,i);printf("%lld\n",a[i][i]*2);t++;}return 0;}
- 整理者
学号姓名 ：151210243 徐成东
院系 ：计算机学院（软件学院）
专业班级： 15计科2班
- 题目描述
Problem Description
Lotus has n kinds of characters,each kind of characters has a value and a amount.She wants to construct a string using some of these characters.Define the value of a string is:its first character's value*1+its second character's value *2+...She wants to calculate the maximum value of string she can construct.
Since it's valid to construct an empty string,the answer is always ≥0。
Input
First line is T(0≤T≤1000) denoting the number of test cases.
For each test case,first line is an integer n(1≤n≤26),followed by n lines each containing 2 integers vali,cnti(|vali|,cnti≤100),denoting the value and the amount of the ith character.
Output
For each test case.output one line containing a single integer,denoting the answer.
Sample Input
2
2
5 1
6 2
3
-5 3
2 1
1 1
Sample Output
35
5
- 考核知识点
考察思维能力
- 常见误区
很容易把负数舍去，但是这题有时候反而要用到负数，以保证所求的价值是最大的。
- 解题思路
根据排序不等式，显然应该把字母从小往大放。 一种错误的做法是把正权值的字母取出来从前往后放。错误是因为负权的也可能出现在答案中：放在最前面来使后面每个字母的贡献都增加。 正确的做法是把字母从大往小从后往前放，如果加入该字母后答案变劣就停下来。
这有两组特殊的数据：
输入：3
-1 3
2 1
1 1
输出：8【最优串为：-1， -1， -1， 1， 2】
输入：2
-1 5
4 2
输出：37【最优串为：-1， -1， -1， -1， -1， 4， 4】
- 参考答案（附关键注释）
-
1234567891011121314151617181920212223242526272829#include <iostream>#include <algorithm>using namespace std;int a[10000];int main(){int t;cin >> t;while(t--){int n;cin >> n;int val, cnt, k = 0;for(int i = 1; i <= n; i++) ///把字母的价值都存在数组里{ cin >> val >> cnt;while(cnt--)a[k++] = val;}sort(a, a+k);int sum = 0, ans = 0;///把数组排序后，从后往前 从大到小往前加///也就是把价值最高的放在位置最大的地方 这样一直往前加 加到不能加 即是最大的值for(int i = k - 1; i >= 0; i--){ ans+=a[i];if(ans < 0)break;sum+=ans; ///在这里我使用的累加 每往前多加一个数，选定的数就多加一次}cout << sum << endl; }return 0;}
- 整理者
学号姓名 ：141210133 胡晓康
院系 ：计算机学院（软件学院）
专业班级： 14计科1班
- 题目描述
- 题目链接
In the new year party, everybody will get a "special present".Now it's your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present's card number will be the one that different from all the others.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.
The input file will consist of several cases. Each case will be presented by an integer n (1<=n<=200, and n is odd) at first. Following that, n positive integers will be given in a line. These numbers indicate the card numbers of the presents.n = 0 ends the input.
For each case, output an integer in a line, which is the card number of your present.
题意就是让你从一堆数字里找出只出现一次的数字（这个数字是唯一的）
- 考核知识点
简单题
- 常见误区
有多种解题方法。数据并不是很大，不过如果做题方法不对还是会runtime error.
- 解题思路
我的思路就是先把所有的数字用sort排序排一下顺序，然后再用一个一维数组遍历一下，找到那个既不与前面数相同，又不与后面数相同的数就是我们要找的那个特殊数字。有两个特别的数就是第一个数（没有前一个数）和最后一个数（没有后一个数）
- 参考答案（附关键注释）
-
1234567891011121314151617181920212223242526272829#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;int main(){int n;int a[205];while(cin>>n,n!=0){int i;for(i=0;i<n;i++)cin>>a[i];sort(a,a+n);if(a[0]!=a[1])//第一个数单独判断，因为没有前一个数cout<<a[0]<<endl;for(i=1;i<n-1;i++){if(a[i]!=a[i-1]&&a[i]!=a[i+1])cout<<a[i]<<endl;}if(a[n-1]!=a[n-2])//最后一个数单独判断，因为没有后一个数{cout<<a[n-1]<<endl;}}return 0;}
- 整理者
学号姓名 ：151210242 陶林娟
院系 ：计算机学院（软件学院）
专业班级： 15计科2班
- 题目描述
- 题目链接
输入一个英文句子，将每个单词的第一个字母改成大写字母。
- 考核知识点
大小写字符的互换。
- 常见误区
（1）输入的英语句子中含有空格，要用gets()输入。
（2）没有将第一个字符单独考虑。
- 解题思路
首先题目给的一行英语句子，句子中含有空格，所以选择gets()输入。
其次分两种情况考虑：
（1）英语句子开头，i==0时，a[0]=a[0]-32;(英文在ASC码中，小写字母是9开始，大写字符是65开始）
（2）空格后一个都装换成对应的大写字符
最后，puts()输出。
- 参考答案（附关键注释）
-
12345678910111213141516171819#include<iostream>#include<string.h>#include<math.h>#include<sstream>#include<algorithm>#include<math.h>#include<string.h>using namespace std;int main(){char a[104];while(gets(a)){for(int i=0;i<strlen(a);i++){ if(i==0)a[i]-=32;if(a[i]==' ')a[i+1]-=32; }puts(a); }}
- 整理者
学号姓名 ：151210132 许娜
院系 ：计算机学院（软件学院）
专业班级： 15计科1班
发表评论