16年第七届蓝桥杯 c/c++ b组 题解

时间：2022-09-09 23:26:22

http://blog.csdn.net/y1196645376/article/details/69718192

1. 煤球数目  答案：171700

#include <cstdio>

int N = 100, sum1 = 0;

int solve(int x) {
	int sum2 = 0;
	for(int i=1; i<=x; i++)
		sum2 += i;
	return sum2;
}

int main() {
	for(int i=1; i<=N; i++) {
		sum1 += solve(i);
	}
	printf("%d",sum1);
	return 0;
}

2. 生日蜡烛  答案：26

#include <cstdio>

bool isOk(int x){
	int sum = 0;
	for(int i=x; i<100; i++) {
		sum += i;
		if(sum == 236) return true;
	}
	return false;
}

int main() {
	for(int i=0; i<100; i++) {
		if(isOk(i)) {
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}

3. 凑算式 答案：29

#include <cstdio>
#include <cmath>

double number[10];
int sum = 0;
bool vis[10];

void DFS(int index) {
	if(index == 9) {
		if(fabs(number[0] + number[1] / number[2] + 
		(number[3] * 100 + number[4] * 10 + number[5]) / 
		(number[6] * 100 + number[7] * 10 + number[8]) - 10.0 )<= 1e-5) {
			sum++;
			return;
		} else {
			return;
		}	
		
	}
	for(int i=1; i<=9; i++) {
		if(vis[i] == false) {
			vis[i] = true;
			number[index] = (double)i;
			DFS(index+1);
			vis[i] = false;
		}
	}	
}

int main() {
	DFS(0);
	printf("%d",sum);
	return 0;
}

4. 快排

5. 抽签 答案：f(a,k+1,m-i,b);  或 f(a,k+1,m-j,b);

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[]) {
	int i,j;
	if(k==N) { 
		b[M] = 0;
		if(m==0) printf("%s\n",b);
		return;
	}
	for(i=0; i<=a[k]; i++) {
		for(j=0; j<i; j++) b[M-m+j] = k+'A';
		f(a,k+1,m-i,b);  //f(a,k+1,m-j,b);
	}
}
int main() {	
	int  a[N] = {4,2,2,1,1,3};
	char b[BUF];
	f(a,0,M,b);
	return 0;
}

6. 方格填数 答案：1580

16年第七届蓝桥杯 c/c++ b组 题解

#include <cstdio>
#include <cmath>

int sum = 0, number[10];  //
bool vis[10];

bool isOk() {
	if(	abs(number[0]-number[1]) == 1 || 
		abs(number[0]-number[3]) == 1 || 
		abs(number[0]-number[4]) == 1 || 
		abs(number[0]-number[5]) == 1
	) return false;
	if(	abs(number[1]-number[2]) == 1 || 
		abs(number[1]-number[4]) == 1 || 
		abs(number[1]-number[5]) == 1 || 
		abs(number[1]-number[6]) == 1
	) return false;
	if(	abs(number[2]-number[5]) == 1 || 
		abs(number[2]-number[6]) == 1
	) return false;
	if(	abs(number[3]-number[4]) == 1 || 
		abs(number[3]-number[7]) == 1 || 
		abs(number[3]-number[8]) == 1
	) return false;
	if(	abs(number[4]-number[5]) == 1 || 
		abs(number[4]-number[7]) == 1 || 
		abs(number[4]-number[8]) == 1 || 
		abs(number[4]-number[9]) == 1
	) return false;
	if(	abs(number[5]-number[6]) == 1 || 
		abs(number[5]-number[8]) == 1 || 
		abs(number[5]-number[9]) == 1
	) return false;
	if(	abs(number[6]-number[9]) == 1) return false;
	if(	abs(number[7]-number[8]) == 1) return false;
	if(	abs(number[8]-number[9]) == 1) return false;
	return true;
}

void DFS(int index) {
	if(index == 10) { 
		if(isOk()) sum++;
		return;
	}
	for(int i=0; i<=9; i++) {
		if(!vis[i]) {
			vis[i] = true;
			number[index] = i;
			DFS(index+1);
			vis[i] = false;
		}
	}
}
int main() {	
	DFS(0);
	printf("%d",sum);
	
	return 0;
}

7. 剪邮票 答案：116

#include <cstdio>
#include <algorithm>
using namespace std;

int sum = 0, number[20], sum2 = 0;
bool vis[20], vis2[20], flag = false;

bool isExist(int x) {
	for(int i=0; i<5; i++) {
		if(number[i] == x) return true;
	}
	return false;
}

void print() {
	for(int i=0; i<5; i++) {
		printf("%d ",number[i]);
	}
	printf("\n");
}

void isOk(int x) {
	if(!isExist(x)) return;
	if(sum2 == 5) {
		flag = true;
		return;
	}
	if(vis2[x]) return;
	sum2++;
	vis2[x] = true;
	switch(x) {
		case 1 :
			isOk(2);
			isOk(5);
			break;  //////////////
		case 2 :
			isOk(1);
			isOk(6);
			isOk(3);
			break;
		case 3 :
			isOk(2);
			isOk(4);
			isOk(7);
			break;
		case 4 :
			isOk(3);
			isOk(8);
			break;
		case 5 :
			isOk(1);
			isOk(6);
			isOk(9);
			break;
		case 6 :
			isOk(2);
			isOk(5);
			isOk(7);
			isOk(10);
			break;
		case 7 :
			isOk(3);
			isOk(6);
			isOk(8);
			isOk(11);
			break;
		case 8 :
			isOk(4);
			isOk(7);
			isOk(12);
			break;
		case 9 :
			isOk(5);
			isOk(10);
			break;
		case 10 :
			isOk(6);
			isOk(9);
			isOk(11);
			break;
		case 11 :
			isOk(7);
			isOk(10);
			isOk(12);
			break;
		case 12 :
			isOk(8);
			isOk(11);
			break;
		default:break;  
	}
	//vis2[x] = false;  ////////////
}

void DFS(int index) {
	if(index == 5) {
		flag = false;
		sum2 = 0;
		fill(vis2,vis2+20,false);
		isOk(number[0]);
		if(flag) {
			sum++;	
			print();	
		}
		return;
	}
	for(int i=1; i<=12; i++) {
		if(!vis[i] && i>number[index-1]) {
			vis[i] = true;
			number[index] = i;
			DFS(index+1);
			vis[i] = false;
		}
	}
}

int main() {
	DFS(0);
	printf("%d",sum);
	
	return 0;
}

8. 四平方和

#include <cstdio>
#include <cmath>
using namespace std;

int n, n_sqrt, number[4], flag = 0, ok[100000000];

void DFS(int index) {
	if(flag == 1) return;
	if(index == 2) {
		int x = n - number[0] * number[0] - number[1] * number[1];
		if(ok[x] == 0) return;
	}
	if(index == 3) {
		int x = n - number[0] * number[0] - number[1] * number[1] - number[2] * number[2];
		double x2 = sqrt(x);
		if(x2 == (int)x2) {
			number[3] = (int)x2;
			for(int i=0; i<4; i++) {
				printf("%d ",number[i]);
				flag = 1;				
			}
		}
		return;
	}
	for(int j=0; j<=n_sqrt; j++) {
		number[index] = j;
		DFS(index+1);
	}
}

int main() {
	scanf("%d",&n);
	n_sqrt = sqrt(n);
	for(int i=0; i<=n_sqrt; i++) {
		for(int j=0; j<=n_sqrt; j++) {
			ok[i*i + j*j] = 1; 
		}
	}
	DFS(0);

	return 0;
}

9. 交换瓶子

//最少交换 
#include <cstdio>
const int MAXN = 10010;

int N, index = 1, number[MAXN], sum = 0, pos[MAXN];

void swap(int &a, int &b) {  ////引用 
	int temp = a;
	a = b;
	b = temp;
}

int main() {
	scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		int x;
		scanf("%d",&x);
		number[i] = x;
		pos[x] = i;  ////////记录位置，避免for查找 
	}
	for(int i=index; i<=N; i++) {
		if(i != number[i]) {
			index = i + 1;
			//swap(number[index], number[findTheIndex(index)]); 此句被优化： 
			int u = number[i], v = number[pos[i]];
			swap(number[i], number[pos[i]]);
				//此处贪心： 
				//用不在原位的数的下标(即:被选中的i)寻找要交换的数(即:number[pos[i]])，
				//保证了for(int i=index; i<=N; i++)在正向遍历的过程中不回头，以减少时间复杂度 
			swap(pos[u], pos[v]);
			sum++;
		}
	}
	printf("%d",sum);
	
	return 0;
}
之前做过的PATA上的固定交换元的题的代码，同样是贪心（时间复杂度未做优化）： 
//指定1为交换元
#include <cstdio>
const int MAXN = 100010;

int N, number[MAXN], sum = 0;

int find1Index() {
	for(int i=1; i<=N; i++) {
		if(number[i] == 1) return i;
	}
}

int findTheIndex(int x) {
	for(int i=1; i<=N; i++) {
		if(number[i] == x) return i;
	}
}

int findAIndex() {
	for(int i=1; i<=N; i++) {
		if(number[i] != i) return i;
	}
	return -1;
}

void print() {
	for(int i=1; i<=N; i++) {
		printf("%d ",number[i]);
	}
	printf("\n");
}

void swap(int &a, int &b) {  //////
	int temp = a;
	a = b;
	b = temp;
	sum++; 
	print();
}

int main() {
	scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d",&number[i]);
	}
	while(1) {
		int index = find1Index();
		if(index != 1) {
			swap(number[index], number[findTheIndex(index)]);
		} else {
			int index2 = findAIndex();
			if(index2 != -1) {
				swap(number[index], number[index2]);
			} else {
				break;
			}
		}
	}
	printf("%d",sum);
	
	return 0;
}
10. 最大比例

标签：

相关文章