A – Tree
这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。
Continue reading →这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。
Continue reading →做一个容斥即可,答案等于:
\[ f_0 – f_1 + f_2 – f_3 \]
其中 \(f_i\) 代表环上至少有 \(i\) 对矛盾。计算方式如下:
节点内子树的值都比本身要小(堆的性质),且整个子树在序列上是一段连续的子串。
HDU-1506 单调栈的裸题。
// HDU-1506.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 1e5 + 200; struct node { int ch[2], idx, fa, val; void clear() { ch[0] = ch[1] = idx = fa = val = 0; } } nodes[MAX_N]; int n, stk[MAX_N << 1], top; ll ans; int build() { for (int i = 1; i <= n; i++) { int k = i - 1; while (nodes[k].val > nodes[i].val) k = nodes[k].fa; nodes[i].ch[0] = nodes[k].ch[1]; nodes[k].ch[1] = i; nodes[i].fa = k, nodes[nodes[i].ch[0]].fa = i; } return nodes[0].ch[1]; } int dfs(int u) { if (u == 0) return 0; int siz = 1; for (int bit = 0; bit < 2; bit++) siz += dfs(nodes[u].ch[bit]); ans = max(ans, 1LL * siz * nodes[u].val); return siz; } int main() { while (scanf("%d", &n) && n != 0) { ans = 0; nodes[0].ch[0] = nodes[0].ch[1] = nodes[0].idx = nodes[0].fa = nodes[0].val = 0; for (int i = 1; i <= n; i++) { scanf("%d", &nodes[i].val), nodes[i].idx = i, nodes[i].fa = 0; memset(nodes[i].ch, 0, sizeof(nodes[i].ch)); } dfs(build()); printf("%lld\n", ans); } return 0; }
首先仔细剖析出题目意思:我们要规定一个路径,要被经过\(k\),然后再到路径的两头延伸出不大于 \(k\) 的分支,且每个分支独占一颗子树,求方案数。
那么我们可以先把 \(1\) 定为根,然后算出以点 \(u\) 为端点、分支在子树内的方案数 \(f_u\),然后再算向父亲侧的方案数 \(g_u\),再枚举 \((u, v)\):
首先知道:
\[E_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2} – \sum_{j = i + 1}^{n}\frac{q_j}{(i – j)^2} \]
现在要求所有的。我们可以考虑分成前后两个部分分别计算。先考虑前面的部分:
\[a_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2}\]
我们发现这一部分还是很好计算的:当多项式指数为\(i\)时,对应\(a_i\),发现\(q_j\)和\((i – j)^2\)的下标相加恰好为\(i\)。正好是卷积的形式。后面那一个部分也可以直接这样算。
最近都在学些科技,做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。
首先,我们先考虑奇数长度段的情况(\(\{a_n\}\)已经排序):确定中位数为\(a_{mid}\),则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和,并除以元素个数。欲使价值最大,那么显然右侧需要靠近右端点进行选择, 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化:简化对长度的枚举复杂度。