1132-1135

📅time:8.25

🍔题目：

1132 Cut Integer
1133 Splitting A Linked List
1134 Vertex Cover
1135 Is It A Red-Black Tree

even number ：偶数

odd number：奇数

descendant leaves ：后代叶

附录

1132 Cut Integer 20分

浮点错误时，要思考是不是0做除数了

#include<iostream>
#include<string>
using namespace std;
int N;
string Z;
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Z;
		int digits = Z.size();
		int a = stoi(Z.substr(0, digits / 2));
		int b = stoi(Z.substr(digits / 2, digits / 2));
		if (a == 0 || b == 0) {
			cout << "No\n";
			continue;
		}
		//cout << a << " " << b;
		if (stoi(Z) % (a * b) == 0) {
			cout << "Yes\n";
		}
		else cout << "No\n";
	}
}

1133 Splitting A Linked List 25分

#include<iostream>
#include<vector>
using namespace std;
int start, N, K;
struct node {
	int data;
	int next;
}chain[100010];
vector<int>negative;
vector<int>small;
vector<int>big;
int main() {
	cin >> start >> N >> K;
	int address, d, next;
	for (int i = 0; i < N; i++) {
		cin >> address >> d >> next;
		chain[address].data = d;
		chain[address].next = next;
	}
	int temp = start;
	while (temp != -1) {
		if (chain[temp].data < 0) {
			negative.push_back(temp);
		}
		else if (chain[temp].data <= K) {
			small.push_back(temp);
		}
		else if (chain[temp].data > K) {
			big.push_back(temp);
		}
		temp = chain[temp].next;
	}
	for (int i = 0; i < small.size(); i++) {
		negative.push_back(small[i]);
	}
	for (int i = 0; i < big.size(); i++) {
		negative.push_back(big[i]);
	}
	for (int i = 0; i < negative.size(); i++) {
		if (i == negative.size() - 1) printf("%05d %d %d\n", negative[i], chain[negative[i]].data, -1);
		else printf("%05d %d %05d\n", negative[i], chain[negative[i]].data, negative[i + 1]);
	}
}

1134 Vertex Cover 25分

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int N, M;
vector<int> G[10010];
int main() {
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int K;
	cin >> K;
	for (int i = 0; i < K; i++) {
		int n, temp;
		cin >> n;
		set<int>dot;
		for (int j = 0; j < n; j++) {
			cin >> temp;
			dot.insert(temp);
		}
		bool flag = true;
		for (int j = 0; j < N; j++) {
			if (dot.count(j) == 0 && G[j].size() != 0) {
				for (int k = 0; k < G[j].size(); k++) {
					if (dot.count(G[j][k]) == 0) {
						flag = false;
						cout << "No\n";
						break;
					}
				}
				if(!flag)	break;
			}

		}
		if (flag) cout << "Yes\n";
	}
}

1135 Is It A Red-Black Tree 30分

感觉自己写得very good

#include<iostream>
#include<vector>
using namespace std;
int N;
struct node {
	int data;
	node* left = NULL, * right = NULL;
	node(int data) :data(data) {}
};
void insert(node*& root,int data) {
	if (root == NULL) {
		root = new node(data);
		return;
	}
	if (abs(data) < abs(root->data)) {
		insert(root->left, data);

	}
	else {
		insert(root->right, data);
	}
}
int blacknum = 0;
bool ans = true;
int dfs(node* root) {
	if (!ans) {//已经判定不是红黑树了不继续往后判断
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {//左右都为空
		if (root->data > 0) return 1;//1个黑结点
		else return 0;
	}
	int lnum=0, rnum=0;
	if (root->left != NULL) {
		if (root->data < 0 && root->left->data < 0) {//不满足红结点的孩子是黑节点
			ans = false;
			return 0;
		}
		lnum = dfs(root->left);//左子树黑节点个数
	}
	if (root->right != NULL) {
		if (root->data < 0 && root->right->data < 0) {//不满足红结点的孩子是黑节点
			ans = false;
			return 0;
		}
		rnum = dfs(root->right);//右子树黑节点个数
	}
	if (lnum != rnum) {//不相等则不是红黑树
		ans = false;
		return 0;
	}
	else {//返回该树的黑节点数量
		if (root->data > 0)
			return lnum + 1;
		else return lnum;
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int temp, node_num;
		cin >> node_num;
		node* root = NULL;
		ans = true;
		for (int j = 0; j < node_num; j++) {
			cin >> temp;
			insert(root,temp);
		}
		if (root->data < 0) {
			cout << "No\n";
			continue;
		}
		dfs(root);
		if (ans)cout << "Yes\n";
		else cout << "No\n";
	}
}