初步认识树上差分
学习树上差分的前提是:
- 最近公共祖先(LCA)
- 线性差分
学习了这些之后,我们就可以开始学习树上差分了。树上差分的思想跟差分类似:都是在不得不求前缀和的情况下,将区间操作变为单点操作,降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过,所以学习树上差分很有必要(我怀疑是出题组不敢出树链剖分,但又要考察选手们对树上操作的熟悉程度,所以采用了这么个坑爹玩意)。我们先来学习一个基本的操作:点的链上区间加。
学习树上差分的前提是:
学习了这些之后,我们就可以开始学习树上差分了。树上差分的思想跟差分类似:都是在不得不求前缀和的情况下,将区间操作变为单点操作,降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过,所以学习树上差分很有必要(我怀疑是出题组不敢出树链剖分,但又要考察选手们对树上操作的熟悉程度,所以采用了这么个坑爹玩意)。我们先来学习一个基本的操作:点的链上区间加。
这道题还是很有意思的,建图方式非常的巧妙。首先我们先把第一问的 DP 用 \(O(n \log n)\) 的时间求解一下,顺便搞到一个数组\(f[i]\),含义是以\(i\)为结尾的最长子序列长度。建图的时候要注意的是,每一个位置对应的点要拆成两个:这是为了保持答案的唯一性。所以对于\(f[i]=1\)的点\(i\),连边\((s,i)\);对于\(f[i]=k\)的点\(i\),连边\((i+n,t)\)。之后,如果对于\((u,v), f[v] = f[u] + 1, arr[u] \leq arr[v]\)进行连边,跑个最大流就可以出答案了。
第三问其实跟第二问的差不多,只需要把点\(1\)和点\(n\)的外向边(到源点或者是汇点的边)的最大流限制改成无穷大即可。
今天比赛状态极差,又困、又饿,眼睛又干。
我们先把问题转换为三角矩阵上两点的距离,可以类比曼哈顿距离,我们可以把距离分为纵向和横向两种来考虑。
首先是纵向。如果\((x_1,y_1)\)要到\((x_2,y_2)\),那么分下面几种情况:
那么再来看横向。我们发现,如果我们把上方的三角形扩大成这样:
我们发现,这一范围内的三角形不需要额外的横向贡献,只需要计算纵向贡献即为答案。对于在同一行却不在这个区域内的三角形,横向贡献也非常好计算,做差乘二即可。
记得要对输入点进行排序。
// A.cpp #include <bits/stdc++.h> #define pr pair<int, int> using namespace std; const int MAX_N = 1001000; pr prs[MAX_N]; int n, m, si, sj; int answer, exitI, exitJ; int main() { answer = 0x3f3f3f3f; scanf("%d%d%d%d", &m, &n, &si, &sj); for (int i = 1; i <= n; i++) scanf("%d%d", &prs[i].first, &prs[i].second); sort(prs + 1, prs + 1 + n); for (int i = 1; i <= n; i++) { pr pta = prs[i], ptb = make_pair(si, sj); if (pta.first < ptb.first) swap(pta, ptb); int jl = ptb.second, jr = ptb.second + (pta.first - ptb.first) * 2; int ans = (pta.first - ptb.first) << 1; if (pta.second >= jl && pta.second <= jr && (ans < answer || (ans == answer && exitJ >= prs[i].second))) { answer = ans, exitI = prs[i].first, exitJ = prs[i].second; if ((pta.second & 1) != (ptb.second & 1)) answer -= 1; continue; } ans += min(abs(pta.second - jl), abs(pta.second - jr)); if (ans < answer || (ans == answer && exitJ >= prs[i].second)) answer = ans, exitI = prs[i].first, exitJ = prs[i].second; } printf("%d %d\n%d", exitI, exitJ, answer + 1); return 0; }
首先,这道题的\(w_i\)毫无卵用。我们来看这个\(w_i\)对亏损的贡献:
\[ \sum_{i=1}^{n}( i-w_{s_i} )= \frac{n(n-1)}{2}-\sum_{i=1}^{n} w_i \]
所以顺序根本不会造成影响。所以,我们来找一条最短的一笔画路径且字典序最小,方可保证答案最简。
因为题目里明显的说了(可惜我没看到,眼瞎了)
能够离开每个村子的路口的数目一定是2,4或者8。
我可真是个傻逼。
所以,用邻接表存图,然后按标号从小到大进行 DFS 写栈,最后反向弹栈输出即可。
// B.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 220; int n, m, wi[MAX_N], tmpx, tmpy, dist[MAX_N][MAX_N], tot; stack<int> stk; void dfs(int u) { for (int i = 1; i <= n; i++) if (dist[u][i]) { dist[u][i]--, dist[i][u]--; dfs(i); } stk.push(u); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &wi[i]); for (int i = 1; i <= m; i++) scanf("%d%d", &tmpx, &tmpy), dist[tmpx][tmpy]++, dist[tmpy][tmpx]++; dfs(1); printf("%d\n", stk.size() - 1); while (!stk.empty()) printf("%d ", stk.top()), stk.pop(); return 0; }
我们可以考虑设置状态\(f[i][j][k]\)为从节点\(i\)到\(j\)走了\(k\)条边的总长度,然后 Floyd 预处理,最后\(O(n)\)回答即可,傻逼题。
// C.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 55, MAX_M = 1200; int n, m, tmpx, tmpy, tmpz, f[MAX_N][MAX_N][MAX_M], dist[MAX_N][MAX_N], q; int main() { scanf("%d%d", &n, &m); memset(f, 0x3f, sizeof(f)), memset(dist, 0x3f, sizeof(dist)); for (int i = 1; i <= m; i++) scanf("%d%d%d", &tmpx, &tmpy, &tmpz), dist[tmpx][tmpy] = min(dist[tmpx][tmpy], tmpz); for (int i = 1; i <= n; i++) f[i][i][0] = 0; for (int s = 1; s <= n; s++) for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (f[i][j][s] > f[i][k][s - 1] + dist[k][j]) f[i][j][s] = f[i][k][s - 1] + dist[k][j]; scanf("%d", &q); while (q--) { double ans = (double)0x3f3f3f3f; int i, j; bool flag = true; scanf("%d%d", &i, &j); for (int s = 1; s <= n; s++) if (1.0 * f[i][j][s] / (1.0 * s) < ans && f[i][j][s] != (double)0x3f3f3f3f) ans = min(ans, 1.0 * f[i][j][s] / (1.0 * s)), flag = false; if (flag) puts("OMG!"); else printf("%.3lf\n", ans); } return 0; }
说实话,这就是我最薄弱的一项,且在比赛中一览无余的暴露出来了。
我们可以把这道题转换一下,可以发现,这个喜悦值毫无关系,第二题的题意即为
给一些物品\(a_i\),每次操作有\(p_i\)的概率可能出现,求要使所有物品出现的期望操作次数。
考虑物品的个数很少,可以进行状压,压缩到\(S\)。对于每一个出现过物品\(i\)的情况,都可以从没有出现过的状态转移过来,即S^(1<<(i - 1))
。对之前的情况乘上一个\(p_i\)即为这一部分的贡献。之后,因为\(\sum_{i} {p_i} \neq 1\),所以存在操作无效的情况,也就是\((1-\sum_{i\in S} p_i)*E_S\)。之后加上操作次数\(1\),式子全貌为:
\[ E_S = (\sum_{i\in S} p_i*E_{S’}) + (1-\sum_{i\in S} p_i)*E_S + 1 \]
移项合并可得:
\[ (\sum_{i\in S} p_i)*E_S = (\sum_{i\in S} p_i*E_{S’}) + 1 \\ E_S = \frac{(\sum_{i\in S} p_i*E_{S’}) + 1}{\sum_{i\in S} p_i} \]
// A.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 21; int n, wi[MAX_N]; long long ans1; double pi[MAX_N], dp[(1 << 20)]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf%d", &pi[i], &wi[i]), ans1 += wi[i]; for (int stat = 0; stat < (1 << n); stat++) { double psum = 0, ans = 0; for (int i = 1; i <= n; i++) if (stat & (1 << (i - 1))) { int prestat = stat ^ (1 << (i - 1)); psum += pi[i]; ans += pi[i] * dp[prestat]; } if (psum != 0) dp[stat] = (ans + 1) / psum; } printf("%lld\n%.3lf", ans1, dp[(1 << n) - 1]); return 0; }
啊,我*。
这道题很水,不讲。
/// B.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 100400, MAX_M = 1e5 + 2000; int head[MAX_N], current, dfn[MAX_N], low[MAX_N], tot, st[MAX_N], hd, aff[MAX_N]; int totp, n, m, tmpx, tmpy, tmpz, ufs[MAX_N], dist[MAX_N]; bool inst[MAX_N]; struct edge { int to, nxt, weight, from; bool operator<(const edge &e) const { return weight > e.weight; } } edges[MAX_M << 1]; int find(int x) { return (ufs[x] == x) ? x : ufs[x] = find(ufs[x]); } void unite(int x, int y) { if (find(x) != find(y)) ufs[find(x)] = find(y); } int addpath(int u, int v, int weight) { edges[current].to = v, edges[current].nxt = head[u]; edges[current].from = u; edges[current].weight = weight, head[u] = current++; return current - 1; } void tarjan(int u) { inst[u] = true, st[++hd] = u; dfn[u] = ++tot, low[u] = dfn[u]; for (int i = head[u]; i != -1; i = edges[i].nxt) if (dfn[edges[i].to] == 0) tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]); else if (inst[edges[i].to]) low[u] = min(low[u], dfn[edges[i].to]); if (dfn[u] == low[u]) { int j; totp++; do { j = st[hd], aff[j] = totp; inst[j] = false; } while (st[hd--] != u); } } int main() { while (scanf("%d%d", &n, &m) && n != 0 && m != 0) { memset(dist, 0x3f, sizeof(dist)); memset(st, 0, sizeof(st)), memset(dfn, 0, sizeof(dfn)), hd = 0; for (int i = 1; i <= 2 * n; i++) ufs[i] = i; memset(head, -1, sizeof(head)), memset(aff, 0, sizeof(aff)); totp = n, current = 0, tot = 0; for (int i = 1; i <= m; i++) scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx + 1, tmpy + 1, tmpz); tarjan(1); for (int i = 1; i <= n; i++) for (int e = head[i]; e != -1; e = edges[e].nxt) if (aff[i] != aff[edges[e].to]) dist[aff[edges[e].to]] = min(dist[aff[edges[e].to]], edges[e].weight); long long ans = 0; for (int i = n + 1; i <= totp; i++) if (aff[1] != i) ans += dist[i]; printf("%lld\n", ans); } return 0; }
这道题来自于 Codeforces,画风十分一至。
首先转换题意,这道题提示了每一个横纵坐标都只会存在一个点,求长为\(len\)且纵坐标最大最小值也为\(len\)的区间个数。我们可以用分治来搞一搞。首先定一个区间\([l,r]\),中点为\(mid\)。我们来探索跨这两个小区间的几种情况。
首先,我们在分类讨论之前设定几个数组:
设\(minl[i]\)为区间\([i,mid]\)的最小值,\(maxl[i]\)为区间\([i,mid]\)的最大值;
设\(minr[i]\)为区间\([mid+1,i]\)的最小值,\(maxr[i]\)为区间\([mid+1,i]\)的最大值。
那么,我们可以讨论跨越的情况:
最值都在左、右同一个区间内
最值分别在两个不同的区间
(i\),可以根据最值之差算出右端点,进行检查并计数。
第二种稍稍麻烦一点:跨区间要考虑最值的两种分布方式,我们以最小值在左侧,最大值在右侧为例,假设有个点符合条件:
\[ maxr[j]-minl[i] = j-i \\ \text{移项得} \\ maxr[j]-j=minl[i]-i \]
可以枚举断点,把计算内容放到桶里去(注意负数,加上数域偏移),然后用两个指针判断合法区间,左端指针减一,右指针加一。
// C.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 50200, NUM_DOMAIN = 6e5; pair<int, int> prs[MAX_N]; int arr[MAX_N], n, maxl[MAX_N], maxr[MAX_N], minl[MAX_N], minr[MAX_N], bucket[2 * NUM_DOMAIN + 1]; long long answer = 0; void dq(int l, int r) { if (l == r) { answer++; return; } int mid = (l + r) >> 1; // preprocessing; minl[mid] = arr[mid], maxl[mid] = arr[mid]; maxr[mid + 1] = arr[mid + 1], minr[mid + 1] = arr[mid + 1]; for (int i = mid - 1; i >= l; i--) minl[i] = min(minl[i + 1], arr[i]), maxl[i] = max(maxl[i + 1], arr[i]); for (int i = mid + 2; i <= r; i++) maxr[i] = max(maxr[i - 1], arr[i]), minr[i] = min(minr[i - 1], arr[i]); // make judges; // at the left: for (int i = mid; i >= l; i--) { int j = i + (maxl[i] - minl[i]); if (j > mid && j <= r && minr[j] > minl[i] && maxr[j] < maxl[i]) answer++; } // at the right; for (int i = mid + 1; i <= r; i++) { int j = i - (maxr[i] - minr[i]); if (j <= mid && j >= l && minl[j] > minr[i] && maxl[j] < maxr[i]) answer++; } // in the middle; // min|max: int ptr1 = mid + 1, ptr2 = mid; for (int i = mid; i >= l; i--) { while (minr[ptr2 + 1] > minl[i] && ptr2 < r) ptr2++, bucket[maxr[ptr2] - ptr2 + NUM_DOMAIN]++; while (maxl[i] > maxr[ptr1]) { bucket[maxr[ptr1] - ptr1 + NUM_DOMAIN]--, ptr1++; if (ptr1 > r) break; } if (ptr1 > r) break; if (ptr1 <= ptr2) answer += bucket[minl[i] - i + NUM_DOMAIN]; } for (int i = mid; i >= l; i--) bucket[minl[i] - i + NUM_DOMAIN] = 0; for (int i = mid + 1; i <= r; i++) bucket[maxr[i] - i + NUM_DOMAIN] = 0; // max|min: ptr1 = mid, ptr2 = mid + 1; for (int i = mid + 1; i <= r; i++) { while (minl[ptr2 - 1] > minr[i] && ptr2 > l) ptr2--, bucket[maxl[ptr2] + ptr2 + NUM_DOMAIN]++; while (maxr[i] > maxl[ptr1]) { bucket[maxl[ptr1] + ptr1 + NUM_DOMAIN]--, ptr1--; if (ptr1 < l) break; } if (ptr1 < l) break; if (ptr2 <= ptr1) answer += bucket[minr[i] + i + NUM_DOMAIN]; } for (int i = mid + 1; i <= r; i++) bucket[minr[i] + i + NUM_DOMAIN] = 0; for (int i = mid; i >= l; i--) bucket[maxl[i] + i + NUM_DOMAIN] = 0; dq(l, mid), dq(mid + 1, r); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &prs[i].first, &prs[i].second); for (int i = 1; i <= n; i++) arr[prs[i].first] = prs[i].second; dq(1, n); printf("%lld", answer); return 0; }
这个模型有点儿牛逼哦。
我们先来建一个网络。我们把我们得到的\(n\)个点复制一遍,变成第\(i\)与第\(i+n\)个点。让源点全部连接点域\([1,n]\)内的点,让点域\([n+1,2n]\)内的点全部连接汇点。如果有边\((u,v)\),连接边\((u,v+n)\)。这里面所有的边容量都是\(1\)。求最大流做差即可。
我们把网络分层(把它想成 3D 的形状),第一层是源点和原生点,第二层是复制点和汇点。这两层之间的边都相当于有向无环图里的单向边,求最大流即可知道哪些不是路径覆盖中的点。
// LOJ6002.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 200 * 3, INF = 0x3f3f3f3f; int n, m, head[MAX_N], current, upward[MAX_N], s, t, dep[MAX_N], cur[MAX_N], tmpx, tmpy; bool tag[MAX_N]; struct edge { int to, nxt, weight; } edges[6000 << 2]; void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].weight = weight; edges[current].nxt = head[src], head[src] = current++; } void add(int src, int dst, int w) { addpath(src, dst, w), addpath(dst, src, 0); } bool bfs() { memset(dep, 0, sizeof(dep)); queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && !dep[edges[i].to]) q.push(edges[i].to), dep[edges[i].to] = dep[u] + 1; } return dep[t] != 0; } int dfs(int u, int flow) { if (u == t || flow == 0) return flow; for (int &i = cur[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1) { int to = edges[i].to, fl = dfs(to, min(edges[i].weight, flow)); if (fl > 0) { upward[u] = edges[i].to; if (u != s) tag[edges[i].to - n] = true; edges[i].weight -= fl, edges[i ^ 1].weight += fl; return fl; } } return 0; } int Dinic() { int ans = 0; while (bfs()) { for (int i = 1; i <= 2 * n + 2; i++) cur[i] = head[i]; while (int fl = dfs(s, INF)) ans += fl; } for (int i = 1; i <= n; i++) if (!tag[i]) { int p = i; printf("%d ", p); while (upward[p] && upward[p] != t) printf("%d ", upward[p] - n), p = upward[p] - n; printf("\n"); } return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); s = n * 2 + 1, t = s + 1; for (int i = 1; i <= n; i++) add(s, i, 1), add(i + n, t, 1); for (int i = 1; i <= m; i++) { scanf("%d%d", &tmpx, &tmpy); add(tmpx, tmpy + n, 1); } printf("%d", n - Dinic()); return 0; }
明显的最大权闭合子图,把实验和器材连边,并且变通一下边权,求最大流并记录最小割上的点即可。输入输出略显毒瘤。
// LOJ6001.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 2000, INF = 0x3f3f3f3f; int m, n, s, t, head[MAX_N], current, cur[MAX_N], dep[MAX_N], tmpx; bool vis[MAX_N]; string tmp; struct edge { int to, nxt, weight; } edges[MAX_N << 2]; void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } bool bfs() { memset(dep, 0, sizeof(dep)), memset(vis, 0, sizeof(vis)); queue<int> q; q.push(s), dep[s] = 1; do { int u = q.front(); q.pop(), vis[u] = true; for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && !dep[edges[i].to]) dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to); } while (!q.empty()); return dep[t] != 0; } int dfs(int u, int flow) { if (u == t || flow == 0) return flow; for (int &i = cur[u]; i != -1; i = edges[i].nxt) if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0) { int to = edges[i].to, fl = dfs(to, min(flow, edges[i].weight)); if (fl > 0) { edges[i].weight -= fl, edges[i ^ 1].weight += fl; return fl; } } return 0; } int dinic() { int ans = 0; while (bfs()) { for (int i = 1; i <= n + m + 2; i++) cur[i] = head[i]; while (int flow = dfs(s, INF)) ans += flow; } return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d\n", &m, &n); s = n + m + 1, t = s + 1; int ans = 0; for (int i = 1; i <= m; i++) { getline(cin, tmp); stringstream ss; ss << tmp, ss >> tmpx; addpath(s, i, tmpx), addpath(i, s, 0); ans += tmpx; while (ss >> tmpx) addpath(i, tmpx + m, INF), addpath(tmpx + m, i, 0); } for (int i = 1; i <= n; i++) scanf("%d", &tmpx), addpath(i + m, t, tmpx), addpath(t, i + m, 0); ans -= dinic(); queue<int> q; for (int i = 1; i <= m; i++) if (vis[i]) q.push(i); while (!q.empty()) { int pt = q.front(); q.pop(), printf("%d", pt); if (!q.empty()) printf(" "); } puts(""); for (int i = 1; i <= n; i++) if (vis[i + m]) q.push(i); while (!q.empty()) { int pt = q.front(); q.pop(), printf("%d", pt); if (!q.empty()) printf(" "); } puts(""); printf("%d", ans); return 0; }