P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态
自然溢出手写哈希模板代码。
#include<bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
using PII = std::pair<double, double>;const int N = 1e4 + 10, P = 131;int h[N], p[N];ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}void solve() {int n;std::map<ull, int> mp;std::cin >> n;ll ans = 0;while (n--) {std::string s;std::cin >> s;s = ' ' + s;h[0] = 0, p[0] = 1;for (int i = 1; i < s.length(); i++) {p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + s[i];}ull hash = get(1, (int) s.length() - 1);if (!mp[hash]) ans++, mp[hash]++;
// std::cout << ans << '\n';}std::cout << ans << '\n';
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int t = 1;
// std::cin >> t;while (t--) {solve();}return 0;
}STL。
#include<bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
using PII = std::pair<double, double>;const int N = 1e4 + 10, P = 131;void solve() {int n;std::unordered_map<std::string, int> mp;std::cin >> n;ll ans = 0;while (n--) {std::string s;std::cin >> s;if (!mp[s]) ans++, mp[s]++;}std::cout << ans << '\n';
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int t = 1;
// std::cin >> t;while (t--) {solve();}return 0;
}P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态
#include<bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
using PII = std::pair<double, double>;const int N = 1e4 + 10, P = 131;void solve() {std::map<int, ll> mp;ll ans = 0;int n, c;std::cin >> n >> c;while (n--) {int x;std::cin >> x;mp[x]++;}
// std::cout << mp.size() << "xxxxxxx\n";for (auto &[i, j]: mp) {if (mp.count(c + i)) {ans += mp[c + i] * j;}
// std::cout << c + i << " " << j << '\n';}std::cout << ans << '\n';
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int t = 1;
// std::cin >> t;while (t--) {solve();}return 0;
}P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态
一眼并查集，唯一要注意的是数据范围很大，需要离散化。
#include<bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
using PII = std::pair<ll, ll>;
using ari = std::array<int, 3>;const int N = 2e5 + 10, P = 131;
int p[N], k;int find(int a) {if (p[a] != a) p[a] = find(p[a]);return p[a];
}void merge(int a, int b) {int pa = find(a), pb = find(b);if (pa != pb) {p[pa] = pb;}
}void solve() {int n;std::cin >> n;std::vector<ari> v;std::map<ll, int> mp;//键值为输入的i，j，值为重新赋值的编号k = 0;for (int i = 1; i <= n; i++) {int c, d, q;std::cin >> c >> d >> q;if (!mp[c]) mp[c] = ++k;if (!mp[d]) mp[d] = ++k;v.push_back({mp[c], mp[d], q});}for (auto [i, j]: mp) {p[j] = j;}for (auto arr: v) {if (arr[2] == 0) continue;merge(arr[0], arr[1]);}for (auto arr: v) {if (arr[2] == 1) continue;int p1 = find(arr[0]), p2 = find(arr[1]);if (p1 == p2) {std::cout << "NO\n";return;}}std::cout << "YES\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}P1379 八数码难题 - 洛谷 | 计算机科学教育新生态
BFS，只需要map存一下每次的状态。
#include<bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
using PII = std::pair<ll, ll>;
using ari = std::array<int, 3>;const int N = 2e5 + 10, P = 131;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};void solve() {std::string n;std::cin >> n;std::queue<std::string> q;q.push(n);std::map<std::string, int> mp;mp[n] = 0;while (q.size()) {auto t = q.front();q.pop();if (t == "123804765") break;int g[3][3], x, y;for (int i = 0; i < t.length(); i++) {g[i / 3][i % 3] = t[i] - '0';if (t[i] == '0') x = i / 3, y = i % 3;}for (int i = 0; i < 4; i++) {int a = dx[i] + x, b = dy[i] + y;if (a < 0 || b < 0 || a > 2 || b > 2) continue;std::swap(g[a][b], g[x][y]);std::string ss;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {ss += g[i][j] + '0';}}if (mp.count(ss) == 0) {mp[ss] = mp[t] + 1;q.push(ss);}std::swap(g[a][b], g[x][y]);}}std::cout << mp["123804765"] << '\n';
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int t = 1;
// std::cin >> t;while (t--) {solve();}return 0;
}