杭电ACM基础题（2075、2076、2078、2081、2083、2088、2090、2092、2093、2095）

2075、A能否被B整除

正整数A是否能被正整数B整除，不知道为什么xhd会研究这个问题，来帮帮他吧。
Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有两个正整数A和B(A,B<10^9)。
Output
对于每组输入数据，输出"YES"表示可以被整除，"NO"表示不能被整除。
Sample Input

2
4 2
5 3

Sample Output

YES
NO

Code:

//研究正整数A能否被正整数B整除
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int a,b;cin>>a>>b;if(a/b==double(a)/double(b)){
    cout<<"YES"<<endl;}else{
    cout<<"NO"<<endl;}}return 0;
} 

2076、时针和分针之间夹角有多大

时间过的好快，一个学期就这么的过去了，xhd在傻傻的看着表，出于对数据的渴望，突然他想知道这个表的时针和分针的夹角是多少。现在xhd知道的只有时间，请你帮他算出这个夹角。

注：夹角的范围[0，180]，时针和分针的转动是连续而不是离散的。
Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有三个整数h(0 <= h < 24)，m(0 <= m < 60)，s(0 <= s < 60)分别表示时、分、秒。
Output
对于每组输入数据，输出夹角的大小的整数部分。
Sample Input

2
8 3 17
5 13 30

Sample Output

138
75

Code

/* 给出时、分、秒的数值，计算时针和分针的夹角 思路：时针转过的角度与分针转过的角度的差值 1、以12:00:00的位置为参照，时针每经过一个小时转动的角度为30度，分针每经过1分钟转动的角度为6度秒针每经过1秒钟转动的角度为6度 2、秒针转动一周，分针转动6度，即每秒对分针的影响为0.1度 3、分针转动一周，时针转动30度， 即每分钟对时针的影响为0.5度，秒针转动一周，时针转动0.5度，即每秒钟对时针的影响约为1/120度 注意：如果绝对值大于180度，则用360度减去该值 */
#include<iostream>
#include<cmath>
using namespace std; 
int main(){
    int t;cin>>t;while(t--){
    int t,m,s;cin>>t>>m>>s;//时分秒if(t>12){
    t=t-12;} //每秒钟对分针的影响为0.1度//每分钟对时针的影响为0.5度，每秒钟对时针的影响为1/120度double fenzhen=m*6+s*0.1;//分针转过的角度 double shizhen=t*30+m*0.5+s*(1.0/120);//时针转过的角度 double jiaodu=abs(shizhen-fenzhen);if(jiaodu<=180){
    cout<<(int)(jiaodu)<<endl;}else{
    cout<<(int)(360-jiaodu)<<endl;}}return 0;
}

2078、复习效率的最大值

为了能过个好年，xhd开始复习了，于是每天晚上背着书往教室跑。xhd复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为100和这门课的难度差的平方。xhd这学期选了n门课，但是一晚上他最多只能复习m门课，请问他一晚上复习的最高效率值是多少？
Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，m(1 <= m <= n)。
接着有n行，每行有一个正整数a(1 <= a <= 100)，表示这门课的难度值。
Output
对于每组输入数据，输出一个整数，表示最高效率值。
Sample Input

2
2 2
52
25
12 5
89
64
6
43
56
72
92
23
20
22
37
31

Sample Output

5625
8836 

Code:

//求一晚上该同学复习效率的最大值
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n,m,diff[40];cin>>n>>m;for(int i=0;i<n;i++){
    cin>>diff[i];}sort(diff,diff+n);cout<<(100-diff[0])*(100-diff[0])<<endl;}return 0;
} 

2081、手机短号

大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后5位，比如号码为13512345678的手机，对应的短号就是645678。
现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？
Input
输入数据的第一行是一个N(N <= 200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。
Output
输出应包括N行，每行包括一个对应的短号，输出应与输入的顺序一致。
Sample Input

2
13512345678
13787654321

Sample Output

645678
654321

Code

//思路：输入一个字符串，提取后5位的字符串与6进行拼接
#include<iostream>
#include<string>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    string phone_number;cin>>phone_number;cout<<"6"+phone_number.substr(6,5)<<endl;}return 0;
} 

2083、简易版之最短距离

寒假的时候，ACBOY要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。
比如有4个朋友，对应的X轴坐标分别为1， 2， 3， 4。当ACBOY选择坐标为2的点做为出发点时，则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4。
现在给出Ｎ个朋友的坐标，那么ACBOY应该怎么走才会花费时间最少呢？
Input
输入首先是一个正整数M，表示M个测试实例。每个实例的输入有2行，首先是一个正整数N（N <= 500)，表示有N个朋友，下一行是N个正整数，表示具体的坐标(所有数据均<=10000).
Output
对于每一个测试实例，请输出访问完所有朋友所花的最少时间，每个实例的输出占一行。
Sample Input

2
2 
2 4 
3 
2 4 6

Sample Output

2
4

Code

