[LibreOJ 2135][ZJOI2015]幻想乡战略游戏

竟然1A了蛤蛤蛤蛤蛤

这题用人话说就是给你一个不会动的树,让你求带权重心。

先解决一个问题:如果要求动态修改点权,并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\),怎么做?

很显然对于一个点\(x\),对它造成贡献的点,可能是在以\(x\)为根的点分子树里的,也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献,必须要经过\(x\)在分治树上的祖先。

所以我们可以考虑对每个重心,记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑,那考虑一下其分治树上祖先对\(x\)的贡献就行了。

那带权重心怎么求呢?如果我们把树的根变成带权重心,那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走,那么最后一定会走到带权重心上。

我们考虑把这个过程放点分树上。从整棵树的重心开始往下走,每次如果发现有一条出边指向的点答案更好,那就往这个子结构(不是指向的点而是那个联通块的重心,否则时间复杂度不对)里走。最后走不动了,走到的点就是带权重心了。

求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法,但是跑的贼快(可能和树剖常数小有关?)。

吐槽一点,原题提到了每个点的度数不超过20,但是网上几乎所有OJ上该题的题面都没提到这一点……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
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 n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  dis[x] = d;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1, d + dist[i]);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
ll calc_dist(int x, int y) {
  int l = lca(x, y);
  return dis[x] + dis[y] - 2LL * dis[l];
}

bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
  bool flag = (siz[x] * 2 >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      flag = (flag && (siz[v] * 2 <= siz[nrt]));
      gen_rt(v, x);
    }
  }
  if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
  V -> push(x);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      search_p(v, V, x);
    }
  }
}
*/
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      int ch = divide(v);
      point2[i] = ch;
      cfa[ch] = x;
    }
  }
  return x;
}
void update(int x, ll delta) {
  int p = x;
  while(p) {
    pans[p] += delta * calc_dist(p, x);
    if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
    sumv[p] += delta;
    p = cfa[p];
  }
}
ll get_ans(int x) {
  ll ans = pans[x];
  int p = x;
  while(p != crt) {
    int f = cfa[p];
    ans += pans[f] - give[p];
    ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
    p = cfa[p];
  }
  return ans;
}
ll get_best() {
  int p = crt;
  std::stack<int> S;
  ll now_ans;
  while(true) {
    S.push(p); vis[p] = true;
    bool fix = true;
    now_ans = get_ans(p);
    for(int i = first[p]; i; i = next[i]) {
      int v = to[i];
      if(vis[v]) continue;
      if(get_ans(v) < now_ans) {
        fix = false;
        p = point2[i];
        break;
      }
    }
    if(fix) break;
  }
  while(!S.empty()) {
    int u = S.top(); S.pop();
    vis[u] = false;
  }
  return now_ans;
}

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
    add_edge(u, v, d); add_edge(v, u, d);
  }
  dfs_1(1); dfs_2(1);
  crt = divide(1); memset(vis, 0, sizeof(vis));
  while(q --) {
    int u, e; scanf("%d%d", &u, &e);
    update(u, e);
    printf("%lld\n", get_best());
  }
  return 0;
}

[LibreOJ 6238][Baltic2015]Network

LibreOJ真是好用(以后尽可能少用BZOJ)

这题我觉得真是个意识流神题。

考虑所有度数为1的点(姑且称为叶子),这些点是一定要向外连边的(只要有一个度数为1的树边不在一个环中,肯定就出桥了)。

那是否可以只在这种叶子之间连边?答案是肯定的。假设叶子上形成了足够多的环,那么上面的边可以随便上。

那是否叶子配对连边就行了(这说明答案是\(\lceil \frac{l}{2}\rceil\),其中\(l\)是叶子的数目)?答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。

然后就有一种乱搞做法:找到一个根使得每个子树的叶子数都不超过总数的一半(这种点很显然存在),然后从这个根开始DFS,把所有叶子按照DFS序排序一遍,前一半向后一半依次连边。如果叶子数目是奇数,那么最后一个可以随便连。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];

int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
  if(int(G[x].size()) == 1) {
    leaves[x] = 1; L.push_back(x);
    leavenum ++;
  }
  for(auto v : G[x]) {
    if(v != fa) {
      calc_leave(v, x);
      leaves[x] += leaves[v];
    }
  }
}
int gen_rt(int x, int fa = 0) {
  for(auto v : G[x]) {
    if(v != fa && leaves[v] * 2 >= leavenum) {
      return gen_rt(v, x);
    }
  }
  return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
  static int cnt = 0;
  dfn[x] = ++ cnt;
  for(auto v : G[x]) {
    if(v != fa) {
      calc_dfn(v, x);
    }
  }
}

