【数据结构1

数据结构1"/>

【数据结构1

P1551 亲戚

题目链接：P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
using namespace std;
int fa[5005], Rank[5005];int find(int x) {if (x == fa[x]) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int i, int j) {int x = find(i), y = find(j);if (Rank[x] <= Rank[y]) {fa[x] = y;} else {fa[y] = x;}if (Rank[x] == Rank[y] && x != y) {Rank[y]++;}
}int main() {int n, m, p, x, y;cin >> n >> m >> p;for (int i = 1; i <= n; i++) {fa[i] = i;Rank[i] = 1;}for (int i = 0; i < m; i++) {cin >> x >> y;merge(x, y);}for (int i = 0; i < p; i++) {cin >> x >> y;if (find(x) == find(y)) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}

参考博客：算法学习笔记(1) : 并查集 - 知乎 (zhihu) 

error: reference to 'rank' is ambiguous_荷叶田田-CSDN博客

P1536 村村通

题目链接：P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
using namespace std;
int fa[1010], n, m;int find(int x) {if (x == fa[x]) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int i, int j) {int x = find(i);int y = find(j);fa[x] = y;
}int main() {while (true) {cin >> n;if (n == 0) {return 0;}cin >> m;for (int i = 1; i <= n; i++) {fa[i] = i;}int x, y;for (int i = 0; i < m; i++) {cin >> x >> y;merge(x, y);}int ans = 0;for (int i = 1; i <= n; i++) {if (i == find(i)) {ans++;}}ans--;cout << ans << endl;}
}

P3370 【模板】字符串哈希

题目链接：P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
long long f[100010];unsigned long long Hash(string s) {unsigned long long cnt = 0;for (int i = 0; i < s.size(); i++) {cnt = 233 * cnt + (unsigned long long)s[i];}return cnt;
}int main() {int n, ans = 1;cin >> n;string s;for (int i = 0; i < n; i++) {cin >> s;f[i] = Hash(s);}sort(f, f + n);for (int i = 1; i < n; i++) {if (f[i] != f[i - 1]) {ans++;}}cout << ans;return 0;
}

P3405 [USACO16DEC]Cities and States S

题目链接：P3405 [USACO16DEC]Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <map>
#include <string>
using namespace std;
map<int, int>m[100010];int main() {int n, ans = 0;cin >> n;string a, b;for (int i = 0; i < n; i++) {cin >> a >> b;int x = a[0] * 26 + a[1];int y = b[0] * 26 + b[1];if (x != y) {ans += m[y][x];m[x][y]++;}}cout << ans;return 0;
}

P5250 【深基17.例5】木材仓库

题目链接：P5250 【深基17.例5】木材仓库 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <set>
#include <cmath>
using namespace std;int main() {int t, c, len;cin >> t;set<int>s;s.insert(2147483647);s.insert(-2147483647);while (t--) {cin >> c >> len;if (c == 1) {if (!s.insert(len).second) {cout << "Already Exist" << endl;}} else {if (s.size() == 2) {cout << "Empty" << endl;continue;}set<int>::iterator it = s.lower_bound(len); //it指向不小于目标值的第一个元素if (*it == len) {s.erase(len);cout << len << endl;} else {set<int>::iterator it1;it1 = it;it1--;//it1指向小于目标值的第一个元素if (abs(*it - len) >= abs(*it1 - len) && *it1 != -2147483647) {cout << *it1 << endl;s.erase(it1);} else {cout << *it << endl;s.erase(it);}}}}return 0;
}

P5266 【深基17.例6】学籍管理

题目链接：P5266 【深基17.例6】学籍管理 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string, int>m;int main() {int t, c;cin >> t;while (t--) {cin >> c;if (c == 1) {string name;int score;cin >> name >> score;m[name] = score;cout << "OK" << endl;} else if (c == 2) {string s;cin >> s;map<string, int>::iterator it = m.find(s);if (it == m.end()) {cout << "Not found" << endl;} else {cout << m[s] << endl;}} else if (c == 3) {string s;cin >> s;map<string, int>::iterator it = m.find(s);if (it == m.end()) {cout << "Not found" << endl;} else {m.erase(it);cout << "Deleted successfully" << endl;}} else {cout << m.size() << endl;}}return 0;
}

P1918 保龄球

题目链接：P1918 保龄球 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <map>
using namespace std;
map<int, int>m;int main() {int n, t, x;cin >> n;for (int i = 1; i <= n; i++) {cin >> x;m[x] = i;}cin >> t;while (t--) {cin >> x;cout << m[x] << endl;}return 0;
}

P1525 [NOIP2010 提高组] 关押罪犯

题目链接：P1525 [NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <algorithm>
using namespace std;struct Person {int x;int y;int z;
} f[100010];
int fa[20005], b[20005];bool Com(Person p1, Person p2) {return p1.z > p2.z;
}int find(int x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int x, int y) {int xx = find(x);int yy = find(y);fa[xx] = yy;
}bool check(int x, int y) {if (find(x) == find(y)) {return true;} else {return false;}
}int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {fa[i] = i;}for (int i = 1; i <= m; i++) {cin >> f[i].x >> f[i].y >> f[i].z;}sort(f + 1, f + m + 1, Com);for (int i = 1; i <= m; i++) {if (check(f[i].x, f[i].y)) {cout << f[i].z;return 0;} else {if (!b[f[i].x]) {b[f[i].x] = f[i].y;} else {merge(b[f[i].x], f[i].y);}if (!b[f[i].y]) {b[f[i].y] = f[i].x;} else {merge(b[f[i].y], f[i].x);}}}cout << 0;return 0;
}

P1621 集合

题目链接：P1621 集合 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int fa[100010], c[100010];
bool IsPrime[100010];int find(int x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int x, int y) {int xx = find(x);int yy = find(y);fa[xx] = yy;
}int main() {int a, b, p, cnt = 0, ans = 0;cin >> a >> b >> p;for (int i = a; i <= b; i++) {fa[i] = i;}memset(IsPrime, 1, sizeof(IsPrime));IsPrime[0] = IsPrime[1] = 0;for (int i = 2; i <= sqrt(b); i++) {if (IsPrime[i]) {for (int j = 2 * i; j < 100010; j += i) {IsPrime[j] = 0;}}}for (int i = p; i <= b; i++) {if (IsPrime[i]) {c[++cnt] = i;}}for (int i = 1; i <= cnt; i++) {int d = 0;while (d * c[i] < a) {d++;}while (c[i] * (d + 1) <= b) {merge(c[i]*d, c[i] * (d + 1));d++;}}for (int i = a; i <= b; i++) {if (fa[i] == i) {ans++;}}cout << ans;return 0;
}

P1892 [BOI2003]团伙

题目链接：P1892 [BOI2003]团伙 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
using namespace std;
int fa[1005], b[1005];int find(int x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int x, int y) {int xx = find(x);int yy = find(y);fa[xx] = yy;
}int main() {int n, m, x, y, ans = 0;char c;cin >> n >> m;for (int i = 1; i <= n; i++) {fa[i] = i;}while (m--) {cin >> c >> x >> y;if (c == 'E') {if (!b[x]) {b[x] = y;} else {merge(b[x], y);}if (!b[y]) {b[y] = x;} else {merge(b[y], x);}} else if (c == 'F') {merge(x, y);}}for (int i = 1; i <= n; i++) {if (fa[i] == i) {ans++;}}cout << ans;return 0;
}

P1955 [NOI2015] 程序自动分析

题目链接：P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int fa[1000010], L[1000010];struct node {int x;int y;int e;
} a[1000010];int find(int x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}void merge(int x, int y) {int xx = find(x);int yy = find(y);fa[xx] = yy;
}bool Com(node n1, node n2) {return n1.e > n2.e;
}int main() {int t, n;cin >> t;while (t--) {cin >> n;vector<int>v;bool flag = 0;for (int i = 1; i <= n * 2; i++) {fa[i] = i;}for (int i = 1; i <= n; i++) {cin >> a[i].x >> a[i].y >> a[i].e;v.push_back(a[i].x);v.push_back(a[i].y);}sort(a + 1, a + n + 1, Com);sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());for (int i = 1; i <= n; i++) {a[i].x = lower_bound(v.begin(), v.end(), a[i].x) - v.begin() + 1;a[i].y = lower_bound(v.begin(), v.end(), a[i].y) - v.begin() + 1;if (a[i].e == 1) {merge(a[i].x, a[i].y);} else {if (find(a[i].x) == find(a[i].y)) {cout << "NO" << endl;flag = 1;break;}}}if (flag == 0) {cout << "YES" << endl;}}return 0;
}

参考博客：算法学习笔记(19): 离散化 - 知乎 (zhihu)

C++STL中的unique函数解析 - Excaliburer - 博客园 (cnblogs)

P4305 [JLOI2011]不重复数字

题目链接：P4305 [JLOI2011]不重复数字 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <cstring>
#include <cmath>
#define P 100007
using namespace std;
long long a[100000];int Hash(int x) {int y = abs(x);while (a[y % P] != 0 && a[y % P] != x) {y++;}return y % P;
}int main() {int t, n, x;cin >> t;while (t--) {cin >> n;bool flag = 0;memset(a, 0, sizeof(a));for (int i = 0; i < n; i++) {scanf("%d", &x);if (x == 0) { //特判0if (flag == 0) {flag = 1;printf("%d ", x);}continue;}int t = Hash(x);if (a[t] != x) {a[t] = x;printf("%d ", x);}}cout << endl;}return 0;
}

P3879 [TJOI2010]阅读理解

题目链接：P3879 [TJOI2010]阅读理解 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int n, m, tree[500010][26], cnt, num;
bitset<1010> f[500010];
string str;void insert(string s, int x) {int now = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (!tree[now][p]) {tree[now][p] = ++cnt;}now = tree[now][p];}f[now][x] = 1;
}void check(string s) {int now = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (!tree[now][p]) {cout << endl;return;}now = tree[now][p];}for (int i = 1; i <= n; i++) {if (f[now][i]) {cout << i << ' ';}}cout << endl;
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> num;for (int j = 0; j < num; j++) {cin >> str;insert(str, i);}}cin >> m;for (int i = 0; i < m; i++) {cin >> str;check(str);}return 0;
}

P2814 家谱

题目链接：P2814 家谱 - 洛谷 | 计算机科学教育新生态 (luogu)

#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string, string>fa;string find(string x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}
}int main() {string s, s1;while (cin >> s) {if (s[0] == '$') {break;} else if (s[0] == '#') {s.erase(0, 1);s1 = s;if (fa[s] == "") {fa[s] = s;}} else if (s[0] == '+') {s.erase(0, 1);fa[s] = s1;} else if (s[0] == '?') {s.erase(0, 1);cout << s << ' ' << find(s) << endl;}}return 0;
}