C语言程序设计-201602期末题解

题目 类型 难度
Average 执行
Tri-triangle 找规律 ★★★
Arithmetic Sequence 执行
Dual Prime 筛法 ★★★★
String Hash 进制转换 ★★★
Cute String 统计 ★★
Harmonic Porgression 辗转相除 ★★★
Good Number 找规律,递推 ★★★★

Average

题意

Alice和Bob各出了一部分钱,求平分分摊情况下,谁应该给谁多少钱?

思路

签到题,直接做就可以了,无论是判断奇偶分情况处理或者是直接用浮点都可以的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main(){
int T,a,b,c;
scanf("%d",&T);
while(T--){
scanf("%d %d",&a,&b);
if(a > b){
c = a - b;
printf("Bob %d",c/2);
if(c&1) printf(".5");
printf("\n");
} else if(a < b){
c = b - a;
printf("Alice %d",c/2);
if(c&1) printf(".5");
printf("\n");
} else {
puts("None");
}
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main(){
int T,a,b,c;
scanf("%d",&T);
while(T--){
scanf("%d %d",&a,&b);
c = a-b;
if(c==0) puts("None");
else if(c > 0)
printf("Bob %g\n",(double)c/2);
else
printf("Alice %g\n",(double)(-c)/2);
}
return 0;
}

Tri-triangle

题意

按要求输出对应的字符图形

思路

典型的找规律题,考察观察力和循环的使用。
常见的做法有两种,一种是传统的按行列分布的规律图形的输出,一种使用二维数组作为缓冲,输出图形。
第一种做法比较直接,第二种写起来稍微麻烦点,下面我们介绍第一种传统做法。
明显图形分成两部分,第一部分是一个三角形,第二部分是下面的两个三角形。
对于第一部分,n = c - ‘A’ + 1表示三角的行数,i0开始。
i行输出的字符为

  1. 输出n-i-1个空格
  2. 从’A’开始,输出i+1 个上升字符
  3. 输出字符-=2,输出i 个下降字符
  4. 输出换行

对于第一部分,n = c - ‘A’ + 1表示三角的行数,i0开始。
i行输出的字符为

  1. 输出n-i-1个空格
  2. 从’A’开始,输出i+1 个上升字符
  3. 输出字符-=2,输出i 个下降字符
  4. 输出2*n-2*i-1个空格
  5. 从’A’开始,输出i+1 个上升字符
  6. 输出字符-=2,输出i 个下降字符
  7. 输出换行

代码

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 <stdio.h>
int main(){
char c[4],t;
int n,i,j;
while(gets(c)){
n = c[0]-'A' + 1;
for(i=0;i<n;i++){
for(j=0;j<2*n-1-i;j++) putchar(' ');
for(t='A',j=0;j<i+1;j++) putchar(t++);
for(t-=2,j=0;j<i;j++) putchar(t--);
putchar('\n');
}
for(i=0;i<n;i++){
for(j=0;j<n-1-i;j++) putchar(' ');
for(t='A',j=0;j<i+1;j++) putchar(t++);
for(t-=2,j=0;j<i;j++) putchar(t--);
for(j=0;j<2*n-1-i*2;j++) putchar(' ');
for(t='A',j=0;j<i+1;j++) putchar(t++);
for(t-=2,j=0;j<i;j++) putchar(t--);
putchar('\n');
}
}
return 0;
}

Arithmetic Sequence

题意

验证一个序列是否是等差数列。

思路

直接做,注意等差数列的差值可以是负数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main(){
int T,n,a,d,b,t,flag;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
flag = 1;
scanf("%d %d",&a,&b);
d = b - a;
b += d;
n -= 2;
while(n--){
scanf("%d",&t);
if(b!=t) flag = 0;
b+=d;
}
puts(flag?"Yes":"No");
}
}

Dual Prime

题意

求区间内,等于两个不同素数乘积的合数的个数。

思路

类似于素数筛法。我们考虑素数筛法时,把原来的标记0表示素数,1表示非素数,改为被素数筛的时候,标记过多少次。
一个符合条件的合数$n$,会被标记$1$次;(自己想想为什么?)
但被标记$1$次的还有像$m = p^2q\, \mid \,p,q是素数\,,\,并且q>\sqrt{m} \; or \; q = 1$的数,所以把$p^2$的倍数再标记1次。
就能筛出所有的符合条件的数。

题目时限给的比较松,有其他枚举的做法也可以过。

代码

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
26
27
28
29
30
31
#include <stdio.h>
const int N = 1000001;
const int SQ = 1001;
int t[N]={0};
void sieve(){
int i,j,k;
for(i=2;i<SQ;i++) if(!t[i]){
k = i*i;
for(j=k;j<N;j+=i)
t[j]++;
for(j=k;j<N;j+=k)
t[j]++;
}
for(i=2;i<N;i++)
t[i] = t[i-1] + (t[i]==1);
}
int main(){
int a,b,T;
scanf("%d",&T);
sieve();
while(T--){
scanf("%d %d",&a,&b);
printf("%d\n",t[b]-t[a-1]);
}
return 0;
}

String Hash

题意

把只含小写英文字母的字符串看成首位是1的26进制数,求其对$1,000,000,007$取模的值。

思路

进制转换的裸题。注意需要使用64位整数来防止溢出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
const long long MOD = 1000000007;
long long gao(char *s){
long long ret = 1;
while(*s){
ret *= 26;
ret += *s - 'a';
ret %= MOD;
s++;
}
return ret;
}
int main(){
char s[1111];
while(gets(s)){
printf("%I64d\n",gao(s));
}
return 0;
}

Cute String

题意

统计单词数和字母出现的种类数是否超过10。

思路

一个计数器统计单词数,根据题目输入,直接统计空格和串结束符;
再用一个26个的计数器数组来统计对应的字母是否出现,遍历计数器数组计算一共出现了多少个字母。

代码

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 <stdio.h>
#include <string.h>
int main(){
char s[222],*p;
int cc[26],c,sc,i;
while(gets(s)){
memset(cc,0,sizeof(cc));
c = 0;
for(p=s;*p;p++){
if(*p>='A'&&*p<='Z') cc[*p-'A'] = 1;
else if(*p>='a'&&*p<='z') cc[*p-'a'] = 1;
else c++;
}
c++;
for(sc=0,i=0;i<26;i++) sc+=cc[i];
if(sc<=10 && c<=10)
puts("Yes");
else
puts("No");
}
return 0;
}

Harmonic Porgression

题意

求调和级数的一段,使用分数表示结果

思路

直接做即可,相当于每次都是一次分数加,注意使用64位整数防止溢出。

代码

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
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <assert.h>
typedef long long LL;
LL gcd(LL x,LL y){
return y?gcd(y,x%y):x;
}
// pa/pb += c/d
void fracAdd(LL *pa,LL *pb,LL c,LL d){
long long a,b,e;
a = *pa * d + c * *pb;
b = *pb * d;
e = gcd(a,b);
*pa = a / e;
*pb = b / e;
}
int main(){
int T;
long long i,a,b,c,d;
scanf("%d",&T);
while(T--){
scanf("%I64d %I64d",&a,&b);
c = 0;
d = 1;
for(i=a;i<=b;i++){
fracAdd(&c,&d,1,i);
}
printf("%I64d/%I64d\n",c,d);
}
return 0;
}

Good Number

题意

求$n$位无前导$0$的二进制数中,数码$1$比数码$0$多的数的个数。

思路

如果$n=1$,那么结果为$1$。
对于$n>1$,如果$n$是偶数,首位必须是$1$,那么余下的$n-1$位的中,只要存在$i \ge \frac{n}{2}$个$1$,那么就是符合条件的数。

如果$n$是奇数,首位必须是$1$,那么余下的$n-1$位的中,只要存在$i \ge \frac{n-1}{2}$个$1$,那么就是符合条件的数。

综上

所以,先利用递推求出组合数即可。注意使用64位整数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#define N 64
long long a[N][N];
void init(){
int i,j;
for(i=0;i<N;i++) a[i][0] = a[i][i] = 1;
for(i=2;i<N;i++)
for(j=1;j<i;j++)
a[i][j] = a[i-1][j-1] + a[i-1][j];
}
int main(){
int n;
init();
while(~scanf("%d",&n)){
if(n==1) puts("1");
else if(n&1) printf("%I64d\n",(1LL<<(n-2))+(a[n-1][(n-1)>>1]>>1));
else printf("%I64d\n",(1LL<<(n-2)));
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!