devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

PAT (Advanced Level) Practice_pat (advanced level) practice什么意思

作者：小小林熬夜学编程 | 2024-05-26 16:06:44

赞

踩

pat (advanced level) practice什么意思

 

 

 

1001：A+B Format （20 分）（AC：stack）

注意要点：

1.注意0的时候的问题。

  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4.  
  5. stack<char> s;
  6.  
  7. int main(){
  8. 	int a , b , count = 0 , n = 0;
  9. 	scanf("%d %d" , &a , &b);
  10. 	int t = a + b;
  11. 	//全是对于t的正数操作// 
  12. 	if(t < 0){
  13. 		t = -t;
  14. 	}
  15. 	//对于 t 的处理// 
  16. 	while(t != 0){
  17. 		char c = t % 10 + '0';
  18. 		s.push(c);
  19. 		count ++;
  20. 		if(count  == 3){
  21. 			s.push(',');
  22. 			count =0;
  23. 		}
  24. 		t /= 10;
  25. 	}
  26. 	//判断正负//
  27. 	if(a + b < 0){
  28. 		printf("-");
  29. 	} 
  30. 	if(a + b == 0){
  31. 		printf("0");
  32. 		return 0;
  33. 	}
  34. 	//输出//
  35. 	while(!s.empty()){
  36. 		if(n == 0 && s.top() == ','){
  37. 			s.pop();
  38. 			n ++;
  39. 			continue;
  40. 		}
  41. 		printf("%c" , s.top());
  42. 		s.pop();
  43. 		n ++;
  44. 	} 
  45. 	return 0;
  46. }

 

1002：A+B for Polynomials (25)（AC）

注意要点：

1.float数组类型初始化的时候切记内部数字也得是0.0，要不然真的死都不知道怎么死的。

2.多组数据只要是后面不用的，都可以共用一个。

  1. #include<iostream>
  2. using namespace std;
  3. int main() {
  4. 	int M;
  5. 	int a; 
  6. 	float b;
  7. 	int num = 0;
  8. 	float p[1005] = {0.0} ; //注意这个地方//
  9. 	scanf("%d" , &M);
  10. 	//第一行// 
  11. 	for(int i = 0 ; i < M ; i ++) {
  12. 		scanf("%d %f" , &a , &b);
  13. 		p[a] += b ;
  14. 	}
  15. 	//第二行// 
  16. 	getchar();
  17. 	scanf("%d" , &M);//可以直接覆盖// 
  18. 	for(int i = 0 ; i < M ; i ++) {
  19. 		scanf("%d %f" , &a , &b);
  20. 		p[a] += b; //在第一行基础之上往上加// 
  21. 	}
  22. 	//统计个数// 
  23. 	for(int i = 0 ; i < 1005 ; i ++){
  24. 		if(p[i] != 0) num ++;
  25. 	}
  26. 	printf("%d" , num);
  27. 	for(int i = 10 ; i >= 0 ; i --){
  28. 		if(p[i] != 0) 
  29. 			printf(" %d %.1f" , i , p[i]); 
  30. 		
  31. 	}
  32. 	return 0;
  33. }

 

1003：Emergency （25 分）（AC）

注意要点：

1.Dijkstra + BFS

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. const int MAXV = 505;
  6. const int INF = 1000000;
  7.  
  8. int G[MAXV][MAXV] , num[MAXV] , w[MAXV] , d[MAXV] , weight[MAXV];
  9. int N , M , S , D; 
  10. bool vis[MAXV] = { 0 };
  11.  
  12. void Dijkstra(int S){
  13. 	//初始化//
  14. 	fill(d , d + MAXV , INF);
  15. 	memset(w , 0 , sizeof(w));
  16. 	memset(num , 0 , sizeof(num));
  17. 	//开始各种标记//
  18. 	d[S] = 0;
  19. 	w[S] = weight[S];
  20. 	num[S] = 1;
  21. 	//遍历每个点//
  22. 	for(int i = 0 ; i < N ; i ++) {
  23. 	//找到d之中最小的//
  24. 		int u = -1 , MIN = INF;
  25. 		for(int j = 0 ; j < N ; j ++){
  26. 			if(vis[j] == false && d[j] < MIN){
  27. 				u = j;
  28. 				MIN = d[j];
  29. 			}
  30. 		}
  31. 	//特殊情况找不到，退出//
  32. 		if(u == -1) return ;
  33. 		vis[u] = true;
  34. 	//修改值// 
  35. 		for(int v = 0 ; v < N ; v ++) {
  36. 			if(vis[v] == false && G[u][v] != INF){
  37. 				if(d[u] + G[u][v] < d[v]){
  38. 					d[v] = d[u] + G[u][v];
  39. 					w[v] = w[u] + weight[v];
  40. 					num[v] = num[u];
  41. 				}
  42. 				else if(d[u] + G[u][v] == d[v]){
  43. 						if(w[u] + weight[v] > w[v])
  44. 							w[v] = w[u] + weight[v];
  45. 						num[v] += num[u];
  46. 				}
  47. 			}
  48. 		}
  49. 	}
  50. }
  51.  
  52. int main() {
  53. 	int a , b , c;
  54. 	scanf("%d %d %d %d" , &N , &M , &S , &D);
  55. 	for(int i = 0 ; i < N ; i ++) {
  56. 		scanf("%d" , &weight[i]);//救援队既是权值//		 
  57. 	}
  58. 	
  59. 	fill(G[0] , G[0] + MAXV * MAXV , INF);
  60. 	
  61.  	for(int i = 0 ; i < M ; i ++) {
  62. 		scanf("%d %d %d" , &a , &b , &c);
  63. 		G[a][b] = c;
  64. 		G[b][a] = c;
  65. 	}
  66. 	Dijkstra(S);
  67. 	printf("%d %d\n" , num[D] , w[D]);
  68. 	return 0;
  69. }

 

1004：Counting Leaves （30 分）（AC：DFS）

注意要点：

1.一开始的思路是去建立一棵树，想了想发现DFS也可以做出来。

2.强化DFS问题解决方式：递归 + 边界判断。 

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. const int MAXN = 105;
  5.  
  6. vector<int> v[MAXN];
  7. int J[MAXN];
  8. int D = -1;
  9.  
  10. void DFS(int x , int depth){
  11.     //边界// 
  12. 	if(v[x].size() == 0){
  13.     	J[depth] ++;
  14.     	D = max(depth , D);
  15.     	return ;
  16. 	}
  17. 	//递归//
  18. 	for(int i = 0 ; i < v[x].size() ; i ++){
  19. 		DFS(v[x][i] , depth + 1);
  20. 	} 
  21. }
  22.  
  23. int main(){
  24. 	int N , M , ID , K , a;
  25. 	//输入// 
  26. 	scanf("%d %d" , &N , &M);
  27. 	for(int i = 0 ; i < M ; i ++){
  28. 		scanf("%d %d" , &ID , &K);
  29. 		for(int j = 0 ; j < K ; j ++){
  30. 			scanf("%d" , &a);
  31. 			v[ID].push_back(a);
  32. 		}
  33. 	}
  34. 	//DFS//
  35. 	DFS(1 , 0);
  36. 	//输出// 
  37. 	for(int i = 0 ; i <= D ; i ++){
  38. 		if(i == 0){
  39. 			printf("%d" , J[i]);
  40. 		}
  41. 		else{
  42. 			printf(" %d" , J[i]);
  43. 		}
  44. 	}
  45. 	return 0;
  46. }

 

