[LibreOJ 2249][NOI2014]购票
在紧张刺激的等待之后终于肝掉了这道题……
本题的DP方程长成这样(其中\(a\)指\(v\)的某个满足距离限制的祖先,\(d_v\)指\(v\)到根的路径长):
\[f_v = min(f_a + p_v(d_v - d_a) + q_v)\]
化简之后发现:
\[f_v = q_v + p_v d_v + min(f_a - p_v d_a)\]
利用\(min\)中那一块很容易发现是截距式……但是问题在于,我们的转移来源是树上的连续一段祖先,怎样维护他们的凸包?
答案很狂暴啊……用树链剖分套上向量集那题的线段树套凸包,然后完了……
(注意一点细节:本题因为数据范围过大,故可能存在两个向量叉乘爆long long,所以在求凸包时如果直接用叉积判断是否需要删点会炸掉,建议用斜率判断)
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <utility> #include <vector> #include <queue> #include <deque> #include <cmath> #include <set> #include <climits> using ll = long long; using T = ll; using R = long double; const R eps = 1e-8; int sign(R x) { if(fabsl(x) < eps) { return 0; } else { if(x > (R(0.00))) { return 1; } else { return -1; } } } struct Point { T x, y; Point(T qx = 0LL, T qy = 0LL) { x = qx; y = qy; } }; using Vector = Point; Vector operator +(const Vector &a, const Vector &b) { return Vector(a.x + b.x, a.y + b.y); } Vector operator -(const Point &a, const Point &b) { return Vector(a.x - b.x, a.y - b.y); } Vector operator *(const Vector &a, T lam) { return Vector(a.x * lam, a.y * lam); } Vector operator *(T lam, const Vector &a) { return Vector(a.x * lam, a.y * lam); } inline T dot(const Vector &a, const Vector &b) { return (a.x * b.x + a.y * b.y); } inline T times(const Vector &a, const Vector &b) { return (a.x * b.y - a.y * b.x); } inline bool cmp(const Point &a, const Point &b) { if(a.x == b.x) { return a.y < b.y; } else { return a.x < b.x; } } inline R slope(const Vector &a) { R dx = a.x, dy = a.y; return (dy / dx); } inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) { std::sort(P + 1, P + 1 + L, cmp); for(int i = 1; i <= L; i ++) { if(i != 1 && (P[i].x == P[i - 1].x)) continue; while(bot.size() > 1 && sign(slope(P[i] - bot.back()) - slope(bot.back() - bot[bot.size() - 2])) <= 0) { bot.pop_back(); } bot.push_back(P[i]); } for(int i = L; i >= 1; i --) { if(i != L && (P[i].x == P[i + 1].x)) continue; while(top.size() > 1 && sign(slope(P[i] - top.back()) - slope(top.back() - top[top.size() - 2])) <= 0) { top.pop_back(); } top.push_back(P[i]); } std::reverse(top.begin(), top.end()); } const int maxn = 200005; const int maxno = maxn << 2; const int N = 200000; bool zen[maxno]; std::vector<Point> bot[maxno], top[maxno]; Point P[maxn]; inline void maintain(int o, int L, int R) { static Point tmp[maxn]; const int lc = o << 1, rc = o << 1 | 1; const bool used = zen[o]; zen[o] = (zen[lc] && zen[rc]); if(zen[o] != used) { std::copy(P + L, P + R + 1, tmp + 1); int len = R - L + 1; andrew(tmp, len, bot[o], top[o]); } } void modify(int o, int L, int R, const int &p, const Point &v) { if(L == R) { zen[o] = true; P[L] = v; bot[o].push_back(v); top[o].push_back(v); } else { const int M = (L + R) / 2; if(p <= M) { modify(o << 1, L, M, p, v); } else { modify(o << 1 | 1, M + 1, R, p, v); } maintain(o, L, R); } } inline T calc_ans(T k, const Point &v) { return v.y - k * v.x; } inline T search(const std::vector<Point> &vec, const T &k) { int l = 0, r = vec.size() - 1; while(r - l > 2) { int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3; if((calc_ans(k, vec[lm]) > calc_ans(k, vec[rm]))) { l = lm; } else { r = rm; } } T ans = LLONG_MAX; for(int i = l; i <= r; i ++) { ans = std::min(ans, calc_ans(k, vec[i])); } return ans; } T query(int o, int L, int R, const int &ql, const int &qr, const T &k) { if(ql <= L && R <= qr) { return search(bot[o], k); } else { int M = (L + R) / 2; T ans = LLONG_MAX; if(ql <= M) { ans = std::min(ans, query(o << 1, L, M, ql, qr, k)); } if(qr > M) { ans = std::min(ans, query(o << 1 | 1, M + 1, R, ql, qr, k)); } return ans; } } int first[maxn]; int next[maxn << 1], to[maxn << 1]; ll dist[maxn << 1]; void add_edge(int u, int v, ll d) { static int cnt = 0; cnt ++; next[cnt] = first[u]; first[u] = cnt; to[cnt] = v; dist[cnt] = d; } int fa[maxn], dep[maxn], hson[maxn]; ll d[maxn]; int siz[maxn]; int bs[maxn][18]; void dfs_1(int x, int f = -1, int depth = 1) { fa[x] = bs[x][0] = f; dep[x] = depth; siz[x] = 1; int max_siz = 0; for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(v != f) { d[v] = d[x] + dist[i]; dfs_1(v, x, depth + 1); siz[x] += siz[v]; if(siz[v] > max_siz) { hson[x] = v; max_siz = siz[v]; } } } } int dfn[maxn], tid[maxn], up[maxn]; void dfs_2(int x, int a = 1, int f = 0) { static int cnt = 0; dfn[x] = ++ cnt; tid[cnt] = x; up[x] = a; if(hson[x]) { dfs_2(hson[x], a, x); } else { return; } for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(v != f && v != hson[x]) { dfs_2(v, v, x); } } } int k_anc(int x, ll k) { int yx = x; for(int j = 17; j >= 0; j --) { int a = bs[x][j]; if(a != -1 && d[yx] - d[a] <= k) { x = a; } } #ifdef LOCAL printf("%d's %lld-th anc : %d\n", yx, k, x); #endif return x; } int n; ll get_up(int x, int anc, ll k) { ll ans = LLONG_MAX; while(up[x] != up[anc]) { ans = std::min(ans, query(1, 1, n, dfn[up[x]], dfn[x], k)); x = fa[up[x]]; } return std::min(ans, query(1, 1, n, dfn[anc], dfn[x], k)); } ll p[maxn], q[maxn], l[maxn]; ll f[maxn]; void dp(int x) { #ifdef LOCAL printf("processing %d...\n", x); printf("d : %lld\n", d[x]); #endif if(x != 1) { #ifdef LOCAL printf("b : %lld\n", get_up(fa[x], k_anc(x, l[x]), p[x])); #endif f[x] = get_up(fa[x], k_anc(x, l[x]), p[x]) + d[x] * p[x] + q[x]; } else { f[x] = 0; } #ifdef LOCAL printf("ans : %lld\n", f[x]); #endif modify(1, 1, n, dfn[x], Point(d[x], f[x])); for(int i = first[x]; i; i = next[i]) { int v = to[i]; dp(v); } } int main() { int t; scanf("%d%d", &n, &t); for(int i = 2; i <= n; i ++) { int father; T s; scanf("%d%lld%lld%lld%lld", &father, &s, &p[i], &q[i], &l[i]); add_edge(father, i, s); } memset(bs, -1, sizeof(bs)); dfs_1(1); dfs_2(1); for(int j = 1; (1 << j) < n; j ++) { for(int i = 1; i <= n; i ++) { int a = bs[i][j - 1]; if(a != -1) { bs[i][j] = bs[a][j - 1]; } } } dp(1); for(int i = 2; i <= n; i ++) { printf("%lld\n", f[i]); } return 0; }
[LibreOJ 2353][NOI2007]货币兑换
emmm做了一下这道神题……(我可能是少有的用动态凸包苟的?)
首先DP方程长这样:
\[f_i = max(f_{i - 1}, f_j\cdot\frac{A_iR_j+B_i}{A_jR_j+B_j})\]
然后这个方程炒鸡复杂……首先\(f_{i - 1}\)不要管了,然后设\(a_i = \frac{f_i}{A_iR_i + B_i}\)。在xjb推了一番之后我们终于得到了截距式……
\[-a_j R_j \frac{A_i}{B_i} + \frac{f_i}{B_i} = a_j\]
但是这玩意太毒瘤了……斜率不可能单调的,这还好,在凸壳上二分/三分一下即可。但问题在于,横坐标也不单调……
这个时候就需要动态维护凸包了(其实是我不会CDQ),我直接把我向量集那题的二进制分组线段树搬了过来……(逃
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <utility> #include <vector> #include <cmath> #include <climits> #include <deque> #include <cassert> using R = double; const R eps = 1e-8; int sign(R x) { if(fabs(x) < eps) { return 0; } else { if(x > 0.00) { return 1; } else { return -1; } } } struct Point { R x, y; Point(R qx = 0, R qy = 0) { x = qx; y = qy; } }; using Vector = Point; Vector operator +(const Vector &a, const Vector &b) { return Vector(a.x + b.x, a.y + b.y); } Vector operator -(const Point &a, const Point &b) { return Vector(b.x - a.x, b.y - a.y); } Vector operator *(const Vector &a, R lam) { return Vector(a.x * lam, a.y * lam); } Vector operator *(R lam, const Vector &a) { return Vector(a.x * lam, a.y * lam); } inline R dot(const Vector &a, const Vector &b) { return (a.x * b.x + a.y * b.y); } inline R times(const Vector &a, const Vector &b) { return (a.x * b.y - a.y * b.x); } inline bool cmp(const Point &a, const Point &b) { if(sign(a.x - b.x) == 0) { return a.y < b.y; } else { return a.x < b.x; } } inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) { std::sort(P + 1, P + 1 + L, cmp); for(int i = 1; i <= L; i ++) { if(i != 1 && sign(P[i].x - P[i - 1].x) == 0) continue; while(bot.size() > 1 && sign(times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0) { bot.pop_back(); } bot.push_back(P[i]); } for(int i = L; i >= 1; i --) { if(i != L && sign(P[i].x - P[i + 1].x) == 0) continue; while(top.size() > 1 && sign(times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0) { top.pop_back(); } top.push_back(P[i]); } std::reverse(top.begin(), top.end()); } const int maxn = 1000005; const int N = 1000000; const int maxno = maxn << 2; bool zen[maxno]; std::vector<Point> bot[maxno], top[maxno]; Point P[maxn]; inline void maintain(int o, int L, int R) { static Point tmp[maxn]; const int lc = o << 1, rc = o << 1 | 1; const bool used = zen[o]; zen[o] = (zen[lc] && zen[rc]); if(zen[o] != used) { std::copy(P + L, P + R + 1, tmp + 1); int len = R - L + 1; andrew(tmp, len, bot[o], top[o]); } } void modify(int o, int L, int R, const int &p, const Point &v) { if(L == R) { zen[o] = true; P[L] = v; bot[o].push_back(v); top[o].push_back(v); } else { const int M = (L + R) / 2; if(p <= M) { modify(o << 1, L, M, p, v); } else { modify(o << 1 | 1, M + 1, R, p, v); } maintain(o, L, R); } } inline R calc_ans(R k, const Point &v) { return v.y - k * v.x; } inline R search(const std::vector<Point> &vec, const R &k) { int l = 0, r = vec.size() - 1; while(r - l > 2) { int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3; if(sign(calc_ans(k, vec[lm]) - calc_ans(k, vec[rm])) == 1) { r = rm; } else { l = lm; } } R ans = INT_MIN; for(int i = l; i <= r; i ++) { ans = std::max(ans, calc_ans(k, vec[i])); } return ans; } R query(int o, int L, int R, const int &ql, const int &qr, const double &k) { if(ql <= L && R <= qr) { return search(top[o], k); } else { int M = (L + R) / 2; double ans = INT_MIN; if(ql <= M) { ans = std::max(ans, query(o << 1, L, M, ql, qr, k)); } if(qr > M) { ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, k)); } return ans; } } int n, s; R A[maxn], B[maxn], Rate[maxn]; R f[maxn]; R dp() { static double a[maxn]; f[0] = s; f[1] = s; a[1] = f[1] / (A[1] * Rate[1] + B[1]); modify(1, 1, n, 1, Point(a[1] * Rate[1], a[1])); for(int i = 2; i <= n; i ++) { f[i] = query(1, 1, n, 1, i - 1, -A[i] / B[i]) * B[i]; f[i] = std::max(f[i], f[i - 1]); a[i] = f[i] / (A[i] * Rate[i] + B[i]); if(i < n) modify(1, 1, n, i, Point(a[i] * Rate[i], a[i])); } return f[n]; } int main() { scanf("%d%d", &n, &s); for(int i = 1; i <= n; i ++) { scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]); } printf("%.3lf\n", dp()); return 0; }
[BZOJ 1061][NOI2008]志愿者招募
膜了一发BYVoid的题解……竟然搞懂了
这首先是个非常简单的线性规划,就是有若干限制(每天要求的志愿者),形如:
\[P_i = X_a + X_b +\ldots + X_c\geq A_i\]
(这里用\(X_i\)表示第\(i\)类志愿者雇佣了多少个,\(P_i\)表示第\(i\)天的志愿者总数,\(A_i\)同原题面)
且最小化总费用。
既然我们我知道\(P_i\geq A_i\),那么说明\(P_i\)一定可以表示为\(A_i + Y_i\)(\(Y_i\geq 0\))。然后这样限制就变成了:
\[P_i = X_a + X_b +\ldots + X_c + Y_i = A_i\]
这个长得很像可以流量平衡的样子,但是流量的变动是表示不了的……
然后假设\(P_0 = 0\)且\(P_{n + 1} = 0\),这样就可以对限制差分一下,我们就有了\(n + 1\)个限制,然后这个式子就可以流量平衡做了(因为不考虑常数项的话,同一变量只可能在两个限制中出现,并且一正一负,这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项,通过源或者汇连边即可表达)。
然后由于志愿者无限,所以这个东西也一定有解……
我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解,比我透彻多了。
代码:
/************************************************************** Problem: 1061 User: danihao123 Language: C++ Result: Accepted Time:3164 ms Memory:6824 kb ****************************************************************/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <utility> #include <algorithm> #include <queue> #include <cassert> typedef long long ll; int m, n; const int maxno = 100005; const int maxe = 100005; int first[maxno]; int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe]; ll cost[maxe]; int gcnt = 0; void add_edge(int u, int v, ll f, ll c) { gcnt ++; next[gcnt] = first[u]; first[u] = gcnt; from[gcnt] = u; to[gcnt] = v; cap[gcnt] = f; flow[gcnt] = 0; cost[gcnt] = c; } int rev(int i) { return ((i - 1) ^ 1) + 1; } int ins_edge(int u, int v, ll f, ll c = 0LL) { #ifdef LOCAL printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c); #endif add_edge(u, v, f, c); add_edge(v, u, 0, -c); return gcnt - 1; } const ll LINF = 0x7f7f7f7f7f7f7f7fLL; int tot; bool spfa(int s, int t, ll &f, ll &c) { static ll d[maxno]; static bool inq[maxno]; static ll a[maxno]; static int p[maxno]; std::fill(d, d + tot + 1, LINF); std::fill(inq, inq + tot + 1, false); std::fill(a, a + tot + 1, 0LL); std::fill(p, p + tot + 1, 0); d[s] = 0; std::queue<int> Q; Q.push(s); inq[s] = true; a[s] = LINF; while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = first[u]; i; i = next[i]) { if(cap[i] > flow[i]) { int v = to[i]; if(d[v] > d[u] + cost[i]) { d[v] = d[u] + cost[i]; a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i; if(!inq[v]) { Q.push(v); inq[v] = true; } } } } } if(a[t] == 0LL) return false; f += a[t]; c += a[t] * d[t]; for(int e = p[t]; e; e = p[from[e]]) { flow[e] += a[t]; flow[rev(e)] -= a[t]; } return true; } void mcmf(int s, int t, ll &f, ll &c) { while(spfa(s, t, f, c)); } const int maxn = 1005, maxm = 10005; int E[maxn]; int A[maxn], D[maxn]; int main() { scanf("%d%d", &n, &m); int s = 0, t = n + 2; tot = n + 2; for(int i = 1; i <= n; i ++) scanf("%d", &A[i]); for(int i = 1; i <= n + 1; i ++) { D[i] = A[i] - A[i - 1]; if(D[i] >= 0) { E[i] = ins_edge(s, i, D[i]); } else { E[i] = ins_edge(i, t, -D[i]); } } for(int i = 1; i <= n; i ++) { ins_edge(i + 1, i, LINF); } while(m --) { int S, T, C; scanf("%d%d%d", &S, &T, &C); ins_edge(S, T + 1, LINF, C); } ll f = 0, c = 0; mcmf(s, t, f, c); printf("%lld\n", c); return 0; }
[BZOJ 2876][NOI2012]骑行川藏
我终于A了……不就是拉格朗日乘数法的模板题吗
首先这道题最优情况下一定有(这里用\(E_i\)表示第\(i\)段路程的耗能):\(\sum_{i = 1}^n E_i = E_u\)。
然后这个东西是一个等式限制条件,然后我们还要最小化总用时,给人拉格朗日乘数法的即视感……
不管怎么说让我们来列式子吧:
\[h(x_1, x_2,\ldots ,x_n, \lambda) = \sum_{i = 1}^n \frac{s_i}{x_i} + \lambda \sum_{i = 1}^n k_i s_i (x_i - v_i)^2\]
\[\frac{\partial h}{\partial x_i} = -\frac{s_i}{x_i^2} + 2\lambda k_i s_i (x_i - v_i)\]
然后你会想这TM怎么解方程……
但是我们想一想,把\(\frac{\partial h}{\partial x_i} = 0\)稍作整理,得:
\[\frac{1}{2k_i\lambda} = x_i^2 (x_i - v_i)\]
对于式子的左边,是一个关于\(x_i\)的增函数(因为这道题默认了\(x_i\geq 0\)且\(x_i\geq v_i\)),然后不妨令\(\frac{1}{\lambda} = u\),可以发现\(u\)越大则\(x_i\)越大!这样一来那么我们的限制条件就会更加难以满足。
所以我们可以二分这个\(u\)来解这些方程。
BTW,这题卡精度非常厉害……
代码:
/************************************************************** Problem: 2876 User: danihao123 Language: C++ Result: Accepted Time:3960 ms Memory:1524 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <cmath> #include <iostream> #include <cassert> typedef double R; const R eps = 1e-12; const int maxn = 10005; int sign(R x) { if(fabs(x) < eps) { return 0; } else { if(x < 0) { return -1; } else { return 1; } } } R s[maxn], k[maxn], V[maxn]; R rf(int i, R v, R delta) { return v * v * (v - V[i]) - delta; } R rf2(int i, R v) { return 3 * v * v - 2 * v * V[i]; } R gen_rt(int i, R delta) { R x = 1e6; int lambda = 100; while(lambda --) { R a = rf(i, x, delta); if(sign(a) == 0) break; R da = rf2(i, x); x -= a / da; } return x; } int n; R E; R gen_lft() { R l = 1e-14, r = 1e16; while(r - l > eps) { #ifdef LOCAL printf("State [%.18lf, %.18lf]\n", l, r); #endif R M = (l + r) / 2; R T = 0; for(int i = 1; i <= n; i ++) { R v = gen_rt(i, M / (2 * k[i])); T += (v - V[i]) * (v - V[i]) * k[i] * s[i]; } if(sign(T - E) <= 0) { l = M; } else { r = M; } } return l; } int main() { std::cin >> n >> E; for(int i = 1; i <= n; i ++) { std::cin >> s[i] >> k[i] >> V[i]; } R M = gen_lft(); R tm = 0; for(int i = 1; i <= n; i ++) { R v = gen_rt(i, M / (2 * k[i])); tm += s[i] / v; } printf("%.8lf\n", tm); return 0; }
[BZOJ 4195]程序自动分析
看起来是道并查集水题……
可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?
注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!
这种技术,就是离散化
同时注意防卡常!
代码:
[BZOJ 4196]软件包管理器
终于A了!
在CodeVS,洛谷甚至UOJ上各种A
但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?
这题处理安装很简单,一直溯到根。
删除……注意一下树剖的一些神奇性质。