1. 知识点

70封顶，因为……AVL板子忘记了……

2. 分题题解

2.1 1120 Friend Numbers

从小到大输出给定序列的“朋友id(各位相加之和)”

#include
using namespace std;
vector<int>mp(30,0);
set<int>ans;
int N;
int temp,sum;
int CountSum(int num){
	int sum=0;
	while(num){
		sum+=num%10;
		num/=10;
	}
	return sum;
}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&temp);
		sum=CountSum(temp);
		mp[sum]++;
		ans.insert(sum);
	}
	printf("%d\n",ans.size());
	bool flag=false;
	for(set<int>::iterator it=ans.begin();it!=ans.end();it++){
		if(flag){
			printf(" ");
		}else{
			flag=true;
		}
		printf("%d",*it);
	}
	return 0;
} 
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

2.2 1121 Damn Single

输出给定序列中没有对象的人名字

#include
using namespace std;
map<int,int>couple;
vector<int>ans,visitors;
int N,M,u,v;
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d%d",&u,&v);
		couple[u]=v;
		couple[v]=u;
	}
	scanf("%d",&M);
	visitors.resize(M);
	for(int i=0;i<M;i++){
		scanf("%d",&visitors[i]);
	}
	for(int i=0;i<M;i++){
		if(couple.find(visitors[i])!=couple.end()&&find(visitors.begin(),visitors.end(),couple[visitors[i]])!=visitors.end()){
			continue;
		}else{
			ans.push_back(visitors[i]);
		}
	}
	int len=ans.size();
	printf("%d\n",len);
	sort(ans.begin(),ans.end());
	for(int i=0;i<len;i++){
		if(i)printf(" ");
		printf("%05d",ans[i]);
	}
	return 0;
}
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

2.3 1122 Hamiltonian Cycle

判断是否为哈密顿图

#include
using namespace std;
int N,M,K,num,u,v;
vector<int>q,cnt;
vector<vector<bool>>graph;
bool flag;
int main(){
	scanf("%d%d",&N,&M);
	graph.resize(N+1);
	cnt.resize(N+1);
	for(int i=1;i<=N;i++){
		graph[i].resize(N+1);
		fill(graph[i].begin(),graph[i].end(),false);
	}
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		graph[u][v]=true;
		graph[v][u]=true;
	}
	scanf("%d",&K);
	while(K--){
		scanf("%d",&num);
		q.resize(num);
		flag=true;
		fill(cnt.begin(),cnt.end(),0);
		for(int i=0;i<num;i++){
			scanf("%d",&q[i]);
			cnt[q[i]]++;
		}
		if(q[0]!=q[num-1]){
			//没有形成环
//			printf("#1:"); 
			flag=false;
		}else{
			for(int i=1;i<=N;i++){
				if(i==q[0]&&i==q[num-1]&&cnt[i]==2){
					continue;
				}else if(i!=q[0]&&cnt[i]==1){
					continue;
				}else{
					flag=false;
//					printf("#2:(%d)",i);
					break;
				}
			}
		}
		if(flag){
			for(int i=1;i<num;i++){
				if(!graph[q[i-1]][q[i]]){
//					printf("#3:");//没有链接的路径 
					flag=false;
					break;
				}
			}
		}
		if(!flag){
			printf("NO");
		}else{
			printf("YES");
		}
		if(K){
			printf("\n");
		}
	}
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2.4 1123 Is It a Complete AVL Tree

主要是AVL要么不考，要么考起来万一不会就是die得妥妥地

#include
using namespace std;
struct Node{
	int val;
	int height=1;
	int level=0;
	Node*left=NULL;
	Node*right=NULL;
};
int N;
vector<int>v;
/*基础部件*/ 
//1. 创建新结点
Node* newNode(int val){
	Node*root=new Node;
	root->val=val;
	return root;
} 
//2.得到高度信息
int getHeight(Node*root){
	if(root==NULL){
		return 0;
	}else{
		return root->height;
	}
} 
//3.更新高度信息
void UpdateHeight(Node*root){
	root->height=max(getHeight(root->left),getHeight(root->right))+1;
}
//4. 计算平衡因子
int getBalanceFactor(Node*root){
	return getHeight(root->left)-getHeight(root->right);
}
//5.1 左旋
void L(Node* &root){
	Node*temp=root->right;
	root->right=temp->left;
	temp->left=root;
	UpdateHeight(root);
	UpdateHeight(temp);
	root=temp;
} 
//5.2 右旋 
void R(Node* &root){
	Node*temp=root->left;
	root->left=temp->right;
	temp->right=root;
	UpdateHeight(root);
	UpdateHeight(temp);
	root=temp;
}
//5. 插入构建AVL树 
void Insert(Node* &root,int val){
	if(root==NULL){
		root=newNode(val);
	}else{
		if(val<root->val){
			Insert(root->left,val);
			UpdateHeight(root);
			if(getBalanceFactor(root)==2){
				if(getBalanceFactor(root->left)==1){
					//LL型 
					R(root); 
				}else if(getBalanceFactor(root->left)==-1){
					//LR型 
					L(root->left);
					R(root);
				}
			}
		}else{
			Insert(root->right,val);
			UpdateHeight(root);
			if(getBalanceFactor(root)==-2){
				if(getBalanceFactor(root->right)==-1){
					//RR型 
					L(root); 
				}else if(getBalanceFactor(root->right)==1){
					//RL型 
					R(root->right);
					L(root);
				}
			}
		}
	}
}
//层次遍历
vector<vector<Node*>>level;
int max_level=0;
void LevelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	bool flag=false;
	while(!q.empty()){
		Node*top=q.front();
		q.pop();
		level[top->level].push_back(top);
		if(top->level>max_level){
			max_level=top->level;
		}
		if(!flag){
			flag=true;
		}else{
			printf(" ");
		}
		printf("%d",top->val);
		if(top->left!=NULL){
			top->left->level=top->level+1; 
			q.push(top->left);
		}
		if(top->right!=NULL){
			top->right->level=top->level+1; 
			q.push(top->right);
		}
	}
} 
//判断是否是：完全二叉树 
bool isCBT(Node*root){
	if(root==NULL){
		return true;
	}
	queue<Node*>q;
	q.push(root);
	Node*front=NULL;
	while(front=q.front()){
		q.push(front->left);
		q.push(front->right);
		q.pop();
	}
	while(!q.empty()){
		if(q.front()!=NULL){
			return false;
		}
		q.pop();
	}
	return true;
}
int main(){
	scanf("%d",&N);
	Node*root=NULL;
	v.resize(N);
	level.resize(N+1);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	for(int i=0;i<N;i++){
		Insert(root,v[i]);
	}
	LevelTravel(root);
	printf("\n");
	//判断是否是完全树:最后一层是放叶子，其他层都是满的 
	if(isCBT(root)){
		printf("YES");
	}else{
		printf("NO");
	}
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

3. 参考资料

C++判断一棵树是否为完全二叉树(CBT)_alxe_made的博客-CSDN博客