1005：Spell It Right （20 分）（AC：Vector）

注意要点：

1.0的情况考虑一下。

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<int> v;
  6.  
  7. int main(){
  8. 	int sum = 0 ;
  9. 	char a;
  10. 	char b[10][10] = {"zero" , "one" , "two" , "three" , "four" , "five" , "six" , "seven" , "eight" , "nine"};
  11. 	//输入// 
  12. 	while(scanf("%c" , &a) == 1){
  13. 		if(a != '\n')
  14. 			sum =sum + (a - '0');
  15. 	}
  16. 	//倒着插入//
  17. 	if(sum == 0){
  18. 		printf("zero");
  19. 	} 
  20. 	else{
  21. 		while(sum != 0){
  22. 			int c =  sum % 10;
  23. 			v.push_back(c);
  24. 			sum /= 10;	
  25. 		}
  26. 		//输出//
  27. 		for(int i = v.size() - 1 ; i >= 0 ; i --){
  28. 			if(i == v.size() - 1){
  29. 				printf("%s" , b[v[i]]);
  30. 			}
  31. 			else{
  32. 				printf(" %s" , b[v[i]]);
  33. 			}
  34. 		}
  35. 	}
  36. 	return 0;
  37. }

 

1007：Maximum Subsequence Sum （DP）

掌握了一个基本的dp问题的思路。

先写边界，随后确定递推公式。基本的模型一定要先理解清楚，随后做题才能在此基础之上进一步求解。

  1. #include<iostream>
  2. using namespace std;
  3. const int MAXN = 10005;
  4.  
  5. int main(){
  6. 	int K;
  7. 	int a[MAXN] , dp[MAXN];//dp的含义是指，在这个数值状态下的最大的数值是多少// 
  8. 	int s[MAXN] = { 0 };
  9. 	bool flag = true;
  10. 		
  11. 	scanf("%d" , &K);
  12. 	for(int i = 0 ; i < K ; i ++){
  13. 		scanf("%d" , &a[i]);
  14. 		if(a[i] >= 0){
  15. 			flag = false;
  16. 		}
  17. 	}
  18. 	if(flag == true){//如果有一个数字是负数的话，则直接输出// 
  19. 		printf("%d %d %d" , 0 , a[0] , a[K - 1]);
  20. 		return 0;
  21. 	}
  22. 	dp[0] = a[0];//第一个数值就是其本身//
  23. 	for(int i = 1 ; i < K ; i ++){
  24. 		if(dp[i - 1] + a[i] > a[i]){ // 
  25. 			dp[i] = dp[i - 1] + a[i]; 
  26. 			s[i] = s[i - 1];
  27. 		}
  28. 		else{
  29. 			dp[i] = a[i];
  30. 			s[i] = i; 
  31. 		}		
  32. 	} 
  33. 	int n = 0;
  34. 	for(int i = 1 ; i < K ; i ++){
  35. 		if(dp[i] > dp[n]){
  36. 			n = i;
  37. 		}
  38. 	} 
  39. 	printf("%d %d %d\n" , dp[n] , a[s[n]] , a[n]);
  40. 	return 0;
  41. }

 

1008：Elevator （20 分）（AC：vector数学问题）

注意要点：

无。

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<int> v;
  6.  
  7. int main(){
  8. 	int N , a , d = 0;
  9. 	//输入// 
  10. 	scanf("%d" , &N);
  11. 	for(int i = 0 ; i < N ; i ++){
  12. 		scanf("%d" , &a);
  13. 		v.push_back(a);
  14. 	}
  15. 	//层数操作//
  16. 	for(int i = 0 ; i < v.size() ; i ++){
  17. 		//一层// 
  18. 		if(i == 0){
  19. 			d = d + (v[i] - 0) * 6 + 5;
  20. 		}
  21. 		//二层以上 ， 比你高// 
  22. 		else if( i != 0 && (v[i] > v[i - 1])){
  23. 			d = d + ((v[i] - v[i - 1]) * 6 + 5);
  24. 		}
  25. 		// 二层以上，比你低//
  26. 		else{
  27. 			d = d + ((v[i - 1] - v[i]) * 4 + 5);
  28. 		} 
  29. 	} 
  30. 	printf("%d" , d);
  31. 	return 0;
  32. }

 

1009：Product of Polynomials （25 分）（AC：数学模拟）

注意要点：

1.审题，注意这个题目是要求乘法，我一开始做成加法了， 浪费了很多时间。

2.double类型只能由lf来接，否则都是根本接不到。

3.这个题思路也是很清晰，几乎不用拐弯，我开了两个数组的原因是不想交叉起来不好修改。

  1. #include<iostream>
  2. using namespace std;
  3. int main(){
  4. 	int N , M , a , c , maxn = -1 , count = 0;
  5. 	double b , d;
  6. 	double A[10000] = { 0 } , B[10000] = { 0 };
  7. 	//输入// 
  8. 	scanf("%d" , &N);
  9. 	for(int i = 0 ; i < N ; i ++){
  10. 		scanf("%d %lf" , &a , &b);
  11. 		A[a] = A[a] + b;
  12. 		//边界//
  13. 		if(a > maxn){
  14. 			maxn = a; 
  15. 		}	
  16. 	}
  17. 	scanf("%d" , &M);
  18. 	for(int j = 0 ; j < M ; j ++){
  19. 		scanf("%d %lf" , &c , &d);
  20. 		//换到B数组里面// 
  21. 		for(int i = maxn ; i >= 0 ; i --){
  22. 			if(A[i] != 0){
  23. 				B[i + c] = B[i + c] + d * A[i];
  24. 				if(i + c > maxn){
  25. 					maxn = i + c;
  26. 				} 
  27. 			}	
  28. 		}	
  29. 	}
  30. 	for(int i = 0 ; i <= maxn ; i ++){
  31. 		if(B[i] != 0){
  32. 			count ++;
  33. 		}
  34. 	}
  35. 	//输出//
  36. 	printf("%d " , count);
  37. 	for(int i = maxn ; i >= 0 ; i --){
  38. 		if(B[i] != 0.0){
  39. 			printf("%d %.1lf" , i , B[i]);
  40. 			count --;
  41. 			if(count > 0)
  42. 				printf(" ");
  43. 		}
  44. 	} 
  45. 	return 0;
  46. }

 

1011：World Cup Betting （20 分）（AC：数学模拟）

注意要点：

1.这个输出着实牛啤，还能这么输出。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main(){
  5. 	float a, sum = 1 ;
  6. 	int k;
  7. 	char S[3] = {'W' , 'T' , 'L'};//对应字符表// 
  8. 	//输入// 
  9. 	for(int i = 0 ; i < 3 ; i ++){
  10. 		float max = -1.0 ;
  11. 		for(int j = 0 ; j < 3 ; j ++){
  12. 			scanf("%f" , &a);
  13. 			if(a > max){
  14. 				max = a;
  15. 				k = j;
  16. 			}
  17. 		}
  18. 		printf("%c " , S[k]);
  19. 		sum *= max;
  20. 	}
  21. 	//输出2//
  22. 	printf("%.2f" , (sum * 0.65 - 1) * 2); 
  23. 	return 0;
  24. }

 