//思路：将点的位置从小到大排列起来，若共有偶数个点n，则选取的起点为第n/2个点
//若为奇数，则选取的起点为第n/2+1个点 
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int num[500];
int main(){
    int t;cin>>t;while(t--){
    int n;//n个朋友 cin>>n;for(int i=0;i<n;i++){
    cin>>num[i];}sort(num,num+n);int a;//起点位置下标 if(n%2==0){
    a=n/2-1; }else{
    a=n/2;}int sum=0;for(int i=0;i<n;i++){
    sum=sum+abs(num[i]-num[a]);}cout<<sum<<endl;}
} 

2088、Box of Bricks

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, I’ve built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?
Input
The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1≤n≤50 and 1≤hi≤100.

The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.

The input is terminated by a set starting with n = 0. This set should not be processed.
Output
For each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height.
Output a blank line between each set.
Sample Input

6
5 2 4 1 7 5
0

Sample Output

5

Code

//思路：计算出平均每堆需要的数量，将多于平均数量的移走
#include<iostream>
using namespace std;
int main(){
    int t,height[50];bool flag=false;while(cin>>t){
    if(t==0) return 0;if(flag==false){
    flag=true;}else{
    cout<<endl;}int sum=0;for(int i=0;i<t;i++){
    cin>>height[i];sum=sum+height[i];}int aver=sum/t,count=0;for(int i=0;i<t;i++){
    if(height[i]>aver){
    count+=height[i]-aver;}}cout<<count<<endl;}
} 

2090、算菜价

妈妈每天都要出去买菜，但是回来后，兜里的钱也懒得数一数，到底花了多少钱真是一笔糊涂帐。现在好了，作为好儿子（女儿）的你可以给她用程序算一下了
Input
输入含有一些数据组，每组数据包括菜种（字串），数量（计量单位不论，一律为double型数）和单价（double型数，表示人民币元数），因此，每组数据的菜价就是数量乘上单价啊。菜种、数量和单价之间都有空格隔开的。
Output
支付菜价的时候，由于最小支付单位是角，所以总是在支付的时候采用四舍五入的方法把分头去掉。最后，请输出一个精度为角的菜价总量。
Sample Input

青菜 1  2
罗卜 2  1.5
鸡腿 2  4.2

Sample Output

13.4

Code

//给出菜的单价以及数量，计算总共的价格
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    char vegatable[100];double num,price;double sum=0;while(cin>>vegatable>>num>>price){
    sum=sum+num*price;}//输入CTRL+Z结束输入 cout<<setiosflags(ios::fixed)<<setprecision(1)<<sum<<endl;return 0;
}

2092、整数解[转化为解方程组]

有二个整数，它们加起来等于某个整数，乘起来又等于另一个整数，它们到底是真还是假，也就是这种整数到底存不存在，实在有点吃不准，你能快速回答吗？看来只能通过编程。
例如：
x + y = 9，x * y = 15 ? 找不到这样的整数x和y
1+4=5，14=4，所以，加起来等于5，乘起来等于4的二个整数为1和4
7+(-8)=-1，7（-8）=-56，所以，加起来等于-1，乘起来等于-56的二个整数为7和-8
Input
输入数据为成对出现的整数n，m（-10000<n,m<10000），它们分别表示整数的和与积，如果两者都为0，则输入结束。
Output
只需要对于每个n和m，输出“Yes”或者“No”，明确有还是没有这种整数就行了。
Sample Input

9 15
5 4
1 -56
0 0

Sample Output

No
Yes
Yes

Code

/* 思路：将其转化为解一元二次方程组 */ 
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n,m,a;//(-10000,10000)n代表两数的和，m代表两数的乘积while(cin>>m>>n){
    if(n==0&&m==0) return 0;int delt=m*m-4*n;//一元二次方程组的判别式 if(delt<0){
    cout<<"No"<<endl; }else{
    double x=(m+sqrt(delt))/2;double y=(m-sqrt(delt))/2;if(x==floor(x)&&y==floor(y)){
    cout<<"Yes"<<endl;}else{
    cout<<"No"<<endl;}}}return 0;
} 

2093、AC排名

C++编程考试使用的实时提交系统，具有即时获得成绩排名的特点。它的功能是怎么实现的呢？
我们做好了题目的解答，提交之后，要么“AC”，要么错误，不管怎样错法，总是给你记上一笔，表明你曾经有过一次错误提交，因而当你一旦提交该题“AC”后，就要与你算一算帐了，总共该题错误提交了几回。虽然你在题数上，大步地跃上了一个台阶，但是在耗时上要摊上你共花去的时间。特别是，曾经有过的错误提交，每次都要摊上一定的单位时间分。这样一来，你在做出的题数上，可能领先别人很多，但是，在做出同样题数的人群中，你可能会在耗时上处于排名的劣势。
例如：某次考试一共8题（A，B，C，D，E，F，G，H），每个人做的题都在对应的题号下有个数量标记，负数表示该学生在该题上有过的错误提交次数，但到现在还没有AC，正数表示AC所耗的时间，如果正数a跟上一对括号，里面有个整数b，那就表示该学生提交该题AC了，耗去了时间a，同时，曾经错误提交了b次，因此对于下述输入数据：

