1112-1115

📅time:8.19 -

🍔题目：

1112 Stucked Keyboard string
1113 Integer Set Partition sort
1114 Family Property 并查集
1115 Counting Nodes in a Binary Search Tree 二叉搜索树

二叉树

插入

void insert(int a, node* &root) {//一定要注意引用
	if (root == NULL) {
		root = new node();
		root->data = a;
		return;
	}
	if (a <= root->data) {
		insert(a, root->left);
	}
	else {
		insert(a, root->right);
	}
}
//……
int main(){
    node* root=NULL;
    dfs(root);
}

node* insert(int a, node* root) {
	if (root == NULL) {
		root = new node();
		root->data = a;
	}
	else if (a <= root->data) {
		root->left = insert(a, root->left);
	}
	else {
		root->right = insert(a, root->right);
	}
	return root;//注意是在最后return不是在第一个if里return
}
//……
int main(){
    node* root=NULL;
    root = insert(a, root);
}

map

对于map中不存在的键，会返回0。cout<<P[‘a’];//0

设置索引时，注意不要被不存在的键干扰了。

附录

1112 Stucked Keyboard 16分

字符串模拟，题目理解错误，以为>=k个连续就是坏键（实则要两次以上>=k)

理解正确后就不会了。

更新：原来第二次理解也是错的，是要每次都重复k次，只要有一次没重复k次，就是好键

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
int k;
string s;
map<char,int> index;
bool good[1001];
int main() {
	cin >> k >> s;
	char pre = '+';
	int cnt = 0;//置1会出错，因为会认为'+'是好键，执行good[index[pre]] = true;，但是index中没有'+',会使得good[0]=true，而下标0，正是s的第一个字母的映射。
	int num = 0;
	s = s + '%';//在最后加个字符
	fill(good, good + 1001, false);
	//cout << good[index['a']];
	for (int i = 0; i < s.size();i++) {
		if (index.count(s[i]) == 0) {
			index[s[i]] = num++;
		}
		//cout << s[i] << " " << pre << endl;
		if (s[i] != pre) {
			if (cnt % k!=0) {
				good[index[pre]] = true; //cout << pre<<endl;
			}
			pre = s[i];
			cnt = 1;
		}
		else {
			cnt++;
		}
	}
	s = s.substr(0,s.size()-1);//除去加的字符
	set<char>printed;
	for (int i = 0; i < s.size(); i++) {
		if (!good[index[s[i]]] &&printed.find(s[i])==printed.end()) {
			cout << s[i];
			printed.insert(s[i]);
		}
	}
	cout << endl;
   // cout<<good[index['1']];
	for (int i = 0; i < s.size(); i++) {
		if (good[index[s[i]]]) cout << s[i];
		else { 
			cout << s[i];
			i = i + k-1;
		}
	}
}

1113 Integer Set Partition 25分

sort()很简单的题目

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int num[100010];
int main() {
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> num[i];
	}
	sort(num, num + N);
	int pos = N / 2;
	int ans = 0;
	for (int i = 0; i < pos; i++) {
		ans += num[i];
	}
	int b = 0;
	for (int i = pos; i < N; i++) {
		b += num[i];
	}
	cout << N % 2 << " " << b - ans;
}

1114 Family Property 23分

并查集

测试点1答案错误,🐔帮我看一下

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int Fa[10010];
int property[10010];
int area[10010];
int flag[10010];
int peoplenum[10010];
struct node {
	int id;
	int M;
	double avgset;
	double avgarea;
};
int findfather(int a) {
	int t = a;
	while (Fa[t] != t) {
		t = Fa[t];
	}
	//t是目前的根结点
	int temp = Fa[a];
	while (temp != t) {
		Fa[a] = t;
		a = temp;
		temp = Fa[temp];
	}
	return t;
}
int Union(int a, int b) {
	int fa = findfather(a);
	int fb = findfather(b);
	int f = fa;
	if (fa != fb) {
		if (fa < fb) {
			Fa[b] = fa;
			flag[fb] = false;
			//flag[fa] = true;
			f = fa;
		}
		else {
			Fa[a] = fb;
			flag[fa] = false;
			//flag[fa] = true;
			f = fb;
		}
		property[f] = property[fa] + property[fb];
		area[f] = area[fa] + area[fb];
		peoplenum[f] = peoplenum[fa] + peoplenum[fb];
	}
	return f;
}
bool cmp(node* a, node* b) {
	if (a->avgarea != b->avgarea)
		return a->avgarea > b->avgarea;
	return a->id < b->id;
}
int main() {
	cin >> N;
	fill(peoplenum, peoplenum + 10010, 1);
	for (int i = 0; i < 10000; i++) {
		Fa[i] = i;
	}
	int ID, father, mother, k, child, M, Area;
	for (int i = 0; i < N; i++) {
		cin >> ID >> father >> mother >> k;
		int f = Fa[ID];
		if(father!=-1)
			f = Union(ID, father);
		//cout << "Fid" << Fa[ID] << " Father " << Fa[father] << endl;
		//cout << "fa" << f;
		if(mother!=-1)
			f = Union(ID, mother);
		//cout<<"fa"<<f;
		for (int j = 0; j < k; j++) {
			cin >> child;
			f = Union(ID, child);
		}
		cin >> M >> Area;
		flag[f] = true;
		property[f] += M;
		area[f] += Area;

	}
	int n = 0;
	vector<node*>F;
	for (int i = 0; i < 10010; i++) {
		if (flag[i]) {
			n++;
			node* p = new node();
			p->id = i;
			p->M = peoplenum[i];
			p->avgarea = 1.0 * area[i] / peoplenum[i];
			p->avgset = 1.0*property[i] / peoplenum[i];
			F.push_back(p);
		}
	}
	cout << n << endl;
	sort(F.begin(), F.end(), cmp);
	for (int i = 0; i < F.size(); i++) {
		printf("%04d %d %.3f %.3f\n", F[i]->id, F[i]->M, F[i]->avgset, F[i]->avgarea);
	}
}

1115 Counting Nodes in a Binary Search Tree 28分

二叉搜索树。

利用数组进行储存，一个测试点会段错误，应该用动态储存。N<=1000的搜索树最坏会需要2^1000的长度

要注意插入函数的写法（加引用）

#include<iostream>
#include<math.h>
using namespace std;
int N;
struct node {
	int data, depth;
	node* right = NULL, * left = NULL;
};
int maxi = 0;
void insert(int a, node* &root, int depth) {
	if (root == NULL) {
		root = new node();
		root->data = a;
		root->depth = depth;
		if (depth > maxi) maxi = depth;
		return;
	}
	if (a <= root->data) {
		insert(a, root->left, depth + 1);
	}
	else {
		insert(a, root->right, depth + 1);
	}
}
int n = 0, m = 0;
void dfs(node* r) {
	if (r == NULL)return;
	if (r->depth == maxi) n++;
	if (r->depth == maxi - 1) m++;
	dfs(r->left);
	dfs(r->right);
}
int main() {
	cin >> N;
	node* root=NULL;
	int a;
	for (int i = 1; i <= N; i++) {
		cin >> a;
		insert(a, root, 0);
	}
	dfs(root);
	cout << n << " + " << m << " = " << m + n;
}