A – 完全背包
这道题真的是令人窒息,也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然:相同体积的物品归为一种物品,且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的,而且全部分数的容量非常之大,所以正常的 DP 优化是行不通的。做完上面的压缩之后,可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略:
这道题真的是令人窒息,也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然:相同体积的物品归为一种物品,且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的,而且全部分数的容量非常之大,所以正常的 DP 优化是行不通的。做完上面的压缩之后,可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略:
这道题在 JZOJ 上面开 10s,遂 AC。
// A.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 60100; struct point { int x, y, prop, id; bool operator<(const point &pt) const { return prop < pt.prop; } } nodes[MAX_N], *cur[MAX_N]; int n, m; char opt[10]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d%d%d", &nodes[i].x, &nodes[i].y, &nodes[i].prop), nodes[i].id = i; sort(nodes + 1, nodes + 1 + n); for (int i = 1; i <= n; i++) cur[nodes[i].id] = &nodes[i]; while (m--) { scanf("%s", opt + 1); int x, y, x_, y_, k; if (opt[1] == 'Q') { scanf("%d%d%d%d%d", &x, &y, &x_, &y_, &k); bool flag = false; for (int i = 1; i <= n; i++) if (nodes[i].x <= max(x, x_) && nodes[i].x >= min(x, x_) && nodes[i].y <= max(y, y_) && nodes[i].y >= min(y, y_)) { k--; if (k == 0) { printf("%d\n", nodes[i].prop), flag = true; break; } } if (!flag) puts("It doesn't exist."); } else { scanf("%d%d", &x, &y), x++, y++; swap(cur[x]->x, cur[y]->x), swap(cur[x]->y, cur[y]->y); swap(cur[x]->id, cur[y]->id), swap(cur[x], cur[y]); } } return 0; }
这道题应该算是点分治的一道经典题目。点分治的精髓就在于找到重心、对子树进行计算并且合并答案,之后删除中心变成子树内的小问题,分治思想非常的巧妙。
我们首先写好找根函数:
// root finding functions; void dfs1(int u, int fa, int siz) { son[u] = 1; int res = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (edges[i].to == fa || done[edges[i].to]) continue; dfs1(edges[i].to, u, siz); son[u] += son[edges[i].to]; res = max(res, son[edges[i].to] - 1); } res = max(res, siz - son[u]); if (res < rootKey) root = u, rootKey = res; } void findRoot(int src, int siz) { root = src, rootKey = siz; dfs1(src, 0, siz); }
遍历子树:我们设定一个\(dist[]\)数组,算出距离的答案,并且无视曾经被当作根的节点,并向cnt[from[u]]
进行自增操作,维护子树的大小,并把本身编号加入vec
供之后进行排序用途。
// the calc one; void dfs(int u, int fa) { vec.push_back(u); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa && !done[edges[i].to]) { cnt[from[u]]++; dist[edges[i].to] = dist[u] + edges[i].weight; from[edges[i].to] = from[u]; dfs(edges[i].to, u); } }
点分治:我们在计算完子树答案之后,合并的方法是主要的问题。我们可以考虑将vec
进行排序,然后通过递增的性质设置首尾指针,并且去除掉当前子树内的错误答案(因为子树内部的路径不经过根,所以要去掉,之后的分治子问题中会处理这些内部路径)。
void pdq(int curt, int siz) { memset(son, 0, sizeof(son)); memset(cnt, 0, sizeof(cnt)); findRoot(curt, siz); dist[root] = 0, done[root] = true; vec.clear(), vec.push_back(root), from[root] = root; cnt[root]++; for (int i = head[root]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) { from[edges[i].to] = edges[i].to, cnt[edges[i].to]++; dist[edges[i].to] = edges[i].weight; dfs(edges[i].to, root); } sort(vec.begin(), vec.end(), compare); cnt[from[vec[0]]]--; int l = 0, r = vec.size() - 1; while (l < r) { while (dist[vec[l]] + dist[vec[r]] > k) cnt[from[vec[r--]]]--; answer += r - l - cnt[from[vec[l]]]; cnt[from[vec[++l]]]--; } int pos = root; for (int i = head[pos]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) pdq(edges[i].to, son[edges[i].to]); }
嗯,写完了。具体代码如下:
// POJ1741.cpp #include <cstdio> #include <vector> #include <algorithm> #include <iostream> #include <cstring> using namespace std; const int MAX_N = 10100, INF = 0x3f3f3f3f; int head[MAX_N], current, k, n, tmpx, tmpy, tmpz, root, rootKey, son[MAX_N]; int from[MAX_N], dist[MAX_N], cnt[MAX_N]; bool done[MAX_N]; long long answer = 0; vector<int> vec; struct edge { int to, nxt, weight; } edges[MAX_N << 1]; bool compare(int a, int b) { return dist[a] < dist[b]; } void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } // root finding functions; void dfs1(int u, int fa, int siz) { son[u] = 1; int res = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (edges[i].to == fa || done[edges[i].to]) continue; dfs1(edges[i].to, u, siz); son[u] += son[edges[i].to]; res = max(res, son[edges[i].to] - 1); } res = max(res, siz - son[u]); if (res < rootKey) root = u, rootKey = res; } void findRoot(int src, int siz) { root = src, rootKey = siz; dfs1(src, 0, siz); } // the calc one; void dfs(int u, int fa) { vec.push_back(u); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa && !done[edges[i].to]) { cnt[from[u]]++; dist[edges[i].to] = dist[u] + edges[i].weight; from[edges[i].to] = from[u]; dfs(edges[i].to, u); } } void pdq(int curt, int siz) { memset(son, 0, sizeof(son)); memset(cnt, 0, sizeof(cnt)); findRoot(curt, siz); dist[root] = 0, done[root] = true; vec.clear(), vec.push_back(root), from[root] = root; cnt[root]++; for (int i = head[root]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) { from[edges[i].to] = edges[i].to, cnt[edges[i].to]++; dist[edges[i].to] = edges[i].weight; dfs(edges[i].to, root); } sort(vec.begin(), vec.end(), compare); cnt[from[vec[0]]]--; int l = 0, r = vec.size() - 1; while (l < r) { while (dist[vec[l]] + dist[vec[r]] > k) cnt[from[vec[r--]]]--; answer += r - l - cnt[from[vec[l]]]; cnt[from[vec[++l]]]--; } int pos = root; for (int i = head[pos]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) pdq(edges[i].to, son[edges[i].to]); } int main() { while (scanf("%d%d", &n, &k) && n != 0) { answer = 0; memset(head, -1, sizeof(head)), current = 0; for (int i = 1; i <= n - 1; i++) scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz); memset(done, false, sizeof(done)); pdq(1, n); printf("%lld\n", answer); } return 0; }
首先选一个点作为根,把无根树变为有根树,然后递归进行分支(DFS-like)。但是,为了减小复杂度,我们希望在一棵树中递归层数控制到最小,那么这个点的选择就非常的重要。我们选择重心来搞定这个。有了重心,我们的子树大小都不会超过\(n/2\);计算完了之后,删掉根,并递归子树。所以时间复杂度是优秀的\(O(n\log n)\)。
重心的求法:我们用 \(O(n)\) 的时间来求出以每个点为根的子树大小,然后判断划分出联通块各点最少的点,那么这个点就是重心。
例题:IOI2011 Race,POJ1741:Tree 题解
思路:找到重心,则路径可以表示为经过根的两条子路径。第一遍 DFS 中记录走到每个点的距离和边数,同时统计到距离\(dist\)的最小边数\(sides[dist]\)。答案就是
\[ans=max\{sides[k-dist[i]]+sideSubtree[i]\}\]
一定要统计完答案之后再去用\(sideSubtree\)更新\(sides[]\)数组。
依旧需要找重心,但是在一些极限环境下(菊花图之类的)就会出锅,复杂度飙升。这个时候可以搞重构树来解决,把一颗菊花图搞成二叉树(建虚点,搞零边权的边)(目前还不怎么懂)
具体可以看这篇文章:https://ksmeow.moe/edge_based_divide_and_conquer/
例题:BZOJ2870
树链剖分是个好用的东西。我们可以第一遍 DFS 可以求出所有的重儿子,第二遍 DFS 的时候优先走重儿子,求时间戳。
对于重链的区间操作,直接暴力时间戳区间操作;对于轻边或混合链,LCA-like 算法可以搞定。
这个洛谷上题好多,不举例了。
CDQ 分治是一个神仙的离线算法。老师讲的太快,没看完就切掉了 PPT。
功能:对于所有的询问都进行二分来加速。
普通的分块最重要的一点就是确定区间长度。确定一个好的区间长度能让时间复杂度大大降低。一般我们使用\(\sqrt{n}\)来作为区间长度。用数组存好左右端点和每个点所属的区块,并预处理必要的信息。
这道题要求我们维护众数,我们可以先预处理每个两个区块间的众数,然后再每个数搞一个\(vector\)记录数出现的位置,对于暴力的区间,我们可以二分两次并相减得出出现次数。这样就可以解决问题了:
// CH4401.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 40100; vector<int> poses[MAX_N]; int arr[MAX_N], mapping[MAX_N], lft[MAX_N], tot, rig[MAX_N], cnt[MAX_N], mode[900][900], affiliate[MAX_N]; int find(int x, int l, int r) { return upper_bound(poses[x].begin(), poses[x].end(), r) - lower_bound(poses[x].begin(), poses[x].end(), l); } void judge(int x, int l, int r, int &ans, int &ct) { int w = find(x, l, r); if (w > ct || (w == ct && x < ans)) ct = w, ans = x; } int query(int l, int r) { int ans = 0, ct = 0; int p = affiliate[l], q = affiliate[r]; if (p == q) { for (int i = l; i <= r; i++) judge(arr[i], l, r, ans, ct); return mapping[ans]; } int x = 0, y = 0; if (p + 1 <= q - 1) x = p + 1, y = q - 1; for (int i = l; i <= rig[p]; i++) judge(arr[i], l, r, ans, ct); for (int i = lft[q]; i <= r; i++) judge(arr[i], l, r, ans, ct); if (mode[x][y]) judge(mode[x][y], l, r, ans, ct); return mapping[ans]; } int main() { int n, m, t, len; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &arr[i]), mapping[++tot] = arr[i]; sort(mapping + 1, mapping + 1 + n); tot = unique(mapping + 1, mapping + 1 + n) - (mapping + 1); for (int i = 1; i <= n; i++) arr[i] = lower_bound(mapping + 1, mapping + 1 + tot, arr[i]) - mapping, poses[arr[i]].push_back(i); t = sqrt(log(n) / log(2) * n); len = t ? n / t : n; for (int i = 1; i <= t; i++) lft[i] = (i - 1) * len + 1, rig[i] = i * len; if (rig[t] < n) lft[t + 1] = rig[t] + 1, rig[++t] = n; for (int i = 1; i <= t; i++) for (int j = lft[i]; j <= rig[i]; j++) affiliate[j] = i; memset(mode, 0, sizeof(mode)); for (int i = 1; i <= t; i++) { memset(cnt, 0, sizeof(cnt)); int ct = 0, ans = 0; for (int j = lft[i]; j <= n; j++) { if (++cnt[arr[j]] > ct || (cnt[arr[j]] == ct && arr[j] < ans)) ans = arr[j], ct = cnt[arr[j]]; mode[i][affiliate[j]] = ans; } } int last = 0; while (m--) { int l, r; scanf("%d%d", &l, &r), l = (l + last - 1) % n + 1, r = (r + last - 1) % n + 1; if (l > r) swap(l, r); last = query(l, r); printf("%d\n", last); } return 0; }
对于可以离线的问题,我们考虑询问进行分块。先对每一块内第一个问题进行暴力求解,然后块内的其他问答都用\(O(\sqrt{n})\)的时间搞定转移。非常好用。
例题:BZOJ2038: [2009国家集训队]小Z的袜子(hose)
显然,单纯计算区间内答案式子是:
\[\frac{ans}{{r-l+1 \choose 2}}, \text{其中ans是相同袜子的对数。}\]
对于每一个区块,我们可以维护一个\(num[]\)数组记录每一个颜色的出现次数,然后进行转移时对 ans 进行积累,更新询问答案即可。
// BZ2038.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const ll MAX_N = 50100; struct query { ll l, r, id, answerSon, answerDom; bool operator<(const query &qy) const { return id < qy.id; } } queries[MAX_N]; ll ci[MAX_N], n, m, len, btot, num[MAX_N], lft[MAX_N], rig[MAX_N], ans; bool compare_left(query a, query b) { return a.l < b.l || (a.l == b.l && a.r < b.r); } bool compare_right(query a, query b) { return a.r < b.r || (a.r == b.r && a.l < b.l); } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } void change(ll x, ll w) { ans -= num[x] * (num[x] - 1); num[x] += w; ans += num[x] * (num[x] - 1); } void simplify(ll id) { ll d = gcd(queries[id].answerSon, queries[id].answerDom); if (!d) queries[id].answerSon = 0, queries[id].answerDom = 1; else queries[id].answerSon /= d, queries[id].answerDom /= d; } int main() { scanf("%lld%lld", &n, &m); for (ll i = 1; i <= n; i++) scanf("%lld", &ci[i]); for (ll i = 1; i <= m; i++) scanf("%lld%lld", &queries[i].l, &queries[i].r), queries[i].id = i; len = sqrt(m), btot = m / len; sort(queries + 1, queries + 1 + m, compare_left); for (ll i = 1; i <= btot; i++) lft[i] = (i - 1) * len + 1, rig[i] = i * len; if (rig[btot] < m) lft[btot + 1] = rig[btot++] + 1, rig[btot] = m; for (ll i = 1; i <= btot; i++) { sort(queries + lft[i], queries + rig[i] + 1, compare_right); memset(num, 0, sizeof(num)); ans = 0; // previous interval; ll l = queries[lft[i]].l, r = queries[lft[i]].r; // process the first query; for (ll j = l; j <= r; j++) change(ci[j], 1); queries[lft[i]].answerSon = ans; queries[lft[i]].answerDom = (queries[lft[i]].r - queries[lft[i]].l + 1) * (queries[lft[i]].r - queries[lft[i]].l); simplify(lft[i]); for (ll j = lft[i] + 1; j <= rig[i]; j++) { while (l < queries[j].l) change(ci[l++], -1); while (l > queries[j].l) change(ci[--l], 1); while (r < queries[j].r) change(ci[++r], 1); while (r > queries[j].r) change(ci[r--], -1); if (queries[j].l == queries[j].r) queries[j].answerSon = 0, queries[j].answerDom = 1; else { queries[j].answerSon = ans, queries[j].answerDom = (r - l) * (r - l + 1); simplify(j); } } } sort(queries + 1, queries + 1 + m); for (ll i = 1; i <= m; i++) printf("%lld/%lld\n", queries[i].answerSon, queries[i].answerDom); return 0; }
把树上问题转换为序列问题,括号序列(欧拉序)可解。例题:SPOJ COT 2