## 1. 爪形行列式 1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&1& \cdots &1\\ 1&{{x_2}}& \cdots &0\\ \vdots & \vdots & \ddots &0\\ 1&0&0&{{x_n}} \end{array}} \right|$ ## 2. 两三角型行列式 1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&b& \cdots &b\\ b&{{x_2}}& \cdots &b\\ \vdots & \vdots & \ddots &b\\ b&b&b&{{x_n}} \end{array}} \right|$ 2. 求${D_n} = \left| {\begin{array}{*{20}{c}} {{x_1}}&b&b& \cdots &b\\ a&{{x_2}}&b& \cdots &b\\ a&a&{{x_3}}& \cdots &b\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&a&a& \cdots &{{x_n}} \end{array}} \right|$ 3. 求${D_n} = \left| {\begin{array}{*{20}{c}} d&b&b& \cdots &b\\ c&x&a& \cdots &a\\ c&a&x& \cdots &a\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c&a&a& \cdots &x \end{array}} \right|$ ## 3. 两条线型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1}}&{{b_1}}&0& \cdots &0\\ 0&{{a_2}}&{{b_2}}& \cdots &0\\ 0&0&{{a_3}}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{b_n}}&0&0& \cdots &{{a_n}} \end{array}} \right|$ ## 4. 范德蒙德型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n \end{array}} \right|$ ## 5. Hessenberg型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&2&3& \cdots &n\\ 1&{ - 1}&0& \cdots &0\\ 0&2&{ - 2}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{1 - n} \end{array}} \right|$ ## 6. 三对角型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} a&b&0& \cdots &0\\ c&a&b& \cdots &0\\ 0&c&a& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &a \end{array}} \right|$ ## 7. 各行元素和相等型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\ {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\ {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}} \end{array}} \right|$ ## 8. 相邻两行对应元素相差K倍型行列式 1. 求${D_n} = \left| {\begin{array}{*{20}{c}} 0&1&2& \cdots &{n - 1}\\ 1&0&1& \cdots &{n - 2}\\ 2&1&0& \cdots &{n - 3}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n - 1}&{n - 2}&1& \cdots &0 \end{array}} \right|$ 2. 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\ {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\ {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&{{a^2}}&{{a^3}}& \cdots &1 \end{array}} \right|$
Category: 解题报告
莫比乌斯反演与容斥原理
退役前一直想把莫比乌斯反演与容斥原理统一在一起,奈何自己水平不足,只能作罢。
这次把《组合数学》、《具体数学》、《初等数论》的相关内容读了一遍,总算是完成了这个遗愿:
mobius_and_inclusion_exclusion_principle
Download:http://oi.cyo.ng/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf
拓展阅读1:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
拓展阅读2:http://vfleaking.blog.uoj.ac/blog/87
A Companion to Symbols in Latex
list: http://mohu.org/info/symbols/symbols.htm
handwritten symbol recognition: http://detexify.kirelabs.org/classify.html
【Tricks】Hello World!
之前见过这货的低配版
也是全部define成_
,然后搞
但今天看到这货,用了define能组合的特点
真的是变态啊_(:з」∠)_
#define _________ } #define ________ putchar #define _______ main #define _(a) ________(a); #define ______ _______(){ #define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C) #define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F) #define ____ _(0x72)_(0x6C)_(0x64)_(0x21) #define _____ __ ___ ____ _________ #include<stdio.h> _____
【BZOJ 4817】[SDOI2017] 树点涂色
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817
解题报告
我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数
于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = N << 1; const int LOG = 20; int n, m, head[N], nxt[M], to[M]; int in[N], ot[N], dep[N], num[N], ff[N][LOG]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline int LCA(int u, int v) { if (dep[u] < dep[v]) { swap(u, v); } for (int j = LOG - 1; ~j; j--) { if (dep[ff[u][j]] >= dep[v]) { u = ff[u][j]; } } if (u == v) { return u; } for (int j = LOG - 1; ~j; j--) { if (ff[u][j] != ff[v][j]) { u = ff[u][j]; v = ff[v][j]; } } return ff[u][0]; } class SegmentTree{ int root, ch[M][2], tag[M], mx[M]; public: inline void init() { build(root, 1, n); } inline void modify(int l, int r, int d) { modify(root, 1, n, l, r, d); } inline int query(int l, int r = -1) { return query(root, 1, n, l, r >= 0? r: l); } private: inline void PushDown(int w) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; mx[ls] += tag[w]; mx[rs] += tag[w]; tag[ls] += tag[w]; tag[rs] += tag[w]; tag[w] = 0; } } inline int query(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return mx[w]; } else { PushDown(w); int mid = l + r + 1 >> 1, ret = 0; if (L < mid) { ret = max(ret, query(ch[w][0], l, mid - 1, L, R)); } if (mid <= R) { ret = max(ret, query(ch[w][1], mid, r, L, R)); } return ret; } } inline void modify(int w, int l, int r, int L, int R, int d) { if (L <= l && r <= R) { tag[w] += d; mx[w] += d; } else { PushDown(w); int mid = l + r + 1 >> 1; if (L < mid) { modify(ch[w][0], l, mid - 1, L, R, d); } if (mid <= R) { modify(ch[w][1], mid, r, L, R, d); } mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } inline void build(int &w, int l, int r) { static int cnt = 0; w = ++cnt; if (l == r) { mx[w] = dep[num[l]]; } else { int mid = l + r + 1 >> 1; build(ch[w][0], l, mid - 1); build(ch[w][1], mid, r); mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } }SGT; class LinkCutTree{ int ch[N][2], fa[N]; public: inline void SetFather(int w, int f) { fa[w] = f; } inline void access(int x) { for (int last = 0; x; last = x, x = fa[x]) { splay(x); if (fa[x]) { int p = GetMin(x); SGT.modify(in[p], ot[p], -1); } if (ch[x][1]) { int p = GetMin(ch[x][1]); SGT.modify(in[p], ot[p], 1); } ch[x][1] = last; } } private: inline bool IsRoot(int x) { return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x); } inline int GetMin(int x) { return ch[x][0]? GetMin(ch[x][0]): x; } inline void splay(int x) { for (int f, ff; !IsRoot(x); ) { f = fa[x], ff = fa[f]; if (IsRoot(f)) { rotate(x); } else { if ((ch[ff][0] == f) ^ (ch[f][0] == x)) { rotate(x); rotate(x); } else { rotate(f); rotate(x); } } } } inline void rotate(int x) { int f = fa[x], t = ch[f][1] == x; fa[x] = fa[f]; if (!IsRoot(f)) { ch[fa[f]][ch[fa[f]][1] == f] = x; } ch[f][t] = ch[x][t ^ 1]; fa[ch[x][t ^ 1]] = f; ch[x][t ^ 1] = f; fa[f] = x; } }LCT; inline void DFS(int w, int f) { static int ID = 0; LCT.SetFather(w, f); ff[w][0] = f; dep[w] = dep[f] + 1; num[in[w] = ++ID] = w; for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); } } ot[w] = ID; } int main() { n = read(); m = read(); for (int i = 1; i < n; i++) { AddEdge(read(), read()); } DFS(1, 0); for (int j = 1; j < LOG; j++) { for (int i = 1; i <= n; i++) { ff[i][j] = ff[ff[i][j - 1]][j - 1]; } } SGT.init(); for (int i = 1; i <= m; i++) { int opt = read(); if (opt == 1) { LCT.access(read()); } else if (opt == 2) { int u = read(), v = read(), lca = LCA(u, v); printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1); } else { int x = read(); printf("%d\n", SGT.query(in[x], ot[x])); } } return 0; }
【BZOJ 4589】Hard Nim
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589
解题报告
我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int MOD = 1000000007; const int REV = 500000004; bool vis[N]; int arr[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int Pow(int w, int t) { int ret = 1; for (; t; t >>= 1, w = (LL)w * w % MOD) { if (t & 1) { ret = (LL)ret * w % MOD; } } return ret; } inline void FWT(int *a, int len, int opt = 1) { for (int d = 1; d < len; d <<= 1) { for (int i = 0; i < len; i += d << 1) { for (int j = 0; j < d; j++) { int t1 = a[i + j], t2 = a[i + j + d]; if (opt == 1) { a[i + j] = (t1 + t2) % MOD; a[i + j + d] = (t1 - t2) % MOD; } else { a[i + j] = (LL)(t1 + t2) * REV % MOD; a[i + j + d] = (LL)(t1 - t2) * REV % MOD; } } } } } int main() { for (int n, m; ~scanf("%d %d", &n, &m); ) { memset(arr, 0, sizeof(arr)); for (int i = 2; i <= m; i++) { if (!vis[i]) { arr[i] = 1; for (int j = i << 1; 0 <= j && j <= m; j += i) { vis[j] = 1; } } } int len = 1; for (; len <= m; len <<= 1); FWT(arr, len); for (int i = 0; i < len; i++) { arr[i] = Pow(arr[i], n); } FWT(arr, len, -1); printf("%d\n", (arr[0] + MOD) % MOD); } return 0; }
【BZOJ 4599】[JLOI2016] 成绩比较
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286
解题报告
仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式,于是我们可以用拉格朗日插值来求解
于是总的时间复杂度:$O(mn^2)$
Code
这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200; const int MOD = 1000000007; int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline int Pow(int w, int t) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%MOD) { if (t & 1) { ret = (LL)ret * w % MOD; } } return ret; } inline int LagrangePolynomial(int x, int len, int *ff, int *xx) { int ret = 0; for (int i=1;i<=len;i++) { int tmp = ff[i]; for (int j=1;j<=len;j++) { if (i == j) continue; tmp = (LL)tmp * (x - xx[j]) % MOD; tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD; } ret = (ret + tmp) % MOD; } return (ret + MOD) % MOD; } int main() { n = read(); m = read(); K = read(); for (int i=1;i<=m;i++) { u[i] = read(); } for (int i=1;i<=m;i++) { r[i] = read(); } //预处理组合数 C[0][0] = 1; for (int i=1;i<=n;i++) { C[i][0] = 1; for (int j=1;j<=i;j++) { C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } //拉格朗日插值 for (int w=1;w<=m;w++) { for (int i=1;i<=n+1;i++) { f[i] = 0; h[i] = i; for (int j=1;j<=i;j++) { f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD; } } g[w] = LagrangePolynomial(u[w], n+1, f, h); } //广义容斥原理 int ans = 0; for (int i=K,t=1;i<=n;i++,t*=-1) { alpha[i] = C[n-1][i]; for (int j=1;j<=m;j++) { alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD; } ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD; } printf("%d\n",(ans+MOD)%MOD); return 0; }
【BZOJ 4318】OSU!
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/
解题报告
设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)},E_{(i,x)}$分别表示$x^2,x$的期望
那么根据全期望公式,我们有如下结论:
$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$
不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性,于是我们可以将前两个式子化为:
$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$
然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$
另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533
Code
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { int n=read(); double e1=0,e2=0,e3=0,ans=0,p; for (int i=1;i<=n;i++) { scanf("%lf",&p); ans += e3 * (1 - p); e3 = p * (e3 + 3 * e2 + 3 * e1 + 1); e2 = p * (e2 + 2 * e1 + 1); e1 = p * (e1 + 1); } printf("%.1lf\n",ans+e3); return 0; }
【BZOJ 3881】[COCI2015] Divljak
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html
解题报告
考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了
Code
#include<bits/stdc++.h> #define LL long long #define lowbit(x) ((x)&-(x)) using namespace std; const int N = 2000009; const int LOG = 26; const int SGZ = 26; int in[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } class Ac_Automaton{ int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N]; int head[N], to[N], nxt[N], ot[N], fa[N][LOG]; class FenwickTree{ int mx, sum[N]; public: inline void init(int nn) { mx = nn; } inline void modify(int p, int d) { for (int i = p; i <= mx; i += lowbit(i)) { sum[i] += d; } } inline int query(int l, int r) { int ret = 0; for (int i = l - 1; i > 0; i -= lowbit(i)) { ret -= sum[i]; } for (int i = r; i; i -= lowbit(i)) { ret += sum[i]; } return ret; } private: }bit; public: inline void insert(char *s, int nn, int id) { int w = root; for (int i = 1; i <= nn; i++) { int cc = s[i] - 'a'; if (!ch[w][cc]) { ch[w][cc] = ++cnt; } w = ch[w][cc]; } pos[id] = w; } inline void build() { static queue<int> que; for (int i = 0; i < SGZ; i++) { if (ch[root][i]) { que.push(ch[root][i]); } } for (; !que.empty(); que.pop()) { int w = que.front(); AddEdge(fail[w], w); for (int i = 0; i < SGZ; i++) { if (!ch[w][i]) { ch[w][i] = ch[fail[w]][i]; } else { que.push(ch[w][i]); fail[ch[w][i]] = ch[fail[w]][i]; } } } DFS(0, 0); for (int j = 1; j < LOG; j++) { for (int i = 0; i <= cnt; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; } } bit.init(cnt + 1); } inline void match(char *s, int nn) { static vector<int> vt[N]; static int que[N], stk[N], vis[N]; int qtot = 0, stot = 0, vtot = 0; que[++qtot] = root; for (int i = 1, w = root; i <= nn; i++) { w = ch[w][s[i] - 'a']; que[++qtot] = w; } sort(que + 1, que + 1 + qtot); qtot = unique(que + 1, que + 1 + qtot) - que - 1; sort(que + 1, que + 1 + qtot, cmp); for (int i = 1; i <= qtot; i++) { if (stot) { int lca = LCA(que[i], stk[stot]); for (; stot && dep[stk[stot]] > dep[lca]; --stot) { if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) { vt[stk[stot - 1]].push_back(stk[stot]); } else { vt[lca].push_back(stk[stot]); } } if (stot && stk[stot] != lca) { stk[++stot] = lca; vis[++vtot] = lca; } } stk[++stot] = que[i]; vis[++vtot] = que[i]; } for (; stot > 1; --stot) { vt[stk[stot - 1]].push_back(stk[stot]); } update(root, vt); for (int i = 1; i <= vtot; i++) { vt[vis[i]].clear(); } } inline int query(int id) { return bit.query(in[pos[id]], ot[pos[id]]); } private: inline void update(int w, vector<int> *vt) { for (int i = 0; i < (int)vt[w].size(); i++) { bit.modify(in[w], -1); bit.modify(in[vt[w][i]], 1); update(vt[w][i], vt); } } inline int LCA(int a, int b) { if (dep[a] < dep[b]) { swap(a, b); } for (int j = SGZ - 1; ~j; j--) { if (dep[fa[a][j]] >= dep[b]) { a = fa[a][j]; } } if (a == b) { return a; } for (int j = SGZ - 1; ~j; j--) { if (fa[a][j] != fa[b][j]) { a = fa[a][j]; b = fa[b][j]; } } return fa[a][0]; } static bool cmp(int a, int b) { return in[a] < in[b]; } inline void DFS(int w, int f) { static int tt = 0; in[w] = ++tt; dep[w] = dep[fa[w][0] = f] + 1; for (int i = head[w]; i; i = nxt[i]) { DFS(to[i], w); } ot[w] = tt; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } }ac; int main() { static char ss[N]; int n = read(); for (int i = 1; i <= n; i++) { scanf("%s", ss + 1); int len = strlen(ss + 1); ac.insert(ss, len, i); } ac.build(); int m = read(); for (int i = 1; i <= m; i++) { if (read() == 1) { scanf("%s", ss + 1); int len = strlen(ss + 1); ac.match(ss, len); } else { printf("%d\n", ac.query(read())); } } return 0; }
【BZOJ 3672】[NOI2014] 购票
解题报告
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809
解题报告
一句话题解:树上CDQ分治
先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$
我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = N << 1; const LL INF = 6e18; int n, head[N], nxt[M], to[M], fa[N]; LL q[N], p[N], len[N], dep[N], f[N]; struct Point{ LL x, y, id, range; inline Point() { } inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) { } inline bool operator < (const Point &P) const { return x > P.x || (x == P.x && y > P.y); } inline Point operator - (const Point &P) { return Point(x - P.x, y - P.y, 0, 0); } inline double operator * (const Point &P) { return (double)x * P.y - (double)y * P.x; } inline double slope(const Point &P) { return (double)(y - P.y) / (x - P.x); } static bool update(const Point &P1, const Point &P2) { return P1.range > P2.range; } }; inline LL read() { char c = getchar(); LL ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } class DivideAndConquer{ int sz[N], vis[N]; public: inline void solve(int w, int universe) { int top = w; vis[w = FindRoot(w, universe)] = 1; if (fa[w] && !vis[fa[w]]) { solve(top, universe - sz[w]); } vector<Point> cvx; for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) { cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw])); } vector<Point> que; que.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { DFS(to[i], w, que); } } sort(que.begin(), que.end(), Point::update); sort(cvx.begin(), cvx.end()); for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) { for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) { for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot); cvx[tot++] = cvx[j]; } int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id; while (l <= r) { mid = l + r >> 1; if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) { ret = mid; r = mid - 1; } else { l = mid + 1; } } if (ret >= 0) { f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]); } } for (int i = 0, j; i < (int)que.size(); i++) { if (j = que[i].id, que[i].range <= dep[w]) { f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]); } } que.clear(); cvx.clear(); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { solve(to[i], sz[to[i]]); } } } private: inline int FindRoot(int w, int universe) { int ret = 0, ans; FindRoot(w, w, universe, ret, ans); return ret; } inline void FindRoot(int w, int f, int universe, int &ret, int &ans) { int mx = 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { FindRoot(to[i], w, universe, ret, ans); sz[w] += sz[to[i]]; mx = max(mx, sz[to[i]]); } } mx = max(mx, universe - sz[w]); if (!ret || mx < ans) { ans = mx; ret = w; } } inline void DFS(int w, int f, vector<Point> &ret) { ret.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { DFS(to[i], w, ret); } } } }DAC; int main() { n = read(); read(); for (int i = 2; i <= n; i++) { fa[i] = read(); LL c = read(); AddEdge(fa[i], i); p[i] = read(); q[i] = read(); len[i] = read(); dep[i] = dep[fa[i]] + c; } fill(f, f + N, INF); f[1] = 0; dep[0] = -1; DAC.solve(1, n); for (int i = 2; i <= n; i++) { printf("%lld\n", f[i]); } return 0; }
【BZOJ 4198】[NOI2015] 荷马史诗
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4198
解题报告
k叉哈夫曼树
注意最大化儿子不满的那个结点的深度
Code
#include<bits/stdc++.h> #define LL long long using namespace std; struct Data{ LL apt, mx; inline Data() { } inline Data(LL a, LL c):apt(a), mx(c) { } inline Data operator + (const Data &d) { return Data(apt + d.apt, max(mx, d.mx + 1)); } inline bool operator < (const Data &d) const { return apt > d.apt || (apt == d.apt && mx > d.mx); } }; priority_queue<Data> que; inline LL read() { char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main() { int n = read(), k = read(); for (int i = 1; i <= n; i++) { que.push(Data(read(), 0)); } LL ans = 0; for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) { Data np(0, 0); for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) { np = np + que.top(); que.pop(); } ans += np.apt; que.push(np); } printf("%lld\n%lld\n", ans, que.top().mx); return 0; }
【BZOJ 3940】[Usaco2015 Feb] Censoring
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3940
解题报告
用栈和AC自动机来模拟即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int SGZ = 26; char ctn[N], wrd[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } class AC_Automaton{ int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N]; queue<int> que; public: inline void insert(char *s, int len) { int w = Root; for (int i = 1; i <= len; i++) { int cc = s[i] - 'a'; if (!ch[w][cc]) { ch[w][cc] = ++cnt; dep[cnt] = dep[w] + 1; } w = ch[w][cc]; } apt[w] = len; } inline void build() { for (int i = 0; i < SGZ; i++) { if (ch[Root][i]) { que.push(ch[Root][i]); } } for (; !que.empty(); que.pop()) { int w = que.front(); for (int i = 0; i < SGZ; i++) { if (ch[w][i]) { fail[ch[w][i]] = ch[fail[w]][i]; apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]); que.push(ch[w][i]); } else { ch[w][i] = ch[fail[w]][i]; } } } } inline int root() { return Root; } inline int move(int &w, int cc) { w = ch[w][cc]; return apt[w]; } }aca; int main() { scanf("%s", ctn + 1); int n = read(), m = strlen(ctn + 1); for (int i = 1; i <= n; i++) { scanf("%s", wrd + 1); aca.insert(wrd, strlen(wrd + 1)); } aca.build(); vector<int> ans, pos; for (int i = 1; i <= m; i++) { int w = pos.empty()? aca.root(): *--pos.end(); int len = aca.move(w, ctn[i] - 'a'); ans.push_back(ctn[i]); pos.push_back(w); for (int j = 1; j <= len; j++) { ans.pop_back(); pos.pop_back(); } } for (int i = 0; i < (int)ans.size(); i++) { putchar(char(ans[i])); } return 0; }
【BZOJ 4566】[HAOI2016] 找相同字符
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4566
解题报告
我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 800009; const int SGZ = 27; int n, m; char s[N]; class Suffix_Automaton{ int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N]; public: inline void init() { cnt = tail = 1; for (int i = 1; i <= n; i++) { append(s[i] - 'a', 0); } append(SGZ - 1, -1); for (int i = n + 2; i <= n + m + 1; i++) { append(s[i] - 'a', 1); } for (int i = 1; i <= cnt; i++) { AddEdge(fail[i], i); } DFS(0, 0); } inline LL query() { LL ret = 0; for (int i = 1; i <= cnt; i++) { ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1]; } return ret; } private: inline void DFS(int w, int f) { for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); sz[w][0] += sz[to[i]][0]; sz[w][1] += sz[to[i]][1]; } } } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void append(char cc, int t) { int w = tail, cur = ++cnt; if (t != -1) { sz[cur][t] += 1; } len[cur] = len[tail] + 1; for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]); if (w) { if (len[ch[w][cc]] == len[w] + 1) { fail[cur] = ch[w][cc]; } else { int nt = ++cnt, pt = ch[w][cc]; memcpy(ch[nt], ch[pt], sizeof(ch[nt])); len[nt] = len[w] + 1; fail[nt] = fail[pt]; fail[cur] = fail[pt] = nt; for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]); } } else { fail[cur] = 1; } } }sam; int main() { scanf("%s", s + 1); n = strlen(s + 1); s[n + 1] = 'z' + 1; scanf("%s", s + n + 2); m = strlen(s + n + 2); sam.init(); printf("%lld\n", sam.query()); return 0; }
【BZOJ 4195】[NOI2015] 程序自动分析
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4195
解题报告
用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = 300009; int n, fa[N], cet[M], val[N], dif[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int find(int x) { return fa[x] == x? x: fa[x] = find(fa[x]); } int main() { freopen("prog.in", "r", stdin); freopen("prog.out", "w", stdout); for (int T = read(); T; T--) { n = read(); int tot = 0, cnt = 0, tt = 0; for (int i = 1; i <= n; i++) { cet[++tot] = val[++cnt] = read(); cet[++tot] = val[++cnt] = read(); cet[++tot] = read(); } sort(val + 1, val + 1 + cnt); cnt = unique(val + 1, val + 1 + cnt) - val - 1; for (int i = 1; i <= cnt; i++) { fa[i] = i; } for (int i = 1; i <= n; i++) { int t = cet[tot--]; int u = cet[tot--], v = cet[tot--]; u = lower_bound(val + 1, val + 1 + cnt, u) - val; v = lower_bound(val + 1, val + 1 + cnt, v) - val; if (t == 1) { fa[find(u)] = find(v); } else { dif[++tt] = u; dif[++tt] = v; } } bool ok = 1; for (int i = 1; i <= tt; i += 2) { int u = dif[i], v = dif[i + 1]; if (find(u) == find(v)) { ok = 0; break; } } puts(ok? "YES": "NO"); } return 0; }
【BZOJ 4196】[NOI2015] 软件包管理器
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4196
解题报告
考虑树链剖分
线段树部分只需要支持区间赋值,查询区间中1的个数
总的时间复杂度:$O(n \log ^ 2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 200009; int n, m, head[N], nxt[N], to[N], beg[N], ot[N]; int fa[N], top[N], hvy[N], sz[N], dep[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void DFS1(int w, int f) { fa[w] = f; dep[w] = dep[f] + 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { DFS1(to[i], w); sz[w] += sz[to[i]]; if (sz[to[i]] > sz[hvy[w]]) { hvy[w] = to[i]; } } } inline void DFS2(int w, int t) { static int dfc = 0; beg[w] = ++dfc; top[w] = t; if (hvy[w]) { DFS2(hvy[w], t); for (int i = head[w]; i; i = nxt[i]) { if (to[i] != hvy[w]) { DFS2(to[i], to[i]); } } } ot[w] = dfc; } class Segment_Tree{ int cnt, root, ch[M][2], sum[M], tag[M]; public: inline void init() { init(root, 1, n); } inline int install(int w) { int ret = 0, tmp; while (true) { int l = beg[top[w]], r = beg[w], len = r - l + 1; tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1); ret += tmp; if (fa[top[w]] != w && tmp) { w = fa[top[w]]; } else { break; } } return ret; } inline int uninstall(int w) { return modify(root, 1, n, beg[w], ot[w], -1); } private: inline void init(int &w, int l, int r) { w = ++cnt; if (l < r) { int mid = l + r + 1 >> 1; init(ch[w][0], l, mid - 1); init(ch[w][1], mid, r); } } inline void PushDown(int w, int l, int mid, int r) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; if (tag[w] == 1) { sum[ls] = mid - l; sum[rs] = r - mid + 1; } else { sum[ls] = sum[rs] = 0; } tag[ls] = tag[rs] = tag[w]; tag[w] = 0; } } inline int modify(int w, int l, int r, int L, int R, int t) { if (L <= l && r <= R) { int ret = sum[w]; sum[w] = t == -1? 0: r - l + 1; tag[w] = t; return ret; } else { int mid = l + r + 1 >> 1, ret = 0; PushDown(w, l, mid, r); if (L < mid) { ret += modify(ch[w][0], l, mid - 1, L, R, t); } if (mid <= R) { ret += modify(ch[w][1], mid, r, L, R, t); } sum[w] = sum[ch[w][1]] + sum[ch[w][0]]; return ret; } } }SGT; int main() { freopen("manager.in", "r", stdin); freopen("manager.out", "w", stdout); n = read(); for (int i = 2; i <= n; i++) { AddEdge(read() + 1, i); } DFS1(1, 1); DFS2(1, 1); SGT.init(); m = read(); char cmd[20]; for (int i = 1; i <= m; i++) { scanf("%s", cmd + 1); if (cmd[1] == 'i') { printf("%d\n", SGT.install(read() + 1)); } else { printf("%d\n", SGT.uninstall(read() + 1)); } } return 0; }