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

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

Average

题意

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

思路

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

代码

#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;
}

#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表示三角的行数，i从0开始。
第i行输出的字符为

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

对于第一部分，n = c - ‘A’ + 1表示三角的行数，i从0开始。
第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. 输出换行

代码

#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

题意

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

思路

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

代码

#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次。
就能筛出所有的符合条件的数。

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

代码

#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位整数来防止溢出。

代码

#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个的计数器数组来统计对应的字母是否出现，遍历计数器数组计算一共出现了多少个字母。

代码

#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位整数防止溢出。

代码

#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$，那么就是符合条件的数。

$$\begin{array} \,\therefore \quad S_1(n) = \sum_{i=\frac{n}{2}}^{n-1} {n-1 \choose i} \\ \because \quad {n-1 \choose i} = {n-1 \choose n-1-i}\,,\, \sum_{i=0}^{n-1} {n-1 \choose i} = 2^{n-1} \\ \therefore \quad S_1(n) = 2^{n-2} \end{array}$$

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

$$\begin{array} \,\therefore \quad S_2(n) = \sum_{i=\frac{n-1}{2}}^{n-1} {n-1 \choose i} \\ \because \quad {n-1 \choose i} = {n-1 \choose n-1-i}\,,\, \sum_{i=0}^{n-1} {n-1 \choose i} = 2^{n-1} \\ \therefore \quad S_2(n) = 2^{n-2} + \frac{1}{2}{n-1 \choose \frac{n-1}{2}} \end{array}$$

综上

$$S(n) = \left\{ \begin{array}{ll} 1&n=1 \\ 2^{n-2}& n \equiv 0 \mod 2 \\ 2^{n-2} + \frac{1}{2}{n-1 \choose \frac{n-1}{2}} & n \equiv 1 \mod 2 \end{array} \right.$$

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

代码

#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;
}