1013：Battle Over Cities （25 分）（AC ：DFS ， 并查集）

注意要点：

1.dfs之后改用连接表，不要使用图了。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<vector>
  5. using namespace std;
  6. const int INF = 10000000;
  7.  
  8. vector<int> v[1005];
  9. int c;
  10. bool vis[1005];
  11. void dfs(int e){
  12. 	if(e == c) return ;
  13. 	vis[e] = true;
  14. 	for(int i = 0 ; i < v[e].size() ; i ++){
  15. 		if(vis[v[e][i]]== false){
  16. 			dfs(v[e][i]);
  17. 		}
  18. 	}
  19. }
  20.  
  21. int main(){
  22. 	int N , M , K ,a , b;
  23. 	//输入// 
  24. 	scanf("%d %d %d" , &N , &M , &K);
  25. 	for(int i = 0 ; i < M ; i ++){
  26. 		scanf("%d %d" , &a , &b);
  27. 		v[a].push_back(b);
  28. 		v[b].push_back(a);
  29. 	}
  30. 	//输出//
  31. 	for(int i = 0 ; i < K ; i ++){
  32. 		scanf("%d" , &c);
  33. 		memset(vis , false , sizeof(vis));
  34. 		int block = 0;
  35. 		for(int i = 1 ; i <= N ; i ++){
  36. 			if(i != c && vis[i] == false){
  37. 				dfs(i);
  38. 				block ++;
  39. 			}
  40. 		}
  41. 		printf("%d\n" , block - 1);	
  42. 	} 
  43. 	return 0;
  44. }

 

1020：Tree Traversals （25 分）(AC)

注意要点：

2.这个层序遍历的这个地方非常容易错，修改了两三次才AC了。

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. struct node{
  5. 	int data;
  6. 	node* lchild;
  7. 	node* rchild;
  8. };
  9.  
  10. int pos[55] , in[55];
  11. int N; 
  12. //利用后根数列和中根数列求原来的数列// 
  13. node* creat(int posL , int posR , int inL , int inR) {
  14. 	//边界// 
  15. 	if(posL > posR){
  16. 		return NULL;
  17. 	}
  18. 	//求根节点// 
  19. 	node* root = new node;
  20. 	root->data = pos[posR];
  21. 	int k;
  22. 	for(k = inL ; k <= inR ; k ++) {
  23. 		if(in[k] == pos[posR])
  24. 			break;
  25. 	}
  26. 	//左右分支// 
  27. 	int numleft = k - inL;
  28. 	root->lchild = creat(posL , posL + numleft - 1 , inL , k - 1);//易错//
  29. 	root->rchild = creat(posL + numleft , posR - 1, k + 1 , inR);
  30. 	return root;
  31. }
  32.  
  33. //利用BFS来输出这个层序遍历。// 
  34. int num = 0 ; 
  35. void BFS(node* root) {
  36. 	queue<node*> q;
  37. 	q.push(root);
  38. 	while(!q.empty()){
  39. 		node* t = q.front();
  40. 		q.pop();
  41. 		printf("%d" , t->data);
  42. 		num ++;
  43. 		if(num < N) printf(" ");
  44. 		if(t->lchild != NULL)	q.push(t->lchild);
  45. 		if(t->rchild != NULL)	q.push(t->rchild);
  46. 	}
  47. }
  48.  
  49. int main() {
  50. 	scanf("%d" , &N);
  51. 	for(int i = 0 ; i < N ; i ++) {
  52. 		scanf("%d" , &pos[i]);
  53. 	}
  54. 	for(int i = 0 ; i < N ; i ++) {
  55. 		scanf("%d" , &in[i]); 
  56. 	}
  57. 	node* root = creat(0 , N - 1 , 0 , N - 1);
  58. 	BFS(root);
  59. 	return 0;	 
  60. }

 

1030：Travel Plan （30 分）（AC：Dijkstra第二形态 + 记忆化DFS）

注意要点：

1.这个地方注意这是个无向图。需要注意来回的数值都可以。

2.巧了，不知道为什么PTA的数值题目都可以用 Matrix 来做。看来数据还是小。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. const int MAXN = 505;
  6. const int INF = 100005;
  7.  
  8. //初始化定义// 
  9. int G[MAXN][MAXN];
  10. int cost[MAXN][MAXN]; 
  11. int d[MAXN] , x[MAXN];
  12. int pre[MAXN];
  13. bool vis[MAXN];
  14. int N , M , S , D;
  15. int a , b , c , de;
  16.  
  17. void Dijkstra(int s){
  18. 	fill(d , d + MAXN , INF);
  19. 	fill(x , x + MAXN , INF);
  20. 	//Ñ°ÕÒÇ°Çý½áµã// 
  21. 	for(int i = 0 ; i < N ; i ++){
  22. 		pre[i] = i;
  23. 	}
  24. 	d[s] = 0;
  25. 	x[s] = 0;
  26. 	for(int i = 0 ; i < N ; i ++){
  27. 		int u = -1 , MIN = INF;
  28. 		//第一步：找最小值// 
  29. 		for(int j = 0 ; j < N ; j ++){
  30. 			if(vis[j] == false && d[j] < MIN){
  31. 				MIN = d[j];
  32. 				u = j;
  33. 			}
  34. 		}
  35. 		//第二步：确定范围//
  36. 		if(u == -1) return ;
  37. 		//第三步：更新数值//
  38. 		vis[u] = true; 
  39. 		for(int v = 0 ; v < N ; v ++){
  40. 			if(vis[v] == false && G[u][v] != INF){
  41. 				if(d[u] + G[u][v] < d[v]){
  42. 					d[v] = d[u] + G[u][v];
  43. 					x[v] = x[u] + cost[u][v];
  44. 					pre[v] = u;
  45. 				}
  46. 				else if(d[u] + G[u][v] == d[v]){
  47. 					if(x[u] + cost[u][v] < x[v]){
  48. 						x[v] = x[u] + cost[u][v];
  49. 						pre[v] = u;
  50. 					}
  51. 				}
  52. 			}
  53. 		}
  54. 	}
  55. }
  56.  
  57. //记忆化搜索// 
  58. void DFS(int v){
  59. 	if(v == S){
  60. 		printf("%d " , S);
  61. 		return ;
  62. 	}
  63. 	DFS(pre[v]);
  64. 	printf("%d " , v);
  65. }
  66.  
  67. int main(){
  68. 	//初始化数据// 
  69. 	fill(d , d + MAXN , false);
  70. 	fill(G[0] , G[0] + MAXN * MAXN , INF);
  71. 	//ÊäÈë// 
  72. 	scanf("%d %d %d %d" , &N , &M , &S , &D);
  73. 	for(int i = 0 ; i < M ; i ++){
  74. 		scanf("%d %d %d %d" , &a , &b , &c , &de);
  75. 		G[a][b] = c;
  76. 		G[b][a] = c;
  77. 		cost[a][b] = de;
  78. 		cost[b][a] = de;
  79. 	}
  80. 	//最短路径//
  81. 	Dijkstra(S);
  82. 	//输出//
  83. 	DFS(D);
  84. 	printf("%d %d\n" , d[D] , x[D]); 
  85. }

 

