杭电ACM基础题（2031、2032、2033、2034、2035、2039、2040、2042、2043、2051）

2031、进制转换

输入一个十进制数N，将它转换成R进制数输出。
Input
输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<>10）。
Output
为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考16进制（比如，10用A表示，等等）。
Sample Input

7 2
23 12
-4 3

Sample Output

111
1B
-11

Code

//将一个十进制数转化为R进制数输出
//除基取余法
#include<iostream>
using namespace std;//十进制数n转化为r进制数
char c[1000];
void ten_convert(int n,int r){
    //将余数存入c[]数组 int i=0,t;if(n<0){
    cout<<"-";n=-1*n;}while(n!=0){
    t=n%r;n=n/r;switch(t){
    case 10:c[i++]='A';break;case 11:c[i++]='B';break;case 12:c[i++]='C';break;case 13:c[i++]='D';break;case 14:c[i++]='E';break;case 15:c[i++]='F';break;default:c[i++]=t+'0'; //将数字转化为字符 break;}}for(int k=i-1;k>=0;k--){
    cout<<c[k];}cout<<endl;
} int main(){
    int n,r;//注意n可以是负数while(cin>>n>>r){
    //将十进制数n转化为r进制数//32位整数范围是：-2147483648～2147483647,当把-2147483648 转换成它的相反数 2147483648 时，已经超范围了……if(n<0){
    ten_convert(n,r);}else{
    ten_convert(n,r);}}return 0;
} 

2032、杨辉三角

还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Input
输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=30），表示将要输出的杨辉三角的层数。
Output
对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。
Sample Input

2 3

Sample Output

1
1 11
1 1
1 2 1

Code

//输出第n层的杨辉三角--找规律 
#include<iostream>
using namespace std;
int a[31][31];
int main(){
    int n;//[1,30]while(cin>>n){
    for(int i=1;i<=n;i++){
    a[i][1]=1;    a[i][i]=1;}for(int i=3;i<=n;i++){
    for(int j=2;j<i;j++){
    a[i][j]=a[i-1][j-1]+a[i-1][j];}}//输出n层的杨辉三角 for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
    if(j==1)cout<<a[i][j];elsecout<<" "<<a[i][j];} cout<<endl;}cout<<endl;}return 0;
} 

2033、时钟数的A+B

这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。
Input
输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。题目保证所有的数据合法。
Output
对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0~59），每个输出占一行，并且所有的部分都可以用32位整数表示。
Sample Input

2
1 2 3 4 5 6
34 45 56 12 23 34

Sample Output

5 7 9
47 9 30

Code:

//表示时分秒的两个数进行相加，如34(时间) 45(分钟) 56(秒) +12 23 34 
#include<iostream>
using namespace std;
int main(){
    int n;cin>>n;while(n--){
    int ah,am,as,bh,bm,bs;cin>>ah>>am>>as>>bh>>bm>>bs;int sumh=0,summ=0,sums=0;//先计算秒 sums=as+bs;if(sums>60){
    summ=summ+sums/60;//向分钟数进位 sums=sums%60;}summ=summ+am+bm;if(summ>60){
    sumh=sumh+summ/60;//进位summ=summ%60; }sumh=sumh+ah+bh;cout<<sumh<<" "<<summ<<" "<<sums<<endl; }return 0;
}

2034、{A}-{B}集合作差

今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）
Input
每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。
Output
针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.
Sample Input

3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8 
0 0

Sample Output

2 3
NULL

Code
{A}-{B}

//求两个集合的差，{A}-{B}
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,m;//[0,100]int a[100],b[100];while(cin>>n>>m){
    if(n==0&&m==0) return 0;//输入集合A的数据 for(int i=0;i<n;i++){
    cin>>a[i];}//输入集合B的数据 for(int j=0;j<m;j++){
    cin>>b[j];}//计算{A}-{B}int c[100],k=0,flag;for(int i=0;i<n;i++){
    flag=1;for(int j=0;j<m;j++){
    if(a[i]==b[j]){
    flag=0;break;}}if(flag==1){
    c[k]=a[i];k++;}}//将c[]输出if(k==0) cout<<"NULL";else{
    sort(c,c+k);for(int i=0;i<k;i++){
    cout<<c[i]<<" ";} }cout<<endl;}return 0;
} 

2035、求A^B

求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”
Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。
Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。
Sample Input

2 3
12 6
6789 10000
0 0

Sample Output

8
984
1

Code
方法一：

//输出A^B的最后三位数表示的整数
//方法一：每次求完对1000取余 
#include<iostream>
using namespace std;
int main(){
    int a,b;while(cin>>a>>b){
    if(a==0&&b==0) return 0;int result=1;for(int i=0;i<b;i++){
    result=result*a;result=result%1000;}cout<<result<<endl;} return 0;
} 

方法二：快速幂

/* 求A^B%1000 思路1：取模定理，需要循环b次 思路2：快速幂 如计算3^7,将7表示为2进制的形式进行计算 3^7=(3^4*3^2*3^1) 7的二进制表示为111 */
#include<iostream>
using namespace std;
int main(){
    int a,b;while(cin>>a>>b){
    if(a==0&&b==0) break;//a^b%1000;int res=1;while(b>0){
    if(b%2==1){
    res=res*a%1000;}a=a*a%1000;b=b/2;}cout<<res<<endl;}return 0;
} 

2039、判断所给a,b,c能否组成三角形

