蓝桥寒假训练4->2014年第五届蓝桥杯国赛_高职组

1.好好学习

汤姆跟爷爷来中国旅游。一天，他帮助中国的小朋友贴标语。他负责贴的标语是分别写在四块红纸上的四个大字：“好、好、学、习”。但是汤姆不认识汉字，他就想胡乱地贴成一行。请你替小汤姆算一下，他这样乱贴，恰好贴对的概率是多少？答案是一个分数，请表示为两个整数比值的形式。例如：1/3 或 2/15 等。
如果能够约分，请输出约分后的结果。
//法一：//排列组合公式//法二：#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int main(){	int count=0;	int a[4]={0,0,1,2};//代表好好学习	do{		count++;	}while(next_permutation(a,a+4));	cout<<count<<endl;}//注意：全排列的意思是n个不同的数//若有相同的，即存在多重集，则全排列的结果为 去重复 后的//1/12
2.正负金字塔
看下面的图形： + - + - - + - + - - + - - + -  - - - + - - - - + - - + - -   + + - - + + + - - + - - +    + - + - + + - + - - + -     - - - - + - - - + - -      + + + - - + + - - +       + + - + - + - + -        + - - - - - - -         - + + + + + +          - + + + + +           - + + + +            - + + +             - + +              - +               -它是由正号和负号组成的金字塔形状。其规律是：每个符号的左上方和右上方符号如果相同，则输出为正号，否则为负号。其第一行数据由外部输入。以下代码实现了该功能。请仔细阅读代码，并填写划线部分缺失的代码。
void f(char* x, int space, int n){				int i;				if(n<1) return;				for(i=0; i<space; i++) PRintf(" ");				for(i=0; i<n; i++) printf("%c ", x[i]);				printf("/n");								for(i=0; i<n-1; i++) x[i] = ____________________________;				f(x,space+1,n-1);								 }// 用于f的测试int test(){				char x[] = "+-+--+-+--+--+-";				//char x[] = "+-+";				f(x, 5, sizeof(x)-1);				return 0;}答案：(x[i]==x[i+1]?'+':'-')
3.神奇6位数
有一个6位的正整数，它有个很神奇的性质：
分别用2 3 4 5 6去乘它，得到的仍然是6位数，并且乘积中所包含的数字与这个6位数完全一样！只不过是它们的顺序重新排列了而已。
请计算出这个6位数。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int dight[10];int judge(int a){	int c[10];	memset(c,0,sizeof(c));	if(a>999999){		return 0;	}	while(a){		c[a%10]++;		a/=10;	}	for(int i=0;i<=9;i++){		if(dight[i]!=c[i]){			return 0;		}	}	return 1;}int main(){	int count;	//cout<<1000000/6<<endl;	for(int i=100000;i<=166667;i++){		count=0;		memset(dight,0,sizeof(dight));		int t=i;		while(t){			dight[t%10]++;			t/=10;		}		for(int j=2;j<=6;j++){			int re=i*j;			if(judge(re)){				count++;			}			else{				break;			}		}		if(count==5){			cout<<i<<endl;			break;		}	}	return 0;}//142857
4.国王的遗产
X国是个小国。国王K有6个儿子。在临终前，K国王立下遗嘱：国王的一批牛作为遗产要分给他的6个儿子。其中，大儿子分1/4，二儿子1/5，三儿子1/6，....直到小儿子分1/9。牛是活的，不能把一头牛切开分。最后还剩下11头牛，分给管家。请计算国王这批遗产中一共有多少头牛。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int main(){	for(int i=2520;i>=1;i--){		int sum=i;		for(int j=4;j<=9;j++){			sum-=i/j;		}		if(sum==11){			cout<<i<<endl;			break;		}	}	return 0;}//25205.危险系数
问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
输入格式
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数； 接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道； 最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。
输出格式
一个整数，如果询问的两点不连通则输出-1.
样例输入
7 61 32 33 43 54 55 61 6
样例输出
2
//求两点路径间的某点，去掉该点，两点间的任何路径均不连通//思路：深搜所有可能的路径，每条路径都出现的点即为所求#include <cstdio>#include <cstring>#include <iostream>using namespace std;struct node{	int to;	int next;}edge[2005];int head[1005];int book[1005];int path[2010];int times[1005];int cnt,count;int n,m,u,v;void Init(){	cnt=0;	count=0;	memset(head,0,sizeof(head));	memset(edge,0,sizeof(edge));	memset(book,0,sizeof(book));	memset(times,0,sizeof(times));}void Add(int x,int y){	cnt++;	edge[cnt].to=y;	edge[cnt].next=head[x];	head[x]=cnt;}void dfs(int x,int step){	if(x==v){		count++;		for(int i=0;i<step;i++){			times[path[i]]++;		}		return;	}	for(int i=head[x];i;i=edge[i].next){		if(!book[edge[i].to]){			book[edge[i].to]=1;			path[step]=edge[i].to;			dfs(edge[i].to,step+1);			book[edge[i].to]=0;		}	}}int main(){	int x,y,t=0;	cin>>n>>m;	for(int i=1;i<=m;i++){		cin>>x>>y;		Add(x,y);		Add(y,x);	}	cin>>u>>v;	book[u]=1;	path[0]=u;	dfs(u,1);	for(int i=1;i<n;i++){		if(times[i]==count&&i!=u&&i!=v){			t++;		}	}	if(count)		cout<<t<<endl;	else		cout<<-1<<endl;	return 0;}
6.横向打印二叉树
二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。当遇到空子树时，则把该节点放入那个位置。 比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如图1所示。 
本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。 输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。输入数据中没有重复的数字。 输出该排序二叉树的横向表示。 对应上例中的数据，应输出：
   |-1210-|   |-8-|       |   |-7       |-5-|           |-4
为了便于评卷程序比对空格的数目，请把空格用句点代替：
...|-1210-|...|-8-|.......|...|-7.......|-5-|...........|-4
例如：
用户输入：
10 5 20
则程序输出：
...|-2010-|...|-5
再例如：
用户输入：
5 10 20 8 4 7
则程序输出：
.......|-20..|-10-|..|....|-8-|..|........|-75-|..|-4
//建树，找规律#include <cstdio>#include <cstring>#include <iostream>using namespace std;struct node{	int num;	struct node *left;	struct node *right;};struct node *tree=NULL;struct node *Insert(struct node *tree,int num){	if(tree==NULL){		tree=(struct node *)malloc(sizeof(struct node));		tree->num=num;		tree->left=tree->right=NULL;	}	else if(num>tree->num)		tree->right=Insert(tree->right,num);	else		tree->left=Insert(tree->left,num);	return tree;}void PrintTree(struct node *t,int loc){//loc为当前节点是其父亲的左儿子还是右儿子 1：左 2：右	struct node *temp=tree;	int count;	if(!t)		return;	PrintTree(t->right,2);		if(t!=tree){//处理第一层		count=1;		count+=(temp->num>9?2:1);		for(int i=1;i<=count;i++)			printf(".");		if(t->num>temp->num){			loc=2;			temp=temp->right;		}		else{			loc=1;			temp=temp->left;		}	}	while(temp!=t){//t之前的层		if((loc==1&&temp->num<t->num)||(loc==2&&temp->num>t->num)){			printf("|");		}		else{			printf(".");		}		count=2;		count+=(temp->num>9?2:1);		for(int i=1;i<=count;i++)			printf(".");		if(t->num>temp->num){			temp=temp->right;			loc=2;		}		else{			temp=temp->left;			loc=1;		}	}	//处理t	if(t!=tree){		printf("|-");	}	printf("%d",t->num);	if(t->left||t->right){		printf("-|");	}	cout<<endl;		PrintTree(t->left,1);}int main(){	int num;	while(cin>>num){		tree=Insert(tree,num);	}	PrintTree(tree,0);	return 0;}