1031：Hello World for U （20 分）（AC：打印图案）

思路提示：

1.首先需要确定n1 ， n2 , n3的数值，其次按照边框再每一个打印出来，最后二维数组写出。

注意要点：

1.最后强调一次这个memset这个功能。在cstring头文件下。

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. int main(){
  5. 	char s[100];
  6. 	char m[100][100];
  7. 	memset(m , ' ' , sizeof(m)); 
  8. 	scanf("%s" , s);
  9. 	//确定n1 , n2 , n3 //
  10. 	int len = strlen(s) + 2;
  11. 	int n1 = len / 3;
  12. 	int n3 = n1;
  13. 	int n2 = len / 3 + len % 3;
  14. 	//填入数组中//
  15. 	int k = 0 ;
  16. 	for(int i = 0; i < n1 ; i ++){//n1// 
  17. 		m[i][0] = s[k ++];
  18. 	} 
  19. 	for(int i = 1 ; i <= n2 - 2 ; i ++){//n2// 
  20. 		m[n1 - 1][i] = s[k ++];
  21. 	}
  22. 	for(int i = n3 - 1 ; i >= 0 ; i --){//n3// 
  23. 		m[i][n2 - 1] = s[k ++];
  24. 	}
  25. 	//输出// 
  26. 	for(int i = 0 ; i < n1 ; i ++){
  27. 		for(int j = 0 ; j < n2 ; j ++){
  28. 			printf("%c" , m[i][j]);
  29. 		}
  30. 		printf("\n");
  31. 	}
  32. 	return 0;
  33. }

 

1033：Sharing （25 分）（AC：模拟链表）

思路提示：

1.模拟链表的技巧。

注意要点：

%05d，超容易犯错。

  1. #include<iostream>
  2. const int MAXN = 100005;
  3. using namespace std;
  4. struct node{
  5. 	char data;
  6. 	int next;
  7. }Node[MAXN];
  8. int main(){
  9. 	int s1 , s2 , n , a , c , k = 0;
  10. 	char b;
  11. 	bool L[MAXN] = { false };
  12. 	//输入// 
  13. 	scanf("%d %d %d" , &s1 , &s2 , &n);
  14. 	for(int i = 0 ; i < n ; i ++){
  15. 		scanf("%d %c %d" , &a , &b , &c);
  16. 		Node[a].data = b;
  17. 		Node[a].next = c;
  18. 	}
  19. 	//第一轮//
  20. 	int root = s1; 
  21. 	while(root != -1){
  22. 		L[root] = true;
  23. 		root = Node[root].next;	
  24. 	}
  25. 	L[root] = true;
  26. 	
  27. 	//第二轮:找交点//
  28. 	int root2 = s2;
  29. 	while(root2 != -1){
  30. 		if(L[root2] == true){
  31. 			printf("%05d" , root2);
  32. 			L[root2] = false;//防止下次判断//	
  33. 			break;
  34. 		}
  35. 		root2 = Node[root2].next;	
  36. 	}
  37. 	if(L[root2] == true)
  38. 		printf("-1");		
  39. 	return 0;
  40. }

 

1035：Password （20 分）(AC:：水题)

思路提示：请认真读题。

注意要点：

1.这个地方注意这个多数和单一的情况。

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. struct A{
  5. 	string b;//第一个字符串//
  6. 	string c;//第二个字符串//
  7. 	bool flag;//判断这个是否修改过//
  8. }a[1005];
  9.  
  10. int main(){
  11. 	int n , count = 0;
  12. 	scanf("%d" , &n);
  13. 	for(int i = 0 ; i < n ; i ++){
  14. 		cin >> a[i].b >> a[i].c;
  15. 		for(int j = 0 ; j < a[i].c.size() ; j ++){//不停的进行修改保存// 
  16. 			if(a[i].c[j] == '1'){
  17. 				a[i].c[j] = '@';
  18. 				a[i].flag = 1;
  19. 				continue;
  20. 			}
  21. 			if(a[i].c[j] == '0'){
  22. 				a[i].c[j] = '%';
  23. 				a[i].flag = 1;
  24. 				continue;
  25. 			}
  26. 			if(a[i].c[j] == 'l'){
  27. 				a[i].c[j] = 'L';
  28. 				a[i].flag = 1;
  29. 				continue;
  30. 			}
  31. 			if(a[i].c[j] == 'O'){
  32. 				a[i].c[j] = 'o';
  33. 				a[i].flag = 1;
  34. 				continue;
  35. 			}
  36. 		} 
  37. 		if(a[i].flag == 1){
  38. 				count ++;//有问题个数的统计// 
  39. 		}
  40. 	}
  41. 	//输出// 
  42. 	if(n == 1 && count == 0){//1的情况// 
  43. 		printf("There is 1 account and no account is modified");
  44. 	} 
  45. 	else if(count == 0){//多数的情况// 
  46. 		printf("There are %d accounts and no account is modified" , n);
  47. 	}
  48. 	else{//输出错误的情况// 
  49. 		printf("%d\n" , count);
  50. 		for(int i = 0 ; i < n ; i ++){
  51. 			if(a[i].flag == 1){
  52. 				cout << a[i].b << " " << a[i].c;
  53. 				count --;
  54. 				if(count != 0){
  55. 					printf("\n");
  56. 				}
  57. 			}	
  58. 		}
  59. 	}
  60. 	return 0;
  61. }

 

1036：Boys vs Girls （25 分）（AC ：水题）

注意要点：注意读题，缺的地方写Absent。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<math.h>
  4. using namespace std;
  5.  
  6. int main(){
  7. 	int n , maxm = 10000 , maxn = -1 ;
  8. 	string maxmID , maxmname , maxnID , maxnname;
  9. 	scanf("%d" , &n);
  10. 	for(int i = 0 ; i < n ; i ++){
  11. 		int number;
  12. 		char sex ;
  13. 		string ID , name;
  14. 		cin >> name >> sex >> ID >> number;
  15. 		if(sex == 'M' && maxm > number){//成绩为男性// 
  16. 			maxmname = name;
  17. 			maxmID = ID;
  18. 			maxm = number;
  19. 		}
  20. 		if(sex == 'F' && maxn < number){//成绩为女性// 
  21. 			maxnname = name;
  22. 			maxnID = ID;
  23. 			maxn = number;
  24. 		}
  25. 	}
  26. 	//输出//
  27. 	if(maxm == 10000 || maxn == -1){//缺一个// 
  28. 		if(maxm == 10000)	
  29. 			cout << maxnname << " " << maxnID << endl << "Absent" << endl << "NA";
  30. 		if(maxn == -1)
  31. 			cout << "Absent" << endl << maxmname << " " << maxmID << endl << "NA";	
  32. 		
  33. 	}
  34. 	else{//全有// 
  35. 		cout << maxnname << " " << maxnID << endl;
  36. 		cout << maxmname << " " << maxmID << endl;
  37. 		printf("%d" , abs(maxn - maxm));	
  38. 	}
  39. 	return 0;
  40. }

 

