😉14 : 20 — 16 : 58 第一次两个半小时100/100。
第三题真的挺难受的。难受的感觉现在都没完全消失。。。。。。（噗嗤 看了大佬的题解 发现是我写麻烦了的锅
20 25 25 30
1112 Stucked Keyboard (20 分)
- 若某字符连续出现的次数x中，存在x%repeat_times不为0的，则可判定该字符按键无故障。
- 某字符状态设为无故障之后，状态就保持无故障。（不能再设为有故障）
- 最后一个字符的处理⚠️
- 按检测到故障的顺序输出
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
using namespace std;
int char2index(char ch) {
if (isdigit(ch)) return ch - '0';
if (islower(ch)) return ch - 'a' + 10;
return 36; // _
}
int main() {
int hash[37] = {0}; // 0-9 0-9 a-z 10-35 _ 36
// 0 not exist 1 not stucked -1 stucked
string str0;
int ktimes;
cin >> ktimes >> str0;
int size = str0.size();
vector<char> qaq;
char curr = str0[0];
int cnt = 1;
for (int i = 1; i < size; ++i) {
if (str0[i] != curr) {
int index = char2index(curr);
if (cnt % ktimes) {
hash[index] = 1;
} else if (hash[index] != 1 && hash[index] != -1) {
hash[index] = -1;
qaq.emplace_back(curr);
}
curr = str0[i];
cnt = 1;
} else {
cnt++;
}
}
int last_index = char2index(curr);
if (cnt % ktimes) {
hash[last_index] = 1;
} else if (hash[last_index] != 1 && hash[last_index] != -1) {
hash[last_index] = -1;
qaq.emplace_back(curr);
}
for (auto item : qaq) {
if (hash[char2index(item)] == -1) {
printf("%c", item);
}
}
printf("\n");
for (int i = 0; i < size;) {
printf("%c", str0[i]);
if (hash[char2index(str0[i])] == -1) {
i += ktimes;
} else i++;
}
return 0;
}
1113 Integer Set Partition (25 分)
- 水题，n为偶数、奇数分开写。奇数时注意。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int nn, nums[100010], sum = 0;
int main() {
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) {
scanf("%d", &nums[i]);
sum += nums[i];
}
sort(nums, nums + nn);
int temp = 0;
for (int i = 0; i < nn / 2; i++) {
temp += nums[i];
}
if (nn % 2) {
int mid = nums[nn / 2];
printf("1 %d\n", max(abs(sum - temp - temp), abs(sum - 2 * temp - 2 * mid)));
} else {
printf("0 %d\n", abs(sum - temp - temp));
}
return 0;
}
1114 Family Property (25 分)
并查集，加了不少花样。
首先是若不将id和index作映射，在_union操作结束后，可能需要一个bool valid[i]来区分下标（id）为i的人是否出现过。。。。。。emmmm我写的有点麻烦了，实际上并不要求维护每个family的成员列表。
还是学习一下liuchuo大佬的思路吧。只要在_union(a,b)时，确保_find(a)、_find(b)中较大的组合并到较小的组，就能省很多事了。。。。。。
- 来自 —日沉云起@csdn
liuchuo大佬的题解
用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～- 喵喵喵？？？输入的时候我在sstream什么呢。。。明明直接读数字就好啊。。。。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <vector>
using namespace std;
struct Rec {
int m_estate = 0, area = 0;
} people[10001]; // index = id
struct Kazoku {
int min_id;
unsigned long n_member;
int total_estate;
double average_area;
bool operator<(const Kazoku &k2) const {
if (average_area != k2.average_area)
return average_area > k2.average_area;
return min_id < k2.min_id;
}
};
map<int, int> id_index;
map<int, int> index_id;
int uf[10001], cntNO = 0;
int _find(int a) {
return uf[a] < 0 ? a : uf[a] = _find(uf[a]);
}
int get_index(int id) {
if (id == -1) return -1;
if (id_index.find(id) == id_index.end()) {
id_index[id] = cntNO;
index_id[cntNO] = id;
cntNO++;
}
return id_index[id];
}
void _union(int a, int b) {
if (b == -1) return;
a = _find(a);
b = _find(b);
if (a != b) {
uf[a] += uf[b];
uf[b] = a;
}
}
map<int, set<int>> lead_members;
map<int, pair<int, int>> lead_id_total;
int main() {
fill(uf, uf + 10001, -1);
stringstream ss;
int nn;
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) {
int id, fid, mid, cid, m_estate, area;
string father, mother;
cin >> id >> father >> mother;
int index = get_index(id);
ss.clear();
ss << father;
ss >> fid;
fid = get_index(fid);
_union(index, fid);
ss.clear();
ss << mother;
ss >> mid;
mid = get_index(mid);
_union(index, mid);
int nchild;
scanf("%d", &nchild);
for (int j = 0; j < nchild; ++j) {
scanf("%d", &cid);
cid = get_index(cid);
_union(index, cid);
}
scanf("%d%d", &m_estate, &area);
people[id].m_estate = m_estate, people[id].area = area;
}
for (int i = 0; i < cntNO; ++i) {
_find(i);
}
for (int i = 0; i < cntNO; ++i) {
int lead_id = index_id[_find(i)], me_id = index_id[i];
lead_members[lead_id].insert(me_id);
lead_id_total[lead_id].first += people[me_id].m_estate;
lead_id_total[lead_id].second += people[me_id].area;
}
set<Kazoku> res;
for (auto &item:lead_members) {
int lead_id = item.first;
res.insert(Kazoku{*(item.second.begin()), item.second.size(),
lead_id_total[lead_id].first,
lead_id_total[lead_id].second * 1.0 / item.second.size()});
}
printf("%lu\n", res.size());
for (auto item : res) {
printf("%04d %lu %.3lf %.3lf\n", item.min_id, item.n_member,
item.total_estate * 1.0 / item.n_member, item.average_area);
}
return 0;
}
1115 Counting Nodes in a BST (30 分)
插入结点，采用递归写法。insert函数传参数要传Node *&！！！
建树（插入结点）时，顺便得到插入点所在深度、计数各层结点数，给insertNode加一个depth参数就好。
#include <cstdio>
#include <algorithm>
using namespace std;
int data, nn, depth_cnt[1010] = {0}, max_depth = -1;
struct Node {
int key;
Node *lchild = NULL, *rchild = NULL;
};
void insertNode(Node *&root, int x, int depth) {
if (root == NULL) {
root = new Node;
root->key = x;
depth_cnt[depth]++;
max_depth = max(max_depth, depth);
return;
}
if (x <= root->key) insertNode(root->lchild, x, depth + 1);
else insertNode(root->rchild, x, depth + 1);
}
int main() {
Node *root = NULL;
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) {
scanf("%d", &data);
insertNode(root, data, 0);
}
printf("%d + %d = %d\n", depth_cnt[max_depth], depth_cnt[max_depth - 1],
depth_cnt[max_depth] + depth_cnt[max_depth - 1]);
return 0;
}