给定三条边，请你判断一下能不能组成一个三角形。
Input
输入数据第一行包含一个数M，接下有M行，每行一个实例，包含三个正数A,B,C。其中A,B,C <1000;
Output
对于每个测试实例，如果三条边长A,B,C能组成三角形的话，输出YES，否则NO。
Sample Input

2
1 2 3
2 2 2

Sample Output

NO
YES

Code:
三角形任意两边之和大于第三边

//给定三条边，判断其是否能组成三角形
#include<iostream>
using namespace std;
int main(){
    int n;cin>>n;while(n--){
    double a,b,c;cin>>a>>b>>c;if(a+b<=c||a+c<=b||b+c<=a){
    cout<<"NO"<<endl;}else{
    cout<<"YES"<<endl;}}return 0;
} 

2040、亲和数

古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数(即不是自身的约数)之和为：

1+2+4+5+10+11+20+22+44+55+110＝284。

而284的所有真约数为1、2、4、71、 142，加起来恰好为220。人们对这样的数感到很惊奇，并称之为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。

你的任务就编写一个程序，判断给定的两个数是否是亲和数
Input
输入数据第一行包含一个数M，接下有M行，每行一个实例,包含两个整数A,B； 其中 0 <= A,B <= 600000 ;
Output
对于每个测试实例，如果A和B是亲和数的话输出YES，否则输出NO。
Sample Input

2
220 284
100 200

Sample Output

YES
NO

Code
判断给定两个数是否为亲和数

/*判断给定的两个数是否是亲和数 真约数： 如284的真约数之和是220,220的真约数之和为284，所以这两个数互为亲和数 */ 
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int a,b;cin>>a>>b;//判断a和b是否是亲和数int sum1=0,sum2=0;for(int i=1;i<a;i++){
    if(a%i==0)sum1=sum1+i;//a的所有真约数之和 } for(int i=1;i<b;i++){
    if(b%i==0){
    sum2=sum2+i;//b的所有真约数之和 }}if(sum1==b&&sum2==a){
    cout<<"YES"<<endl;}else{
    cout<<"NO"<<endl;}}return 0;
} 

2042、经过收费站计数

某个人每经过一个站点，收走当时物品的一半后，再归还一个，等到最后只剩下了3个
编程实现：若经过n个站后，只剩下了3个物品，则原来物品有多少？
Input
输入数据第一行是一个整数N，下面由N行组成，每行包含一个整数a(0<a<=30),表示收费站的数量。
Output
对于每个测试实例，请输出最初的羊的数量,每个测试实例的输出占一行。
Sample Input

2
1
2

Sample Output

4
6

Code

/* 题目：某个人每经过一个站点，收走当时物品的一半后，再归还一个，等到最后只剩下了3个 编程实现：若经过n个站后，只剩下了3个物品，则原来物品有多少？ 分析：最后只剩下3个；经过倒数第一个站点物品有：(3-1)*2=4个；倒数第二个：(4-1)*2=6... */
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n;cin>>n;int sum=3;for(int i=n;i>=1;i--){
    sum=(sum-1)*2;}cout<<sum<<endl;}return 0;
}

2043、判断一个密码是否是安全密码

首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：

(1).密码长度大于等于8，且不要超过16。
(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。

这四个字符类别分别为：
1.大写字母：A,B,C…Z;
2.小写字母：a,b,c…z;
3.数字：0,1,2…9;
4.特殊符号：~,!,@,#,$,%,^;

给你一个密码，你的任务就是判断它是不是一个安全的密码。
Input
输入数据第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符。
Output
对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。
Sample Input

3
a1b2c3d4
Linle@ACM
^~^@^@!%

Sample Output

NO
YES
NO

Code

/* 判断一个密码是否是一个安全的密码 安全密码： (1).密码长度大于等于8，且不要超过16。(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。1.大写字母：A,B,C...Z;2.小写字母：a,b,c...z;3.数字：0,1,2...9;4.特殊符号：~,!,@,#,$,%,^; */
#include<iostream>
#include<cstring>
using namespace std;
int main(){
    int t;char password[51];cin>>t;while(t--){
    cin>>password;int len=strlen(password);if(len<8||len>16){
    cout<<"NO"<<endl;}else{
    int num1=0,num2=0,num3=0,num4=0;for(int i=0;i<len;i++){
    if(password[i]>='A'&&password[i]<='Z'){
    //密码由大写字母组成 num1++;}else if(password[i]>='a'&&password[i]<='z'){
    num2++;} else if(password[i]-'0'>=0&&password[i]-'0'<=9){
    num3++;}else if(password[i]=='~'||password[i]=='!'||password[i]=='@'||password[i]=='#'||password[i]=='$'||password[i]=='%'||password[i]=='^'){
    num4++;}}if((num1>0&&num2>0&&num3>0)||(num1>0&&num2>0&&num4>0)||(num1>0&&num3>0&&num4>0)||(num2>0&&num3>0&&num4>0)){
    cout<<"YES"<<endl;}else{
    cout<<"NO"<<endl;}}    }return 0;
} 

2051、Bitset[将十进制转化为二进制数]

Give you a number on base ten,you should output it on base two.(0 < n < 1000)
Input
For each case there is a postive number n on base ten, end of file.
Output
For each case output a number on base two.
Sample Input

1
2
3

Sample Output

1
10
11

Code

//将十进制数n转化为2进制
#include<iostream> 
using namespace std;void convert_two(int n){
    int t[100],i=0;while(n!=0){
    t[i++]=n%2;n=n/2;}for(int k=i-1;k>=0;k--){
    cout<<t[k];}cout<<endl;
}
int main(){
    int n;while(cin>>n){
    convert_two(n);}return 0;
}