1040：Longest Symmetric String （25 分）（AC：DP）

注意要点：控制每次移动的长度，从1-3。

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4.  
  5. int dp[1005][1005];
  6.  
  7. int main(){
  8. 	string s;//注意小写string// 
  9. 	int ans = 1;
  10. 	getline(cin , s);//专用空格// 
  11. 	int len = s.size();
  12. 	memset(dp , 0 , sizeof(dp));//长度为 1和 2 的情况// 
  13. 	for(int i = 0 ; i < len ; i ++){
  14. 		dp[i][i] = 1;
  15. 		if(i < len - 1){
  16. 			if(s[i] == s[i + 1]){
  17. 				dp[i][i + 1] = 1; 
  18. 				ans = 2;
  19. 			}
  20. 		}
  21. 	}
  22. 	//处理数据长度为3// 
  23. 	for(int L = 3 ; L <= len ; L ++){
  24. 		for(int i = 0 ; i + L - 1 < len ; i ++){
  25. 			int j = i + L - 1;//记录末尾值// 
  26. 			if(s[i] == s[j] && dp[i + 1][j - 1] == 1){
  27. 				dp[i][j] = 1;
  28. 				ans = L;
  29. 			}
  30. 		}
  31. 	}
  32. 	printf("%d" , ans);
  33. 	return 0;
  34. }

 

1043：Is It a Binary Search Tree （25 分）（AC）

注意要点：

这个题目非常好，典型的二叉搜索树的体现。操作类似于树的操作。

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. struct node{
  6. 	int data;
  7. 	node *left;
  8. 	node *right;
  9. };
  10.  
  11. void insert(node* &root , int a) {
  12. 	if(root == NULL){
  13. 		root = new node;
  14. 		root->data = a;
  15. 		root->left = NULL;
  16. 		root->right = NULL;	
  17. 		return ;
  18. 	}
  19. 	if(a < root->data)	insert(root->left , a);
  20. 	else	insert(root->right , a);
  21. }
  22.  
  23. void preorder(node* root , vector<int>&v){
  24. 	if(root == NULL){
  25. 		return ;
  26. 	}
  27. 	v.push_back(root->data);
  28. 	preorder(root->left , v);
  29. 	preorder(root->right , v);
  30. }
  31.  
  32. void preorderM(node* root , vector<int>&v){
  33. 	if(root == NULL){
  34. 		return ;
  35. 	}
  36. 	v.push_back(root->data);
  37. 	preorderM(root->right , v);
  38. 	preorderM(root->left , v);
  39. }
  40.  
  41. void postorder(node* root , vector<int>&v){
  42. 	if(root == NULL){
  43. 		return ;
  44. 	}
  45. 	postorder(root->left , v);
  46. 	postorder(root->right , v);
  47. 	v.push_back(root->data);
  48. }
  49.  
  50. void postorderM(node* root , vector<int>&v){
  51. 	if(root == NULL){
  52. 		return ;
  53. 	}
  54. 	postorderM(root->right , v);
  55. 	postorderM(root->left , v);
  56. 	v.push_back(root->data);
  57. }
  58.  
  59. vector<int>origin , pre , preM , post , postM;//初始， 前序 ， 后序 ， 平衡前序 ， 平衡后序//  
  60. int main() {
  61. 	int N , a;
  62. 	node *root = NULL;
  63. 	//输入// 
  64. 	scanf("%d" , &N);
  65. 	for(int i = 0 ; i < N ; i ++) {
  66. 		scanf("%d" , &a);
  67. 		origin.push_back(a);
  68. 		insert(root , a); 
  69. 	}
  70. 	//前序//
  71. 	preorder(root , pre);
  72. 	//镜像前序//
  73. 	preorderM(root , preM);
  74. 	//后序//
  75. 	postorder(root , post); 
  76. 	//镜像后序//
  77. 	postorderM(root , postM);
  78. 	if(origin == pre){
  79. 		printf("YES\n");
  80. 		for(int i = 0 ;  i < post.size() ; i ++) {
  81. 			if(i == post.size() - 1) 
  82. 				printf("%d" , post[i]);
  83. 			else	
  84. 				printf("%d " , post[i]);
  85. 		}
  86. 	} 
  87. 	else if(origin == preM){
  88. 			printf("YES\n");
  89. 			for(int i = 0 ;  i < postM.size() ; i ++) {
  90. 				if(i == postM.size() - 1) 
  91. 					printf("%d" , postM[i]);
  92. 				else	
  93. 					printf("%d " , postM[i]);
  94. 			}
  95. 	}
  96. 	else{
  97. 		printf("NO\n");
  98. 	}
  99. 	return 0;
  100. } 
  101.


 

1045：Favorite Color Stripe（LCS）

这个题目其实LIS也是可以做的，但是我没有做。以后有时间补上。

一开始我还在想这个地方会不会有冲突出现，但是一想，LCS已经完美的解决了这个问题，关键是这个地方他有个重复的问题在里面。当前的状态如果没有匹配到的话，那就直接把前面的数值补进来。

  1. #include<iostream>
  2. using namespace std;
  3. const int MAXM = 205;
  4. const int MAXL = 10005;
  5.  
  6. int a[MAXM] , b[MAXL] , dp[MAXM][MAXL];//这个要定义到外面，内部空间不够会报错.dp表示当前的最大的数值// 
  7.  
  8. int main(){
  9. 	int n , m , l;
  10. 	scanf("%d" , &n);
  11. 	scanf("%d" , &m);
  12. 	for(int i = 1 ; i <= m ; i ++){
  13. 		scanf("%d" , &a[i]);
  14. 	}
  15. 	scanf("%d" , &l);
  16. 	for(int i = 1 ; i <= l ; i ++){
  17. 		scanf("%d" , &b[i]);
  18. 	}
  19. 	//边界//
  20. 	for(int i = 0 ; i <= m ; i ++){
  21. 		dp[i][0] = 0;
  22. 	} 
  23. 	for(int i = 0 ; i <= l ; i ++){
  24. 		dp[0][i] = 0;
  25. 	}
  26. 	//递推// 
  27. 	for(int i = 1 ; i <= m ; i ++){
  28. 		for(int j = 1 ; j <= l ; j ++){
  29. 			if(a[i] == b[j]){
  30. 				dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]) + 1;
  31. 			}
  32. 			else{
  33. 				dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
  34. 			}
  35. 		}
  36. 	}
  37. 	printf("%d\n" , dp[m][l]);
  38. 	return 0;
  39. }

 

1047：Student List for Course（25 分）（AC）

注意要点：

1.这个地方因为不需要输入名字，所以不用hash了。

2.注意字典序的用法。

