还差一道题
bzoj4070
看错题*2- ---->暴力想不出来
其实我们发现由于每只doge只有在有信息的情况下才会走
那么也就是说每只doge只会连续地走一次 不可能信息传给别的doge之后再传回来 并且只会向一个方向跑 因为只跑一次 那么折返跑肯定是亏的
所以暴力连边就是狗所在的位置向狗连边，狗向能到的地方连边 然后跑最短路看能不能到就行了
由于每只狗能到的位置是n / p的 p大的时候还行 如果p很小的话那么就有n * n / p = n * n条边了
看见n / p那么就想到了平均一下 那么自然p就按sqrt(n)分类
如果p > sqrt(n)仍然暴力连边
p <= sqrt(n)的时候 我们想一共有sqrt(n)种p，如果每种p对应一种doge那么也就只有sqrt(n) * n / p = n*sqrt(n)种
可是每种p可能对应很多只doge
那么我们只要对每种p建边就行了
把每个点额外增加sqrt(n)个点
那么每个位置对应的点向相邻能到的位置对应的点连边
这样一共有n * sqrt(n) 个点 每个点对应两条边
那么也只有n * sqrt(n)条边
所以解决了
具体连边看代码
利用了两个思想 sqrt 分类和集约建边
#include<bits/stdc++.h> using namespace std; const int N = 3e4 + 5, M = 105, inf = 0x3f3f3f3f; struct edge { int nxt, to, w; } e[N * M * 5]; int n, m, edge = 1, cnt, s, t; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; int pos[N][M], h[N * M], d[N * M]; void link(int u, int v, int w) { e[++edge].nxt = h[u]; h[u] = edge; e[edge].to = v; e[edge].w = w; } int dijkstra() { memset(d, 0x3f3f, sizeof(d)); q.push(make_pair(0, s)); d[s] = 0; while(!q.empty()) { pair<int, int> o = q.top(); q.pop(); int u = o.second; if(d[u] < o.first) continue; for(int i = h[u]; i; i = e[i].nxt) { if(d[e[i].to] > d[u] + e[i].w) { d[e[i].to] = d[u] + e[i].w; q.push(make_pair(d[e[i].to], e[i].to)); } } } return d[t] == inf ? -1 : d[t]; } int main() { scanf("%d%d", &n, &m); int _ = min((int)sqrt(n), 100); cnt = n; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= _; ++j) { pos[i][j] = ++cnt; link(pos[i][j], i, 0); } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= _; ++j) { if(i > j) link(pos[i][j], pos[i - j][j], 1); if(i + j <= n) link(pos[i][j], pos[i + j][j], 1); } } for(int i = 1; i <= m; ++i) { int b, p; scanf("%d%d", &b, &p); ++b; if(i == 1) s = b; if(i == 2) t = b; if(p > _) { int nw = b - p, w = 1; while(nw > 0) { link(b, nw, w); nw -= p; ++w; } nw = b + p; w = 1; while(nw <= n) { link(b, nw, w); nw += p; ++w; } } else link(b, pos[b][p], 0); } printf("%d ", dijkstra()); return 0; }
bzoj4071
先开始以为k很大。。。
k = 1的时候是选中位数 具体忘了为什么 应该在数轴上画一下就行了 这应该是初中数学
k = 2的时候仍然可以沿用上面的思路 我们枚举分割点 由于每个人肯定对应一座桥 而且跟距离有关
那么桥对应人的区间应该是连续的一段 所以我们枚举分割点 分别计算两边的距离
但是按什么顺序排序
由于对于每个人自然是选择离中点最近的桥 那么我们以中点为标准可以分割左右区间 所以按中点排序就行了
然后就是分别求前缀后缀的中位数 上treap就行了
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int k, n, tot; long long d; long long dp[N], b[N]; struct Treap { int root, cnt; struct node { int ch[2]; int rnk; long long sz, w, v, sum; } t[N]; void upd(int x) { t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + t[x].w; t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].v * t[x].w; } void rotate(int &x, int w) { int y = t[x].ch[w]; t[x].ch[w] = t[y].ch[w ^ 1]; t[y].ch[w ^ 1] = x; upd(x); upd(y); x = y; } void insert(int &x, int v) { if(!x) { x = ++cnt; t[x].rnk = rand(); t[x].v = v; t[x].w = 1; upd(x); return; } if(v == t[x].v) { ++t[x].w; upd(x); return; } int w = v > t[x].v; insert(t[x].ch[w], v); if(t[t[x].ch[w]].rnk > t[x].rnk) { rotate(x, w); } upd(x); } void erase(int &x, int v) { if(t[x].v == v) { if(t[x].w > 1) { --t[x].w; upd(x); return; } if(!t[x].ch[0] && !t[x].ch[1]) { x = 0; return; } int w = t[t[x].ch[0]].rnk < t[t[x].ch[1]].rnk; rotate(x, w); erase(t[x].ch[w ^ 1], v); } else { erase(t[x].ch[v > t[x].v], v); } upd(x); } int query(int x, int k) { int d = t[t[x].ch[0]].sz + t[x].w; if(t[t[x].ch[0]].sz >= k) { return query(t[x].ch[0], k); } k -= d; if(k <= 0) { return t[x].v; } else { return query(t[x].ch[1], k); } } long long query_sum(int x, int v) { if(!x) { return 0; } if(v < t[x].v) { return query_sum(t[x].ch[0], v) + t[x].sum - t[t[x].ch[0]].sum - v * (t[x].sz - t[t[x].ch[0]].sz); } else if(v == t[x].v) { return t[t[x].ch[0]].sz * v - t[t[x].ch[0]].sum + t[t[x].ch[1]].sum - t[t[x].ch[1]].sz * v; } else { return v * (t[x].sz - t[t[x].ch[1]].sz) - t[x].sum + t[t[x].ch[1]].sum + query_sum(t[x].ch[1], v); } } } treap; struct data { int s, t; data() {} data(int _s, int _t) : s(_s), t(_t) {} bool friend operator < (const data &a, const data &b) { return a.s + a.t < b.s + b.t; } } a[N]; int main() { scanf("%d%d", &k, &n); for(int i = 1; i <= n; ++i) { char p[2], q[2]; int s, t; scanf("%s%d%s%d", &p, &s, &q, &t); if(p[0] == q[0]) { d += abs(s - t); } else { a[++tot] = data(s, t); ++d; } } if(k == 1) { n = 0; for(int i = 1; i <= tot; ++i) { b[++n] = a[i].s; b[++n] = a[i].t; } sort(b + 1, b + n + 1); int p = b[(n + 1) >> 1]; for(int i = 1; i <= tot; ++i) { d += abs(p - a[i].s) + abs(p - a[i].t); } printf("%lld ", d); return 0; } sort(a + 1, a + tot + 1); for(int i = 1; i <= tot; ++i) { treap.insert(treap.root, a[i].s); treap.insert(treap.root, a[i].t); int p = treap.query(treap.root, (i << 1 | 1) >> 1); dp[i] = treap.query_sum(treap.root, p); } long long ans = dp[tot]; for(int i = 1; i <= tot; ++i) { long long tmp = treap.query_sum(treap.root, treap.query(treap.root, tot - i + 1)); treap.erase(treap.root, a[i].s); treap.erase(treap.root, a[i].t); ans = min(ans, tmp + dp[i - 1]); } printf("%lld ", ans + d); return 0; }