浙江龙网

  1. 首页 > 生活百科 > >

持续更新 c++算法竞赛常用板子集合( 二 )

生活百科

缩点其中 \(p\) 为缩点后的新点 。
int dfn[N], low[N], dcnt;bool instack[N];stack <int> s;int p[N], h[N];void dfs(int x, int f) { instack[x] = 1; s.push(x); dfn[x] = low[x] = ++dcnt; for (int i = last[0][x]; i; i = e[0][i].next) {int v = e[0][i].to;if (dfn[v]) {if (instack[v]) low[x] = min(low[x], dfn[v]);continue;}dfs(v, x);low[x] = min(low[x], low[v]); } if (low[x] >= dfn[x]) {p[x] = x, h[x] = a[x], instack[x] = 0;while (s.top() != x) {p[s.top()] = x;h[x] += a[s.top()];instack[s.top()] = 0;s.pop();}s.pop(); }}欧拉路径int st[N], ed[N];struct edge { int u, v;} e[N << 1];int rd[N], cd[N];bool cmp(edge x, edge y) { if (x.u != y.u) return x.u < y.u; return x.v < y.v;}int ans[N << 1], cnt;void dfs(int x) { while (st[x] <= ed[x]) {st[x]++;dfs(e[st[x] - 1].v); } ans[++cnt] = x;}乘法逆元fac[0] = fac[1] = 1;for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;inv[1] = 1;for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;快速幂ll qpow(ll a, ll b) { ll res = 1; while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1; } return res;}矩阵快速幂不是我说这写的是真的丑，凑活着看吧QAQ
struct sq { ll x[110][110]; void build() {for (int i = 1; i <= n; i++) x[i][i] = 1; } void dd() {for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)x[i][j] = 0; }} a, ans;sq operator *(const sq &x, const sq &y) { sq res; res.dd(); for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)res.x[i][j] = (res.x[i][j] + x.x[i][k] * y.x[k][j] % mod) % mod; return res;}void qpow(ll x) { while (x) {if (x & 1) ans = ans * a;a = a * a;x >>= 1; }}线性基\(p\) 数组表示基底，\(x\) 为添加进的数字 。
int p[N];void add(ll x) { for (int i = N; i >= 0; i--) {if (!(x & (1ll << i))) continue;if (p[i]) x ^= p[i];else {p[i] = x; return ;} }}线性筛int prime[6000010], cnt;bool isprime[N + 10];void prim() { isprime[0] = isprime[1] = 1; for (int i = 2; i <= n; i++) {if (!isprime[i]) prime[++cnt] = i;for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {isprime[i * prime[j]] = 1;if (i % prime[j] == 0) break;} }}字符串哈希int Char(char c) { if (c >= '0' && c <= '9') return c - '0' + 1; //0~9: 1~10 if (c >= 'a' && c <= 'z') return c - 'a' + 11; //a~z: 11~37 if (c >= 'A' && c <= 'Z') return c - 'A' + 38; //A~Z: 38~65 return 0;}map <ll, int> mp;cin >> s;ll x = 0;for (int i = 0; i < s.size(); i++) x = (x * 100) + Char(s[i]);mp[x] = 1;KMP\(s\) 和 \(t\) 为需要匹配的两个 char 类型数组 。
\(border_i\) 表示 \(t\) 长度为 \(i\) 的前缀最长的 \(border\) 长度 。
完了border是啥来着？
ls = strlen(s + 1), lt = strlen(t + 1);int j = 0;for (int i = 2; i <= lt; i++) { while (j >= 1 && t[j + 1] != t[i]) j = border[j]; if (t[j + 1] == t[i]) j++; border[i] = j;}int sx = 1, tx = 0;while (sx <= ls) { while (tx >= 1 && s[sx] != t[tx + 1]) tx = border[tx]; if (t[tx + 1] == s[sx]) tx++; if (tx == lt) printf("%d\n", sx - lt + 1); sx++;}AC自动机struct Trie { int id[27], cnt, fail;} t[N];void Build(string &s) { int now = 0; for (int i = 0; i < s.size(); i++) {if (!t[now].id[s[i] - 'a']) t[now].id[s[i] - 'a'] = ++cnt;now = t[now].id[s[i] - 'a']; } t[now].cnt++;}void Fail() { queue <int> q; for (int i = 0; i < 26; i++) {int v = t[0].id[i];if (v != 0) {t[v].fail = 0;q.push(v);} } while (!q.empty()) {int u = q.front(); q.pop();for (int i = 0; i < 26; i++) {int v = t[u].id[i];if (v != 0) {t[v].fail = t[t[u].fail].id[i];q.push(v);}else t[u].id[i] = t[t[u].fail].id[i];} }}string s;int ans;void Query() { int now = 0; for (int i = 0; i < s.size(); i++) {now = t[now].id[s[i] - 'a'];for (int to = now; to; to = t[to].fail) {if (t[to].cnt == -1) break;ans += t[to].cnt;t[to].cnt = -1;} }}【持续更新 c++算法竞赛常用板子集合】

推荐阅读


上一篇：oracle expdp/exp ora-600/ora-39014报错处理

下一篇：JavaScript函数式编程之函子