3.这个地方C的写法。二维数组换成了几个一维数组字符串。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<vector>
  4. #include<algorithm>
  5. using namespace std;
  6. char C[40005][5];
  7. vector<int> course[40005];
  8.  
  9. bool cmp(int a , int b) {
  10. 	return strcmp(C[a] , C[b]) < 0 ;//这个地方注意字典序的排列//
  11. }
  12.  
  13. int main(){
  14. 	int N , K;
  15. 	int c , d;
  16. 	scanf("%d %d" , &N , &K);
  17. 	for(int i = 0 ; i < N ; i ++) {
  18. 		scanf("%s %d" , C[i] , &c);
  19. 		for(int j = 0 ; j < c ; j ++) {
  20. 			scanf("%d" , &d);
  21. 			course[d].push_back(i);
  22. 		}
  23. 	}
  24. 	//输出//
  25. 	for(int i = 1 ; i <= K ; i ++) {
  26. 		printf("%d %d\n" , i , course[i].size());
  27. 		sort(course[i].begin() , course[i].end() , cmp);
  28. 		for(int j = 0 ; j < course[i].size() ; j ++) {
  29. 				printf("%s\n" , C[course[i][j]]);
  30. 		}
  31. 	}
  32. 	
  33. 	return 0;	
  34. }

 

1053：Path of Equal Weight （30 分）（AC）

注意要点：

1.一开始这个路径这个地方需要设置开头的点为0。

2.注意每次实现完之后都要return （因为 return 的是上一级）。

3.这个地方记录一下这个path的问题。其实path本身并不是完全记录每一条的路径。他其实就是一个再覆盖。
本身的地方在于这个输出。这个输出如果对了，就打印在他前面的所有节点的数据就可以了，而他后面的数据则不用管。 

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int N , M , S , path[105];
  7. struct node{
  8. 	int weight;
  9. 	vector<int> child;
  10. }Node[105];
  11.  
  12. bool cmp(int a , int b){
  13. 	return Node[a].weight > Node[b].weight;
  14. }
  15.  
  16. void DFS(int index , int num , int sum){
  17. 	if(sum > S) return ;//超了// 
  18. 	else if(sum == S){//正好// 
  19. 		if(Node[index].child.size()!= 0)
  20. 			return ;
  21. 		for(int i = 0 ; i < num ; i ++){
  22. 			if(i == num - 1)
  23. 				printf("%d\n" , Node[path[i]].weight);
  24. 			else
  25. 				printf("%d " , Node[path[i]].weight);
  26. 		}
  27. 	}
  28. 	else{//不够// 
  29. 		for(int i = 0 ; i < Node[index].child.size() ; i ++){
  30. 			int c= Node[index].child[i];
  31. 			path[num] = c;//这个地方其实是直接覆盖的。 
  32. 			DFS(c , num + 1 , sum + Node[c].weight);	
  33. 		}
  34. 	}
  35. }
  36.  
  37. int main(){
  38. 	scanf("%d %d %d" , &N , &M , &S);
  39. 	for(int i = 0 ; i < N ; i ++){
  40. 		scanf("%d" , &Node[i].weight);
  41. 	}
  42. 	for(int i = 0 ; i < M ; i ++){
  43. 		int id , num , a;
  44. 		scanf("%d %d" , &id , &num);
  45. 		for(int j = 0 ; j < num ; j ++){
  46. 			scanf("%d" , &a);
  47. 			Node[id].child.push_back(a);
  48. 		}
  49. 		sort(Node[id].child.begin() , Node[id].child.end() , cmp);
  50. 	}
  51. 	path[0] = 0;//把id放进来// 
  52. 	DFS(0 , 1 , Node[0].weight);//起始点的位置数码 , 当前的元素的个数，当前元素的和// 
  53. 	return 0;
  54. }

 

1063：Set Similarity（25 分）（AC）

注意要点：

1.注意输入的时候会出点问题，尽可能的分开输入的格式。

  1. #include<iostream>
  2. #include<set>
  3. using namespace std;
  4.  
  5. set<int> a[55];
  6.  
  7. void fun(int b , int c) {
  8. 	int samenum = 0 , allnum = a[c].size();
  9. 	for(set<int>::iterator it = a[b].begin() ; it != a[b].end() ; it ++) {
  10. 		if(a[c].find(*it) != a[c].end())	samenum ++;
  11. 		else	allnum ++;
  12. 	} 
  13. 	printf("%.1f%%\n" , samenum * 100.0 / allnum);
  14. }
  15.  
  16. int main() {
  17. 	int N , n , v;
  18. 	int c , b;
  19. 	int e ;
  20. 	scanf("%d" , &N);
  21. 	for(int i = 1 ; i <= N ; i ++) {
  22. 		scanf("%d" , &n);
  23. 		for(int j = 0 ; j < n ; j ++) {
  24. 			scanf("%d" , &v);
  25. 			a[i].insert(v);
  26. 		}
  27. 	}
  28. 	//输入// 
  29. 	scanf("%d" , &e);
  30. 	for(int i = 0 ; i < e ; i ++) {
  31. 		scanf("%d %d" , &b , &c);
  32. 		fun(b , c);
  33. 	}
  34. 	return 0;
  35. }
  36.

 

1065：A+B and C (64bit) (20)（AC）

注意要点：

1。注意 long long 的写法，范围是（2 ^ - 63 , 2 ^ 63），这个一但求和值必然会超出 long long ，只需要考虑溢出的情况即可。

2。关于溢出，这个东西就是个环形的问题 ，数字超过范围符号变化到但是数字照样加，所以会出现负数的情况。所以你也可以理解，一旦两个正数加成负数必然是溢出，到那时你c的数值必不可能会超过 long long 。与此相反，另外一面情况也可以理解了。

  1. #include<iostream>
  2. using namespace std;
  3. int main() {
  4. 	int N;
  5. 	int numcase = 1;
  6. 	scanf("%d" , &N);
  7. 	for(int i = 0 ; i < N ; i ++) {
  8. 		long long a , b , c;
  9. 		scanf("%lld%lld%lld", &a , &b , &c);
  10. 		long long r = a + b;
  11. 		bool flag ;
  12. 		//溢出情况检查// 
  13. 		if(a > 0 && b > 0 && c < 0) flag = true;
  14. 		else if(a < 0 && b < 0 && c >= 0) flag = false;
  15. 		//正常情况检查// 
  16. 		else if(r > c) flag = true;
  17. 		else flag = false;
  18. 		//输出// 
  19. 		if(flag == true) {
  20. 			printf("Case #%d: true\n" , numcase ++);
  21. 		}
  22. 		else {
  23. 			printf("Case #%d: false\n" , numcase ++);
  24. 		}
  25. 	}
  26. 	return 0;
  27. }

 

1068：Find More Coins（01背包 + 记忆化搜索）

注意要点：注意01背包的含义，前i个硬币恰好有v元可以买到东西。