若每次错误提交的罚分为20分，则其排名从高到低应该是这样的：
Josephus 5 376
John 4 284
Alice 4 352
Smith 3 167
Bob 2 325
Bush 0 0
Input
输入数据的第一行是考试题数n（1≤n≤12）以及单位罚分数m（10≤m≤20），每行数据描述一个学生的用户名（不多于10个字符的字串）以及对所有n道题的答题现状，其描述采用问题描述中的数量标记的格式，见上面的表格，提交次数总是小于100，AC所耗时间总是小于1000。
Output
将这些学生的考试现状，输出一个实时排名。实时排名显然先按AC题数的多少排，多的在前，再按时间分的多少排，少的在前，如果凑巧前两者都相等，则按名字的字典序排，小的在前。每个学生占一行，输出名字（10个字符宽），做出的题数（2个字符宽，右对齐）和时间分（4个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。
Sample Input

8 20
Smith	  -1	-16	8	0	0	120	39	0
John	  116	-2	11	0	0	82	55(1)	0
Josephus  72(3)	126	10	-3	0	47	21(2)	-2
Bush	  0	-1	-8	0	0	0	0	0
Alice	  -2	67(2)	13	-1	0	133	79(1)	-1
Bob	  0	0	57(5)	0	0	168	-7	0

Sample Output

Josephus    5  376
John        4  284
Alice       4  352
Smith       3  167
Bob         2  325
Bush        0    0

Code
利用一个结构体存储每个同学的名字 完成题目的数量，所耗费的时间。
对结构体数组进行排序，首先按照完成题目数，若题目数相同则按照所耗费的时间数，若两者都相同，则按名字

//思路：利用一个结构体存储每个同学的名字 完成题目的数量，所耗费的时间
//对结构体数组进行排序，首先按照完成题目数，若题目数相同则按照所耗费的时间数，若两者都相同，则按名字
#include<iostream>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iomanip>
using namespace std;struct Student{
    char name[11];int ac;//ac的题目数 int contime;//所耗费的时间 
}stu[1000]; int ac_score(string time,int m){
    string s1;//s存储ac该题的时间分 int ptr; for(int i=0;i<time.size();i++){
    if(time[i]!='('){
    s1=s1+time[i];}else{
    break;}ptr=i+1;}string s2;//在未ac之前失败的次数for(int i=ptr+1;i<time.size();i++){
    if(time[i]!=')'){
    s2=s2+time[i];}else{
    break;}}return (atoi(s1.c_str())+atoi(s2.c_str())*m);//atoi()将字符串转为整型 
}bool cmp(Student stu1,Student stu2){
    if(stu1.ac==stu2.ac){
    if(stu1.contime==stu2.contime)return strcmp(stu1.name,stu2.name)<0;elsereturn stu1.contime<stu2.contime;}else{
    return stu1.ac>stu2.ac;                             } 
}int main(){
    int n,m;//考试题数n[1,12] 被罚分数[10,20]cin>>n>>m; int i=0;while(cin>>stu[i].name){
    stu[i].ac=0;stu[i].contime=0;//输入每道题的的状态 string time;for(int j=0;j<n;j++){
    cin>>time;if(time[0]=='-'||time[0]=='0'){
    //该题未AC continue;}else if(time[time.size()-1]==')'){
    //该题在多次后AC了 stu[i].ac++;stu[i].contime+=ac_score(time,m);//所用时间 }else{
    stu[i].contime+=atoi(time.c_str());stu[i].ac++;} }i++;}sort(stu,stu+i,cmp); //对结构体数组进行排序 for(int k=0;k<i;k++){
    //若使用setiosflags(ios::left)会出现格式问题cout<<left<<setw(10)<<stu[k].name<<" "<<right<<setw(2)<<stu[k].ac<<" "<<right<<setw(4)<<stu[k].contime<<endl;}return 0;
} 

2095、find your present (2)[异或]

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, and you can assume that only one number appear odd times.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.
Input
The input file will consist of several cases.
Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.
Output
For each case, output an integer in a line, which is the card number of your present.
Sample Input

5
1 1 3 2 2
3
1 2 1
0

Sample Output

3
2

Code:
异或用法

/*方式一：在一个数组中，找出数组中数值个数为1的数输出；超时 方式二：利用异或的性质 a^a=0;0^c=c; */ 
#include<iostream>
using namespace std;
int main()
{
    int t;while (scanf("%d",&t)){
    if(t==0) return 0;int sum;scanf("%d",&sum);t--;while (t--){
    int a;scanf("%d",&a);sum^=a;//如输入1 1 3 2 2,1^1=0 0^3=3 3^2^2=3 }cout<<sum<<endl;}return 0;
}