西安邮电大学C程序设计大赛初赛

来源:网络整理作者:网友投稿发布时间:2020-12-27 15:43

来源：http: acm xupt edu cn contest php?cid=1189问题A:CONTEST1 十进制转十六进制（BYYAN）时间限制:10Sec内存限制:256MB提交:349解决...

来源：?cid=1189

问题 A: CONTEST1.十进制转十六进制（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 349 解决: 247
[提交][状态][讨论版] 题目描述

十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。要求给出一个非负整数，将它表示成十六进制的形式。

输入

第一行输入一个非负整数a，表示要转换的数，0<=a<=2147483647。

输出

输出这个整数的16进制表示，其中A,B,C,D,E,F都是大写字母。

样例输入 30 样例输出 1E

水题直接上代码：

/************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Mail:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define INF (1ll<<60)-1 using namespace std; typedef long long ll; int main(int argc,char *argv[]) { long n; int a[1000]; int len=0; scanf("%ld",&n); while(n!=0) { a[len]=n%16; len++; n/=16; } for(int i=len-1;i>=0;i--) { if(a[i]<=9) printf("%d",a[i]); else { printf("%c",a[i]-10+(int)'A'); } } return 0; }
问题 B: CONTEST2.核桃的数量（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 283 解决: 237
[提交][状态][讨论版] 题目描述

小张是软件项目经理，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

（1）各组的核桃数量必须相同；

（2）各组内必须能平分核桃（当然是不能打碎的）

（3）尽量提供满足1,2条件的最小数量（节约闹革命嘛）

输入

输入包含三个正整数a,b,c，表示每个组正在加班的人数，用空格分开 (a,b,c均小于30)。

输出

输出一个正整数，表示每袋中核桃的数量，不要输出多余的信息。

样例输入 30 12 9 样例输出 180 三个数最小公倍数： /************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Mail:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define INF (1ll<<60)-1 using namespace std; typedef long long ll; int yueshu(int x,int y); int main(int argc,char *argv[]) { int x,y,z,n,d,m; scanf("%d %d %d",&x,&y,&z); m=x*y/yueshu(x,y); n=m*z/yueshu(z,m); printf("%d",n); return 0; } int yueshu(int x,int y) { int t,d; if(y>x) { t=x; x=y; y=t; } while(y!=0) { d=y; y=x%y; x=d; } return x; }
问题 C: CONTEST3.移动距离（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 310 解决: 105
[提交][状态][讨论版] 题目描述

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3...当排满一行时，从下一行相邻的楼往反方向排号。

例如：当小区排号宽度为6时，开始情形如下：

1 2 3 4 5 6

12 11 10 9 8 7

13 14 15 .....

问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动）

输入

输入为3个整数w m n，空格分开，都在1到10000范围内。

w为排号宽度，m,n为待计算的楼号。

输出

输出一个整数，表示m n 两楼间最短移动距离。

样例输入 6 8 2 样例输出 4

先求坐标，然后求其坐标差：

/************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; int main() { int w,n,m,x1,y1,x2,y2; scanf("%d %d %d",&w,&n,&m); if(n%w==0) { x1=n/w; if(x1%2==0) y1=1; else y1=w; } else { x1=n/w+1; if(x1%2==0) y1=w+1-n%w; else y1=n%w; } if(m%w==0) { x2=m/w; if(x2%2==0) y2=1; else y2=w; } else { x2=m/w+1; if(x2%2==0) y2=w+1-m%w; else y2=m%w; } printf("%d",abs(x1-x2)+abs(y1-y2)); return 0; }
问题 D: CONTEST4.翻硬币（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 132 解决: 81
[提交][状态][讨论版] 题目描述

小明正在玩一个“翻硬币”的游戏，桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。例如，可能情形是：**oo***oooo，如果同时翻转左边的两个硬币，则变为：oooo***oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入

两行等长的字符串，分别表示初始状态和要达到的目标状态，每行的长度<1000。

输出

一个整数，表示最小操作步数。

样例输入 ********** o****o**** 样例输出 5 利用贪心算法，消除不同： /************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; void change(int i); char str1[1005],str2[1005]; int coun=0; int main() { int len; scanf("%s",str1); scanf("%s",str2); len=strlen(str1); for(int i=0;i<len;i++) { if(str1[i]!=str2[i])//若不同，翻一次，另外改变字符数组 { change(i); coun++; } } printf("%d",coun); return 0; } void change(int i) { if(str1[i]=='*') str1[i]='o'; else str1[i]='*'; if(str1[i+1]!='') { if(str1[i+1]=='o') str1[i+1]='*'; else str1[i+1]='o'; } }
问题 E: CONTEST5.字符统计（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 136 解决: 87
[提交][状态][讨论版] 题目描述

编写程序接收从键盘输入的n个字符串（1<n<=10），然后实现下列功能：

（1）输出字符串的长度；

（2）输出字符串所包含的单词的数量；

（3）统计该字符串包含的大写字母、小写字母、数字、空格和其他字符的数量并输出。

输入

第一行为n值，以后连续n行为待统计的字符串，每行的长度<100。

每个单词之间用一个空格隔开，或者用一个标点加一个空格隔开。

输出

输出n行，每行是7个整数，依次表示：字符串长度、单词数量、大写字母数量、小写字母数量、数字数量、空格数量、其他字符数量。每个数字以空格隔开，每行最后一个数字后面没有空格。

样例输入 3 There are 166 students in the C programming contest. Congratulation, you receive nice scores in this test, please continue. I am very fond of learning advanced language program design courses. 样例输出 52 9 2 38 3 8 1 70 10 1 57 0 9 3 68 11 1 56 0 10 1 提示

简单统计

注意：单词数为空格数加一 /************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> using namespace std; int main() { char str1[20][105]; int n,sum,num,da,xiao,shu,kong,qita,i,j,k; scanf("%d ",&n); for(i=0;i<n;i++) gets(str1[i]); for(i=0;i<n;i++) { num=0; da=0; xiao=0; shu=0; kong=0; qita=0; sum=strlen(str1[i]); for(j=0;j<sum;j++) { if(str1[i][j]==' ') kong++; else if(str1[i][j]>='a'&&str1[i][j]<='z') xiao++; else if(str1[i][j]>='A'&&str1[i][j]<='Z') da++; else if(str1[i][j]>='0'&&str1[i][j]<='9') shu++; else qita++; } num=kong+1; printf("%d %d %d %d %d %d %d",sum,num,da,xiao,shu,kong,qita); if(i!=n-1) printf(" "); } return 0; }
问题 F: CONTEST6.可逆素数（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 290 解决: 111
[提交][状态][讨论版] 题目描述

若将某一素数的各位数字顺序颠倒后得到的数仍然是素数，则次素数称为可逆素数。

判断给定的n个数据是否是可逆素数。

输入

第一行为n值，第二行输入n个数字，以空格间隔。

输出

输出n行，每一行的格式为【***是可逆素数】（或者【***是素数，但不是可逆素数】，用中文逗号隔开，或者【***不是素数】）。

请严格按照格式书写，不能出现其它文字或符号。

特别说明：待判断的数据个数不超过10个。

样例输入 3 23 31 18 样例输出 23是素数，但不是可逆素数 31是可逆素数 18不是素数

数的翻转，和素数判定

/************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include<math.h> using namespace std; bool judge(int x); int main() { int n; int a[100]; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { int m=0,t,t1; t=a[i]; while(t) { m=m*10+t%10; t/=10; } if(!judge(a[i])) printf("%d不是素数",a[i]); else { if(judge(m)) printf("%d是可逆素数",a[i]); else printf("%d是素数，但不是可逆素数",a[i]); } if(i!=n) printf(" "); } return 0; } bool judge(int n) { if(n<=1) return false; int m=floor(sqrt(n)+0.5); for(int i=2;i<=m;i++) if(n%i==0) return false; return true; }
问题 G: CONTEST7.双胞胎素数（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 292 解决: 159
[提交][状态][讨论版] 题目描述

已知x,y均为正整数，且x<y,输出x到y之间(包含x,y)的所有双胞胎素数。相邻两个奇数都为素数的这样一对数叫双胞胎素数。

输入

依次输入x和y的值，以空格间隔。

输出

每对双胞胎素数用小括号括起来，中间用英文逗号间隔，两个括号之间不空格。

样例输入 2 23 样例输出 (3,5)(5,7)(11,13)(17,19) 提示

简单素数判断：

一个正整数有可能被表示为n(n>=2)个连续正整数之和。编写程序，输入任意一个正整数，找出符合这种要求的所有连续正整数序列。

例如：15=1+2+3+4+5 15=4+5+6 15=7+8。

输入

输入一个正整数n。

输出

如果可以表示成连续正整数之和，则严格按照样例输出所有表示方式，求解顺序的起始数据从小到大排列；若不能，则输出“NONE”字样的提示语句。

样例输入 15 样例输出 15=1+2+3+4+5 15=4+5+6 15=7+8 提示

先计算可能有几个数，然后判断！

/************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> using namespace std; int main(int argn, char** str) { int n; int sum; bool flag = false; scanf("%d",&n); if(n<= 2) { printf("NONE "); return 0; } for(int m = (int)sqrt(n*2); m >= 2; m--) { sum = m*(m+1)/2; if((n-sum)%m == 0) { int t=(n-sum)/m; flag = true; printf("%d=",n); for(int i = 1; i <= m; i++) { printf("%d",i+t); if(i!=m) printf("+"); } printf(" "); } } if(!flag) printf("NONE "); return 0; }
问题 C: CONTEST3.移动距离（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 310 解决: 105
[提交][状态][讨论版] 题目描述

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3...当排满一行时，从下一行相邻的楼往反方向排号。

例如：当小区排号宽度为6时，开始情形如下：

1 2 3 4 5 6

12 11 10 9 8 7

13 14 15 .....

问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动）

输入

输入为3个整数w m n，空格分开，都在1到10000范围内。

w为排号宽度，m,n为待计算的楼号。

输出

输出一个整数，表示m n 两楼间最短移动距离。

样例输入 6 8 2 样例输出 4

简单DP，根据位数和开头第一个数建立子问题空间！

/************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; #define MOD 1000000007 ll dp[105][105];//dp[i][j]代表了其有i位数，而j代表了i位数的最后面的一位 //以位数为规模，而根据条件，其大小相邻的数位置不能相邻，所以用了二维数组储存 int main() { int k,l; scanf("%d %d",&k,&l); for(int i = 0; i<k; i++) dp[1][i] = 1; for(int i = 2; i<=l; i++) //位数 for(int j = 0; j<k; j++) //i位数的最后面的一位 for(int x = 0; x<k; x++)//根据前一位求解 if(x!=j-1&&x!=j+1) { dp[i][j]+=dp[i-1][x]; //这里也可换成乘法 dp[i][j]%=MOD; } ll sum = 0; for(int i = 1; i<k; i++)//l位末尾不同的个数之和为其答案 { sum+=dp[l][i]; sum%=MOD; } printf("%lld",sum%MOD); return 0; }
具体可以参照：问题 J: CONTEST10.特殊回文数（BY YAN）时间限制: 10 Sec 内存限制: 256 MB
提交: 238 解决: 57
[提交][状态][讨论版] 题目描述

123321是一个非常特殊的数，它从左边读和从右边读是一样的。输入一个正整数n，编程求所有这样的五位和六位十进制数，满足各位数字之和等于n（1<=n<=54）。

输入

输入一个正整数n。

输出

若特殊回文数的个数<=10，则按从小到大的顺序输出满足条件的特殊回文数，每个数字占一行。

若特殊回文数的个数>10，则仅输出总个数。

样例输入 52 样例输出 899998 989989 998899 简单遍历： /************************************************************************* > File Name: UXPT.cpp > Author:chudongfang > Maie:[email protected] > Created Time: 2016年06月15日星期三 23时01分54秒 ************************************************************************/ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; int main() { int n; int count=0; int re[15]; int a[15],b[15],c[15],a1[15],b1[15],c1[15]; memset(a,0,sizeof(a)); memset(a1,0,sizeof(a1)); memset(b,0,sizeof(b)); memset(b1,0,sizeof(b1)); memset(c1,0,sizeof(c1)); memset(c,0,sizeof(c)); memset(re,0,sizeof(re)); scanf("%d",&n); if(n%2==1) { for(int mid=0;mid<=9;mid++) { for(int i=1;i<=9;i++) { if((n-mid-i*2)%2==0&&(n-mid-i*2)/2>=0&&(n-mid-i*2)/2<=9) { count++; if(count<=10) { a1[count]=i; b1[count]=(n-mid-i*2)/2; c1[count]=mid; } } } } } else { for(int i=1;i<=9;i++) { for(int j=0;j<=9;j++) { if(n/2-i-j<=9&&n/2-i-j>=0) { count++; if(count<=10) { a[count]=i; b[count]=j; c[count]=n/2-i-j; } } } } for(int mid=0;mid<=9;mid++) { for(int i=1;i<=9;i++) { if((n-mid-i*2)%2==0&&(n-mid-i*2)/2>=0&&(n-mid-i*2)/2<=9) { count++; if(count<=10) { a1[count]=i; b1[count]=(n-mid-i*2)/2; c1[count]=mid; } } } } } if(count>10) printf("%d",count); else { int len=0; for(int i=1;a1[i]!=0;i++) { re[len]=a1[i]*10000+b1[i]*1000+c1[i]*100+b1[i]*10+a1[i]; len++; } for(int i=1;a[i]!=0;i++) { re[len]=a[i]*100000+b[i]*10000+c[i]*1000+c[i]*100+b[i]*10+a[i]; len++; } sort(re,re+len-1); for(int i=0;i<len;i++) { printf("%d",re[i]); if(i!=len-1) printf(" "); } } return 0; }