其次是记忆化搜索。每个状态的时候就会更新这个状态下的硬币的情况，用flag来确定每个硬币的使用情况。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. const int MAXN = 10005;
  6. const int MAXM = 105;
  7. int v[MAXN] , dp[MAXM];//dp的意思是指在前i个硬币恰好有v元能获得的价值// 
  8. bool flag[MAXN] , choice[MAXN][MAXM];
  9. //在这个地方的价格和体积是一样的，所以二者合并起来了// 
  10. bool cmp(int a , int b){//因为这个题目是一个01背包，倒着输出// 
  11. 	return a > b; 
  12. }
  13.  
  14. int main(){
  15. 	memset(dp , 0 , sizeof(dp));
  16. 	int N , M;
  17. 	scanf("%d %d" , &N , &M);
  18. 	for(int i = 1 ; i <= N ; i ++){
  19. 		scanf("%d" , &v[i]);
  20. 	}
  21. 	sort(v + 1 , v + N + 1 , cmp);//从1开始的sort的写法//
  22. 	//状态转移方程// 
  23. 	for(int i = 1 ; i <= N ; i ++){
  24. 		for(int V = M ; V >= v[i] ; V --){//这个地方的V已经代表了所有的情况了// 
  25. 			if(dp[V] <= dp[V - v[i]] + v[i]){ 
  26. 				dp[V] = dp[V - v[i]] + v[i];
  27. 				choice[i][V] = 1;//使用了一枚硬币// 
  28. 			}
  29. 			else choice[i][V] = 0;//没有使用一枚硬币// 
  30. 		}
  31. 	} 
  32. 	if(dp[M] != M){
  33. 		printf("No Solution");	
  34. 	}
  35. 	else{
  36. 		//记录整个路径//
  37. 		int k = N , num = 0 , c = M;
  38. 		while(k >= 0){
  39. 			
  40. 			if(choice[k][c] == 1){//如果说第k个状态下使用了// 
  41. 				flag[k] = true;//该种硬币标记为已经使用过了// 
  42. 				c = c - v[k];//价值减少// 
  43. 				num ++;
  44. 			}
  45. 			else{
  46. 				flag[k] = false;//没有就标记没有//  
  47. 			}
  48. 			k --;//往前翻//
  49. 		} 
  50. 		//输出//
  51. 		for(int i = N ; i >= 1 ; i --){
  52. 			
  53. 			if(flag[i] == true){
  54. 				printf("%d" , v[i]);
  55. 				num --;
  56. 				if(num > 0)	printf(" ");
  57. 			}
  58. 		} 
  59. 	}
  60. 	return 0;
  61. }

 

1069：The Black Hole of Numbers（20 分）（AC）

注意要点：

1.sort的写法.

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int a[5] = { 0 };
  6.  
  7. bool cmp(int a , int b) {
  8. 	return a > b ; 
  9. }
  10.  
  11. void isarray(int N ) {
  12. 	for(int i = 0 ; i < 4 ; i ++) {
  13. 		a[i] = N % 10;
  14. 		N /= 10;
  15. 	}
  16. }
  17.  
  18. int isnumber(int A[]) {
  19. 	int sum = 0;
  20. 	for(int i = 0 ; i < 4 ; i ++) {
  21. 		sum = sum * 10 + a[i];
  22. 	}
  23. 	return sum;
  24. }
  25.  
  26. int main() {
  27. 	int N , min , max;
  28. 	scanf("%d" , &N);
  29. 	while(1) {
  30. 		isarray(N);
  31. 		sort(a , a + 4);
  32. 		min = isnumber(a);//最小值// 
  33. 		sort(a , a + 4 , cmp);
  34. 		max = isnumber(a); //最大值//
  35. 	    N = max - min ; 
  36. 	    printf("%04d - %04d = %04d\n" , max , min , N);
  37.  		if(N == 0 || N == 6174) break; 
  38.     }
  39.     return 0;
  40. }

 

1086：Tree Traversals Again （25 分）（AC）

注意要点：

1.模板题，就是一个模拟一个栈的输入和输出。

  1. #include<iostream>
  2. #include<stack>
  3. #include<cstring>
  4. using namespace std;
  5. const int MAX = 50;
  6.  
  7. stack<int> s;
  8. int N;
  9. int pre[MAX] , in[MAX] , pos[MAX];
  10. struct node{
  11. 	int data;
  12. 	node* lchild;
  13. 	node* rchild;
  14. }; 
  15.  
  16. node* creat(int preL , int preR , int inL , int inR){
  17. 	//范围// 
  18. 	if(preL > preR)
  19. 		return NULL;
  20. 	//创建根节点// 
  21. 	node* root = new node;
  22. 	root->data = pre[preL];
  23. 	//在中序遍历中找到根节点// 
  24. 	int k;
  25. 	for(k = inL ; k <= inR ; k ++) {//千万注意这个地方如果前面定义了，则后面不能定义。// 
  26. 		if(pre[preL] == in[k]){
  27. 			break;
  28. 		}
  29. 	} 
  30. 	//切分寻找；注意技巧：左右的范围其实是对应可以接起来的。// 
  31. 	int numleft = k - inL ; 
  32. 	root->lchild = creat(preL + 1 , preL + numleft , inL , k - 1);
  33. 	root->rchild = creat(preL + numleft + 1 , preR , k + 1 , inR); 
  34. 	return root; 
  35. }
  36.  
  37. int num = 0 ; 
  38. void postorder(node* root) {
  39. 	if(root == NULL)
  40. 		return ;
  41. 	postorder(root->lchild);
  42. 	postorder(root->rchild);
  43. 	printf("%d" , root->data);
  44. 	num ++;
  45. 	if(num < N)
  46. 		printf(" ");
  47. }
  48.  
  49. int main() {
  50. 	int a , preindex = 0 , inindex = 0;
  51. 	char opera[10];
  52. 	//输入操作// 
  53. 	scanf("%d" , &N);
  54. 	for(int i = 0 ; i < 2 * N ; i ++) {
  55. 		scanf("%s" , opera);
  56. 		if(strcmp(opera , "Push") == 0) {
  57. 			scanf("%d" , &a);
  58. 			pre[preindex ++] = a;
  59. 			s.push(a);
  60. 		}
  61. 		else {
  62. 			in[inindex ++] = s.top();
  63. 			s.pop();
  64. 		}
  65. 	}
  66. 	//建树, 这个地方注意是有几个根的数值就补几个。//
  67. 	node* root = creat(0 , N - 1, 0 , N - 1); 
  68. 	//后序遍历// 
  69. 	postorder(root);
  70. 	return 0;
  71. }

 

1101：Quick Sort（25 分）（AC）

注意要点：

1.思路很清晰，但是这个地方可以利用这个小技巧，因为你每次前面的数据就是这个这个最小值了，所以完全没有必要每次都去遍历前面的数据，直接可以与上一个数据进行比较就行。

2.本题目和QS完全没有任何关系，倒像是在给你介绍QS的原理。

