记录一下常用模板。
快速幂运算
long long fastpow(int a, int b) {
long long ret = 1;
long long base = (long long)a;
while (b != 0) {
if (b & 1 != 0) {
ret *= base;
}
base *= base;
b >>= 1;
}
return ret;
}
并查集
#include <vector>
#include <iostream>
#include "unionset.h"
#define MAX_N 10000
int parent[MAX_N];
int rank[MAX_N];
void uninit(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int unfind(int x) {
while (x != parent[x]) x = parent[x];
return x;
}
void ununite(int x, int y) {
x = unfind(x);
y = unfind(y);
if (x == y) return;
if (rank[x] < rank[y]) {
parent[x] = y;
}
else {
parent[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}
bool unissame(int x, int y) {
return unfind(x) == unfind(y);
}
Trie结构
#include "header.h"
class TrieNode {
public:
string word;
TrieNode* child[26];
TrieNode() {
word = "";
for (int i = 0; i < 26; i++) child[i] = nullptr;
}
};
class Trie {
private:
TrieNode * root;
public:
Trie(vector<string> words) {
root = new TrieNode();
buildTrie(words);
}
void buildTrie(vector<string> words) {
for (auto s : words) {
TrieNode* tmpnode = root;
for (auto c : s) {
int idx = c - 'a';
if (!tmpnode->child[idx]) tmpnode->child[idx] = new TrieNode();
tmpnode = tmpnode->child[idx];
}
tmpnode->word = s;
}
}
bool hasprefix(string prefix) {
TrieNode* tmpnode = root;
for (auto c : prefix) {
if (!tmpnode->child[c - 'a']) return false;
tmpnode = tmpnode->child[c - 'a'];
}
return true;
}
bool hasword(string word) {
TrieNode* tmpnode = root;
for (auto c : word) {
if (!tmpnode->child[c - 'a']) return false;
tmpnode = tmpnode->child[c - 'a'];
}
return tmpnode->word != "";
}
};