bool cmp(const int &x, const int &y) {
  return dfn[x] < dfn[y];
}
int main() {
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  calc_leave(1);
  int rt = gen_rt(1);
  calc_dfn(rt);
  sort(L.begin(), L.end(), cmp);
  printf("%d\n", (leavenum + 1) / 2);
  int half = leavenum / 2;
  for(int i = 0; i < half; i ++) {
    printf("%d %d\n", L[i], L[i + half]);
  }
  if(1 & leavenum) {
    printf("%d %d\n", L[half - 1], L[leavenum - 1]);
  }
  return 0;
}

[BZOJ 3925][ZJOI2015]地震后的幻想乡

赛艇,赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子:
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集(我们不妨假设是从点1开始扩展)\(S\),式子可以这么写(这里不妨用\(T\)来表示两个点集间的边的数目):
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\),但这玩咋求……
然后我们定义一个状态\(d\):
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开,整理一下,得到:
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}p_{S_0, T(S, S - S_0) + k}\,\mathrm{d}x
\end{aligned}
\]
里面有两大块定积分,前一块还看起来蛮好求的,但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\)吗?
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)(这里不妨假设S为全集):
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗?
至于边界处理,\(d_{\{1\}, x}\)全部搞成0就行。
代码:
/**************************************************************
    Problem: 3925
    User: danihao123
    Language: C++
    Result: Accepted
    Time:100 ms
    Memory:1272 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
 
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
  if(s == 1) return 0;
  if(vis[s][k]) return d[s][k];
  d[s][k] = 0;
  int lit_s = s >> 1;
  for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
    int s0 = lit_s0 * 2 + 1;
    int t = 0;
    for(int i = 1; i <= m; i ++) {
      int u = edge[i][0], v = edge[i][1];
      if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
      if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
        t ++;
      }
    }
    int z = k + t;
    d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
    if(s0 == 1) break;
  }
  vis[s][k] = true;
  return d[s][k];
}
 
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v); u --, v --;
    edge[i][0] = u, edge[i][1] = v;
  }
  printf("%.6lf\n", f((1 << n) - 1, 0));
  return 0;
}

 

[BZOJ 1095][ZJOI2007]Hide 捉迷藏

蛤蛤蛤我这题终于调出来了~(然后1A了)

点分树处女作。其实点分树的思想并不难理解,就是把点分的过程抽象化到一棵树上。

其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。

代码(其中有海量本来拿来调试的代码,慎读):

/**************************************************************
    Problem: 1095
    User: danihao123
    Language: C++
    Result: Accepted
    Time:15268 ms
    Memory:128944 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
void add_edge(int u, int v) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
}
 
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
void dfs_1(int x, int father = 0, int depth = 1) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
 
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int fa = 0) {
  bool ok = (2 * siz[x] >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      ok = ok && (2 * siz[v] <= siz[nrt]);
      gen_rt(v, x);
    }
  }
  if(ok) rt = x;
}
int crt;
int cfa[maxn];
typedef std::priority_queue<int> heap;
struct dheap {
  heap Q, D;
  void push(int x) {
    Q.push(x);
  }
  void pop() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    Q.pop();
  }
  int top() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    return Q.top();
  }
  void del(int x) {
    D.push(x);
  }
  size_t size() {
    return Q.size() - D.size();
  }
  int sec() {
    int fir = top(); pop();
    int ret = top(); push(fir);
    return ret;
  }
};
dheap all;
dheap Q[maxn], sg[maxn];
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      cfa[divide(v)] = x;
    }
  }
  return x;
}
int n;
int get_ans(dheap &q) {
  return q.top() + q.sec();
}
bool sta[maxn];
int dist(int x, int y) {
  int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)];
#ifdef DEBUG
  printf("dist(%d, %d) : %d\n", x, y, ret);
#endif
  return ret;
}
void light_on(int p) {
  sta[p] = true;
  int x = p;
  int og = -1, ng = 0;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) {
      old_ans = get_ans(Q[x]);
    }
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].push(dist(p, cfa[x]));
      ng = sg[x].top();
    }
    x = cfa[x];
  }
}
void light_off(int p) {
  sta[p] = false;
  int x = p;
  int og = 0, ng = -1;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) old_ans = get_ans(Q[x]);
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
#ifdef DEBUG
    printf("%d deleting %d\n", x, og);
#endif
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
#ifdef DEBUG
    int tmp = -1;
    if(Q[x].size() > 1) tmp = get_ans(Q[x]);
    printf("ans of %d : %d -> %d\n", x, old_ans, tmp);
#endif
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].del(dist(p, cfa[x]));
      if(sg[x].size() > 0) {
        ng = sg[x].top();
      } else {
        ng = -1;
      }
    }
    x = cfa[x];
  }
}
void print_dheap(dheap &q) {
  std::vector<int> V;
  while(q.size() > 0) {
    int t = q.top(); q.pop();
    printf("%d ", t);
    V.push_back(t);
  }
  puts("");
  for(int i = 0; i < V.size(); i ++) {
    q.push(V[i]);
  }
}
 
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    add_edge(u, v); add_edge(v, u);
  }
  dfs_1(1); dfs_2(1);
#ifdef DEBUG
  for(int i = 1; i <= n; i ++) {
    printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]);
  }
#endif 
  crt = divide(1);
#ifdef DEBUG
  printf("crt id %d\n", crt);
  for(int i = 1; i <= n; i ++) {
    printf("cfa[%d] : %d\n", i, cfa[i]);
  }
#endif
  int num = 0;
  for(int i = 1; i <= n; i ++) {
    light_on(i); num ++;
#ifdef DEBUG
    printf("heap while inserting %d : ", i);
    print_dheap(all);
#endif
  }
  int q; scanf("%d", &q);
  while(q --) {
    char op[3]; scanf("%s", op);
    if(op[0] == 'G') {
      if(num == 0) {
        puts("-1");
      } else if(num == 1) {
        puts("0");
      } else {
        printf("%d\n", all.top());
      }
    } else {
      int i; scanf("%d", &i);
      if(sta[i]) {
        light_off(i);
        num --;
      } else {
        light_on(i);
        num ++;
      }
    }
#ifdef DEBUG
    print_dheap(all);
#endif
  }
  return 0;
}

[BZOJ 3295][CQOI2011]动态逆序对

又一道坑了很久没有写题解的……

删除操作特别的棘手,但好在我们可以离线~时光倒流之后,删除就变成了添加。

每个点加进来之后,对答案的贡献可以分为两部分:

  1. 加入比他早,位置在他前面,值比他大的点。
  2. 加入比他早,位置在他后面,值比他小的点。

然后两者都可以用CDQ统计(我还偷懒用同一个CDQ做的)

代码:

/**************************************************************
    Problem: 3295
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2332 ms
    Memory:5768 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
    int id;
    int p, v;
};
 
int n;
ll C[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int p, int v) {
    while(p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}
ll sum(int p) {
    ll ret = 0;
    while(p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}
int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
void clean(int p) {
    while(p <= n && C[p] != 0) {
        C[p] = 0;
        p += lowbit(p);
    }
}
 
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
    if(L == R) {
        return;
    }
    int M = L + (R - L) / 2;
    CDQ(L, M, flag); CDQ(M + 1, R, flag);
    for(int p = L, l = L, r = M + 1; p <= R; p ++) {
        if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
            tmp[p] = A[l];
            add(A[l].v, 1);
            l ++;
        } else {
            tmp[p] = A[r];
            ans[A[r].id] += query(A[r].v + 1, n);
            r ++;
        }
    }
    for(int i = L; i <= M; i ++) {
        clean(A[i].v);
    }
    for(int i = L; i <= R; i ++) {
        A[i] = tmp[i];
    }
}
bool cmp_id(const Query& a, const Query& b) {
    return a.id < b.id;
}
 
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
    int m;
    scanf("%d%d", &n, &m);
    int id_siz = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= m; i ++) {
        int a;
        scanf("%d", &a);
        delS.push(a);
        del[a] = true;
    }
    for(int i = 1; i <= n; i ++) {
        if(del[arr[i]]) {
            pos[arr[i]] = i;
        } else {
            id_siz ++;
            A[id_siz].id = id_siz;
            A[id_siz].p = i;
            A[id_siz].v = arr[i];
        }
    }
    while(!delS.empty()) {
        int a = delS.top(); delS.pop();
        id_siz ++;
        A[id_siz].id = id_siz;
        A[id_siz].p = pos[a];
        A[id_siz].v = a;
    }
    CDQ(1, n, true);
    sort(A + 1, A + 1 + n, cmp_id);
    for(int i = 1; i <= n; i ++) {
        A[i].v = n - A[i].v + 1;
    }
    CDQ(1, n, false);
    for(int i = 1; i <= n; i ++) {
        ans[i] += ans[i - 1];
    }
    for(int i = 0; i < m; i ++) {
        printf("%lld\n", ans[n - i]);
    }
    return 0;
}

[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。

继续阅读

[BZOJ 1483][HNOI2009]梦幻布丁

做了很久了吧,但现在才写题解……(斜眼

首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?

这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。

继续阅读

[BZOJ 3252]攻略

近期心情不顺,坑了一堆没写的题解……(嗯我反演等回来再填坑吧(逃

好了还是说说这题吧,私以为鄙人的做法还是蛮妙的:

定义\(d(x)\)表示\(x\)到根上所有点的权值和,\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点,他的所有儿子中\(d_{max}(x)\)最大的称为重儿子,其他作为轻儿子,然后做一遍树剖。然后将所有重链的权值和扔到一个数组里,降序排序,选前\(k\)大求和即可(不够的话全选)。

为什么?

显然,尽可能选叶子是划算的。然后,任意一条重链链顶的父亲所在的重链的权值和必定大于该重链,所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并,恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的,所以答案是最优的。

继续阅读

[坑]狄利克雷卷积和反演

开个坑,记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了,就讲讲性质吧。

有几个一定要记住的东西:

\[\mu \ast 1 = e\]

\[\varphi \ast 1 = id\]

\[\mu \ast id = \varphi\]

这几个在推式子的过程中都有很大的作用,务必要记住。

所谓莫比乌斯反演,其实就是:

\[F = f \ast 1\Leftrightarrow f = F \ast \mu\]

(谜之音:其实很多所谓“反演题”都没用到这俩性质啊……)

关于莫比乌斯函数本身,还有一个好康的性质:

\[(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i\]

继续阅读

[BZOJ 2599][IOI2011]Race

由于一些琐事,很长时间没有更新博客了……尽管做了不少题,但还是给我些时间整理思绪吧……

大方向肯定是点分治没错啦……

点分治的题处理经过根的路径通常有两种套路……一种是类似BZOJ 1468那样,收集所有儿子的信息,然后一次性合并,并排除不合法的情况。另一种类似于这道题,顺次处理儿子的信息,处理一个合并一个。

具体的思路是,用[tex]p[x][/tex]表示目前已知的所有从根开始长度为[tex]x[/tex]的路径(当然根本身也算上啦,所以说一开始就把[tex]p[root][/tex]设为0),然后根搜集信息时每次对一个儿子进行DFS,假设某结点[tex]x[/tex]到根的距离为[tex]d[x][/tex],那么显然[tex]x[/tex]对答案的贡献为[tex]p[k-d[x]][/tex],之后把这个子树合并到[tex]p[/tex]中。

注意清理[tex]p[/tex]的时候不能直接暴力memset……这样会被卡常致死。更好的方法是对于每次把子树合并到[tex]p[/tex]中时,把[tex]x[/tex]记录下来,然后清理[tex]p[/tex]时常数就小很多了。

代码:

/**************************************************************
    Problem: 2599
    User: danihao123
    Language: C++
    Result: Accepted
    Time:14640 ms
    Memory:23532 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int maxm = maxn * 2;
const int maxk = 1000005;
struct Edge {
    Edge *next;
    int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
    graph_cnt = 0;
    memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
    Edge *e = &pool[graph_cnt++];
    e->next = first[u];
    first[u] = e;
    e->to = v;
    e->dist = d;
}
 
int k;
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
    siz[x] = 1;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_siz(v, x);
            siz[x] += siz[v];
        }
    }
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
    bool OK = siz[x]*2 >= siz[now_root];
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_best_root(v, x);
            OK = OK && (siz[v]*2 <= siz[now_root]);
        }
    }
    if(OK) {
        best_root = x;
    }
}
int buf[maxk];
int ans;
void deal_ans(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    ans = min(ans, dep + buf[k-d]);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            deal_ans(v, x, dep + 1, d + e->dist);
        }
    }
}
void add_to_buf(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    buf[d] = min(buf[d], dep);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            add_to_buf(v, x, dep + 1, d + e->dist);
        }
    }
}
void clear_buf(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    buf[d] = 0x3f3f3f3f;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            clear_buf(v, x, dep + 1, d + e->dist);
        }
    }
}
void divide(int x) {
    gen_siz(x, 0);
    now_root = best_root = x; gen_best_root(x, 0);
    x = best_root;
    vis[x] = true;
    buf[0] = 0;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            deal_ans(v, x, 1, e->dist);
            add_to_buf(v, x, 1, e->dist);
        }
    }
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            clear_buf(v, x, 1, e->dist);
        }
    }
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            divide(v);
        }
    }
}
inline int readint() {
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}
 
int main() {
    int n;
    n = readint();
    k = readint();
    clear_graph();
    for(int i = 1; i <= (n-1); i++) {
        int u, v, d;
        u = readint();
        v = readint();
        d = readint();
        u++; v++;
        add_edge(u, v, d);
        add_edge(v, u, d);
    }
    ans = 0x3f3f3f3f;
    memset(buf, 0x3f, sizeof buf);
    divide(1);
    if(ans == 0x3f3f3f3f) {
        ans = -1;
    }
    printf("%d\n", ans);
    return 0;
}