2.这个地方注意有个坑，最后需要输出一个回车。我其实很费解这个东西。以后建议所有的题目之后都去写一个回车以防万一。

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. const int INF = 1000000000;
  5. int main() {
  6. 	int N , sum = 0;
  7. 	int a[100005] = {0};
  8. 	int leftmax[100005] = {0};
  9. 	int rightmin[100005] = {0};
  10. 	
  11. 	//input// 
  12. 	scanf("%d" , &N);
  13. 	leftmax[0] = 0;
  14. 	rightmin[N - 1] = INF;
  15. 	for(int i = 0 ; i < N ; i ++) {
  16. 		scanf("%d" , &a[i]);
  17. 	}
  18. 	//leftmax:可修正,其实完全不必每次都把数据遍历一次//
  19. 	for(int i = 1 ; i < N ; i ++) {
  20. 		leftmax[i] = max(leftmax[i - 1] , a[i - 1]);
  21. 	}
  22. 	//rightmin,这个地方你想，如果要是N - 1 的话，N - 1 + 1 不就翻出数组外头去了。。//
  23. 	for(int i = N - 2; i >= 0 ; i --) {
  24. 		rightmin[i] = min(rightmin[i + 1] , a[i + 1]);
  25. 	}
  26. 	//statistic// 
  27. 	for(int i = 0 ; i < N ; i ++) {
  28. 		if(a[i] > leftmax[i] && a[i] < rightmin[i]) {
  29. 			sum ++;
  30. 		}
  31. 	}
  32. 	//output//
  33. 	printf("%d\n" , sum);
  34. 	for(int i = 0 ; i < N ; i ++) {
  35. 		if(a[i] > leftmax[i] && a[i] < rightmin[i]) {
  36. 	    	printf("%d" , a[i]);
  37. 	    	sum--;
  38. 	    	if(sum != 0) printf(" ");
  39. 		}
  40. 	}
  41. 	printf("\n");//无厘头的要求。// 
  42. 	return 0;
  43. }

 

1107：Social Clusters（30 分）（AC）

注意要点：

1/并查集。最难的不是并查集，而是主函数。

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int father[1005] = {0} ; 
  6. int isroot[1005] = {0} ;
  7. int hobby[1005] = {0};
  8.  
  9. void init(int N) {
  10. 	for(int i = 1 ; i <= N ; i ++) {
  11. 		father[i] = i;
  12. 		isroot[i] = false;
  13. 	}
  14. }
  15.  
  16. bool cmp(int a , int b) {
  17. 	return a > b ;
  18. }
  19.  
  20. int findfather(int x) {
  21. 	int a = x;
  22. 	while(x != father[x]) {
  23. 		x = father[x];
  24. 	}
  25. 	while(a != father[a]){
  26. 		int z = a; 
  27. 		a = father[a];
  28. 		father[z] = x ;
  29. 	}
  30. 	return x;
  31. }
  32.  
  33. void Union(int a , int b) {
  34. 	int A = findfather(a);
  35. 	int B = findfather(b);
  36. 	if(A != B) {
  37. 		father[A] = B ; 
  38. 	}
  39. }
  40.  
  41. int main() {
  42. 	int N , k , d , sum = 0;
  43. 	scanf("%d" , &N);
  44. 	init(N);
  45. 	for(int i = 1 ; i <= N ; i ++){
  46. 		scanf("%d: " , &k);
  47. 		for(int j = 0 ; j < k ; j ++) {
  48. 			scanf("%d" , &d);
  49. 			if(hobby[d] == 0) {
  50. 				hobby[d] = i;
  51. 			}
  52. 			Union(i , findfather(hobby[d]));
  53. 		}
  54. 	}
  55. 	
  56. 	for(int i = 1 ; i <= N ; i ++) {
  57. 		isroot[findfather(i)] ++;
  58. 	}
  59. 	
  60. 	for(int i = 1 ; i <= N ; i ++) {
  61. 		if(isroot[i] != 0) {
  62. 			sum ++; 
  63. 		}
  64. 	}
  65. 	
  66. 	sort(isroot + 1 , isroot + N + 1 , cmp);
  67. 	
  68. 	printf("%d\n" , sum);
  69. 	for(int i = 1 ; i <= sum ; i++) {
  70. 			if(i == sum)
  71. 				printf("%d" , isroot[i]);
  72. 			else
  73. 				printf("%d " , isroot[i]);
  74. 	}
  75. 	return 0;
  76. }

1155. Heap Paths

解题思路：参考柳神。有的时候发现并不是不会做题，而是题目真的看不懂。。

1.利用dfs保存每条路径。（在dfs中打印数据）

2.判断大根堆和小根堆。（在大根堆中父亲节点的数据大于儿子节点的数据）

  1.  
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. int n , a[1005];
  7. vector<int> v;
  8.  
  9. void dfs(int x){
  10. 	if(2 * x > n && 2 * x + 1 > n){//×ó¸ù½ÚµãµÄÊýÖµ´óÓÚÕû¸öÊý¾Ý && ÓÒ¸ú½ÚµãµÄÊý¾Ý´óÓÚÕû¸öÊý¾Ý// 
  11. 		if(x <= n){//Õâ¸ö¸ùµÄ½ÚµãûÓгöÁ˽磬µ«ÊÇÕâ¸ö¸ùµÄ½Úµã³öÁ˽磬Ôò˵Ã÷Õâ¸öµØ·½µ½ÁËÄ©¶ËÁË// 
  12. 			for(int i = 0 ; i < v.size() ; i ++){//Õâ¸öµØ·½Ï൱ÓÚÊǶÔÓÚÕû¸ö·¾¶µÄÒ»¸ö±éÀú¡£ 
  13. 				printf("%d%s" , v[i] , i != v.size() - 1 ? " " : "\n");
  14. 			}
  15. 		}
  16. 	}
  17. 	else{
  18. 		v.push_back(a[2 * x + 1]);//ÏȽ«ÓÒ½Úµã·ÅÈ룬±éÀúÓÒ½ÚµãϵÄÊ÷// 
  19. 		dfs(2 * x + 1);
  20. 		v.pop_back();
  21. 		v.push_back(a[2 * x]);//ÔÙ½«×ó½Úµã·ÅÈ룬±éÀú×ó½ÚµãϵÄÊ÷// 
  22. 		dfs(2 * x);
  23. 		v.pop_back(); 
  24. 	}
  25. }
  26.  
  27. int main(){
  28. 	bool ismin = false , ismax = false;
  29. 	scanf("%d" , &n);
  30. 	for(int i = 1 ; i <= n ; i ++){
  31. 		scanf("%d" , &a[i]);
  32. 	}
  33. 	v.push_back(a[1]);
  34. 	dfs(1);
  35. 	for(int i = 2 ; i <= n ; i ++){//Õâ¸öµØ·½´ÓµÚ¶þ¸ö½Úµã¿ªÊ¼,Èç¹û´ÓµÚÒ»¸ö½ÚµãÒ²¿ÉÒÔ// 
  36. 		if(a[i / 2] < a[i])	ismin = true;//Èç¹û×Ó½ÚµãµÄÊýÖµ±È¸ù½ÚµãµÄÊýֵҪСµÄ»°£¬ÊÇ´ó¸ù¶Ñ// 
  37. 		if(a[i / 2] > a[i])	ismax = true;//Èç¹û×Ó½ÚµãµÄÊýÖµ±È¸ù½ÚµãµÄÊýÖµÒª´óµÄ»°£¬ÔòÊÇС¸ù¶Ñ// 
  38. 	}
  39. 	if(ismax == true && ismin == true){
  40. 		printf("Not Heap");
  41. 	}
  42. 	else if(ismax == true){
  43. 		printf("Max Heap");
  44. 	}
  45. 	else if(ismin == true){
  46. 		printf("Min Heap");
  47. 	}
  48. 	
  49. 	return 0;
  50. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/627363
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号