danihao123's Blog

只会做水题力……qwq（搞错大小写，自裁请）

每条边存在的时间事一个区间，因此考虑线段树分治……首先当然要写一个可撤销并查集。

然后每个点维护他到父亲的边的边权膜2，合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了，因为LCA到根的部分会算两遍，对答案无影响。

代码：

/**************************************************************
    Problem: 4025
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9928 ms
    Memory:34840 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
const int maxn = 100005;
const int maxno = maxn << 2;
const int maxm = 200005;
int n, m, T;
 
int p[maxn], siz[maxn], d[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; siz[i] = 1; d[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
int get_d(int x) {
  if(p[x] == x) {
    return 0;
  } else {
    return (d[x] + get_d(p[x])) % 2;
  }
}
typedef std::pair<int, int> upd;
upd link_set(int x, int y, int v) {
  if(siz[x] > siz[y]) std::swap(x, y);
  p[x] = y; siz[y] += siz[x]; d[x] = v;
  return std::make_pair(x, y);
}
upd merge_set(int x, int y) {
  int v = (get_d(x) + get_d(y) + 1) % 2;
  return link_set(get_fa(x), get_fa(y), v);
}
void unlink_set(const upd &pr) {
  int x = pr.first, y = pr.second;
  p[x] = x; siz[y] -= siz[x]; d[x] = 0;
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
std::vector<upd> event[maxno];
std::stack<std::pair<int, upd> > S;
void update(int o, int L, int R, int ql, int qr, upd v) {
  if(ql <= L && R <= qr) {
    event[o].push_back(v);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
  }
}
int val[maxno];
void solve(int o, int L, int R) {
  for(int i = 0; i < event[o].size(); i ++) {
    const upd &pr = event[o][i];
    int x = pr.first, y = pr.second;
    if(is_same(x, y)) {
      if((get_d(x) + get_d(y)) % 2 == 0) {
        val[o] = 0;
        break;
      }
    } else {
      S.push(std::make_pair(o, merge_set(x, y)));
    }
  }
  if(L == R) {
    if(val[o] != 0) val[o] = 1;
  } else {
    if(val[o] != 0) {
      int M = (L + R) / 2;
      solve(o << 1, L, M);
      solve(o << 1 | 1, M + 1, R);
    }
  }
  while((!S.empty()) && S.top().first >= o) {
    upd v = S.top().second; S.pop();
    unlink_set(v);
  }
}
void print(int o, int L, int R) {
  if(L == R) {
    if(val[o]) {
      puts("Yes");
    } else {
      puts("No");
    }
  } else {
    if(val[o] != -1) {
      val[o << 1] = val[o];
      val[o << 1 | 1] = val[o];
    }
    int M = (L + R) / 2;
    print(o << 1, L, M);
    print(o << 1 | 1, M + 1, R);
  }
}
 
int main() {
  memset(val, -1, sizeof(val));
  scanf("%d%d%d", &n, &m, &T);
  for(int i = 1; i <= m; i ++) {
    int u, v, s, t; scanf("%d%d%d%d", &u, &v, &s, &t);
    s ++; if(s <= t) update(1, 1, T, s, t, std::make_pair(u, v));
  }
  init_dsu(); solve(1, 1, T); print(1, 1, T);
  return 0;
}

一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解

还有样例过于草（出题人钦点淫梦运营）

考虑从小到大枚举序列的每一位置\(p\)，然后我们发现每一位置的值的合法性事单调的（小的合法，大了就不合法），这样可以对每一个位置二分答案。

然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)（表示当前还没有被预定的大于等于\(i\)的数有多少个），然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响，然后每次一个点确定是什么值了也要修改对应的前缀区间。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, addv[o]); paint(rc, addv[o]);
    addv[o] = 0;
  }
}

int left[maxn];
void build_tree(int o, int L, int R) {
  // addv[o] = 0;
  if(L == R) {
    minv[o] = left[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = INF;
    if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

int d[maxn], d2[maxn];
int lsiz;
void process() {
  std::sort(d + 1, d + 1 + n);
  std::sort(d2 + 1, d2 + 1 + n);
  lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
  for(int i = 1; i <= n; i ++) {
    d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
    left[d[i]] ++;
  }
  for(int i = lsiz - 1; i >= 1; i --) {
    left[i] += left[i + 1];
  }
  build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
  for(int i = n; i >= 1; i --) {
    siz[i] ++;
    int f = (int)floor((R(i)) / k);
    siz[f] += siz[i];
  }
  for(int i = 1; i <= n; i ++) {
    int f = (int)floor((R(i)) / k);
    if(f > 0) {
      update(1, 1, lsiz, 1, A[f], siz[i]);
    }
    int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
    while(true) {
      if(R - L <= 3) {
        for(int j = R; j >= L; j --) {
          if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
            ret = j; break;
          }
        }
        break;
      }
      int M = L + (R - L) / 2;
      if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
        L = M;
      } else {
        R = M;
      }
    }
    A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
  }
}

int main() {
  scanf("%d%Lf", &n, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &d[i]); d2[i] = d[i];
  }
  process(); solve();
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    printf("%d", d2[A[i]]);
  }
  puts(""); return 0;
}

APIO的时候听了一下wqs二分，做了这题，然后现在才写题解……

wqs二分的思路大抵就是你要求必须选\(k\)个，那就二分每个操作的一个“额外代价”，然后进行没有限制的选择。然后最后选出来的个数事和你二分的代价正相关/反相关的。

这道题的话，就二分选择黑边的代价，然后跑一般的最小生成树（有相同边权时要选择黑边！）。当然我们会遇到一个问题，就是二分到\(x\)的时候选的比\(k\)多，到\(x + 1\)的时候又比\(k\)少了。这道题的处理方法，事考虑代价为\(x\)时，其实存在选\(k\)个的最优解（如果说大于\(x\)那就没了），因此我们钦点代价为\(x\)跑一遍限制只能选\(k\)条黑边的最短路即可。

代码：

/**************************************************************
    Problem: 2654
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5756 ms
    Memory:5856 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
const int maxm = 100005;
struct Edge {
  int u, v, d;
  int typ;
  bool operator <(const Edge &res) const {
    if(d == res.d) {
      return typ < res.typ;
    } else {
      return d < res.d;
    }
  }
};
 
Edge E[maxm];
int n, m, need;
 
int par[maxn], siz[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    par[i] = i;
    siz[i] = 1;
  }
}
int get_fa(int x) {
  if(par[x] == x) {
    return x;
  } else {
    return (par[x] = get_fa(par[x]));
  }
}
void link_set(int x, int y) {
  if(siz[x] > siz[y]) std::swap(x, y);
  siz[y] += siz[x];
  par[x] = y;
}
void merge_set(int x, int y) {
  return link_set(get_fa(x), get_fa(y));
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
typedef long long ll;
int ans = 0x7fffffff;
bool kruskal(int delta) {
  std::vector<Edge> vec;
  for(int i = 1; i <= m; i ++) {
    Edge e = E[i];
    if(e.typ == 0) {
      e.d += delta;
    }
    vec.push_back(e);
  }
  std::sort(vec.begin(), vec.end());
  int used = 0; ll tot = -(ll(delta)) * (ll(need));
  init_dsu();
  for(int i = 0; i < m; i ++) {
    const Edge &e = vec[i];
    int u = e.u, v = e.v;
    if(!is_same(u, v)) {
      if(used == need && e.typ == 0) continue;
      merge_set(u, v); tot += e.d;
      if(e.typ == 0) used ++;
    }
  }
  if(used == need) {
    ans = std::min(ans, (int(tot)));
    return true;
  } else {
    return false;
  }
}
 
int main() {
  scanf("%d%d%d", &n, &m, &need);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].d, &E[i].typ);
    E[i].u ++; E[i].v ++;
  }
  int L = -10000001, R = 10000001;
  while(true) {
#ifdef LOCAL
    printf("Range (%d, %d)\n", L, R);
    fflush(stdout);
#endif
    if(R - L <= 3) {
      for(int i = R; i >= L; i --) {
        if(kruskal(i)) {
          break;
        }
      }
      break;
    }
    int M = L + (R - L) / 2;
    if(kruskal(M)) {
      L = M;
    } else {
      R = M;
    }
  }
  printf("%d\n", ans);
  return 0;
}

肉肉肉肉，，，

碰置换群啥的不是第一次了……这个题就是给你一堆置换（不要忘记还有一个幺元啊），然后限制颜色数量，求本质不同解个数。那么考虑使用Burnside引理，接下来考虑怎么计算每个置换的不动点数量，这个要求每个循环的颜色一致（不就事Polya定理了吗），所以说可以用背包DP搞一搞。

代码：

/**************************************************************
    Problem: 1004
    User: danihao123
    Language: C++
    Result: Accepted
    Time:156 ms
    Memory:3172 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
int sr, sb, sg, m, p;
int pow_mod(int a, int b) {
  int ans = 1, res = a;
  while(b) {
    if(1 & b) ans = (ans * res) % p;
    res = (res * res) % p; b >>= 1;
  }
  return ans;
}
int inv(int x) {
  return pow_mod(x % p, p - 2);
}
 
int d[65][21][21][21];
std::vector<int> len;
int dp() {
  int n = len.size();
  d[0][0][0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    int l = len[i - 1];
    for(int j = 0; j <= sr; j ++) {
      for(int k = 0; k <= sb; k ++) {
        for(int t = 0; t <= sg; t ++) {
          d[i][j][k][t] = 0;
          if(j >= l) d[i][j][k][t] += d[i - 1][j - l][k][t];
          if(k >= l) d[i][j][k][t] += d[i - 1][j][k - l][t];
          if(t >= l) d[i][j][k][t] += d[i - 1][j][k][t - l];
          d[i][j][k][t] %= p;
        }
      }
    }
  }
  return d[n][sr][sb][sg];
}
 
int next[65]; bool vis[65];
int main() {
  scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &p);
  int n = sr + sb + sg;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    len.push_back(1);
  }
  ans = dp();
  for(int i = 1; i <= m; i ++) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &next[i]);
    }
    len.clear();
    for(int i = 1; i <= n; i ++) {
      if(!vis[i]) {
        int p = i, cnt = 0;
        do {
          vis[p] = true; cnt ++;
          p = next[p];
        } while(p != i);
        len.push_back(cnt);
      }
    }
    ans = (ans + dp()) % p;
  }
  ans = (ans * inv(m + 1)) % p;
  printf("%d\n", ans);
  return 0;
}

逆矩阵文明，，，

很显然我们可以定义一个状态\(f[i][j]\)表示当前血量为\(i\)走到\(j\)的概率，然后肥肠爆歉这个东西没法DP（可能会有的点的伤害为0，这样可以凿出来环）。考虑高消，这个东西有个好处是不可能从血量低的到血量高的状态，所以可以从大到小枚举血量，这样各层事独立的，复杂度比直接高消降低了很少。可惜复杂度为\(O(sn^3)\)（设血量为\(s\)），会T掉。

考虑转移的过程，转移时等价于解这样一个方程：

\[
\begin{aligned}
a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} &= c_1\\
a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} &= c_2\\
&\ldots\\
a_{n1}x_{1} + a_{n2}x_{2} + \ldots + a_{nn}x_{n} &= c_n
\end{aligned}
\]

其中的未知数\(x\)事我们要求的东西，\(c\)表示从高血量状态转移过来的概率（这个可以视作常数）。根据友矩阵那一套理论，这一系列方程等价于以下等式：

\[
\begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \ldots & a_{nn}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ x_{2} \\ \vdots \\ x_{n}
\end{bmatrix}
=
\begin{bmatrix}
c_1\\ c_2\\ \vdots\\ c_n
\end{bmatrix}
\]

不妨将之简记为\(AB = C\)，其中我们只有\(B\)不知道，要求的也是\(B\)。我们除一下就可以得到\(B = A^{-1}C\)，然后我们还发现每一层的\(A\)都是一样的，所以每一层的\(A^{-1}\)也都是一样的，预处理即可。这样转移部分的复杂度就变成了\(O(sn^2)\)（矩阵乘法在这里事方阵乘列向量）。

至于逆矩阵的求法，我们知道对矩阵做初等变化也就等价于乘上另一个矩阵。因此，我们将一个矩阵\(A\)用类似于高消的手段消为单位阵\(I\)，所做的初等变换也就等价于乘上\(A^{-1}\)。我们对一个单位阵\(I\)作用上一样的操作，也就等于给这个单位阵乘上了\(A^{-1}\)，这样我们就得到了\(A^{-1}\)。

代码：

/**************************************************************
    Problem: 3640
    User: danihao123
    Language: C++
    Result: Accepted
    Time:8708 ms
    Memory:13416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
int n, m, hp;
const int maxn = 151, maxm = 5005;
const int maxh = 10005;
typedef double R;
typedef R Mat[maxn][maxn];
Mat D, F;
void calc_inv() {
  for(int i = 1; i <= n; i ++) {
    F[i][i] = 1;
  }
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    // assert(r > -1);
    if(r != i) {
      for(int j = 1; j <= n; j ++) {
        std::swap(D[r][j], D[i][j]);
        std::swap(F[r][j], F[i][j]);
      }
    }
    R bs = D[i][i];
    for(int j = 1; j <= n; j ++) {
      D[i][j] /= bs; F[i][j] /= bs;
    }
    for(int k = 1; k <= n; k ++) {
      if(k != i) {
        R rate = D[k][i];
        for(int j = 1; j <= n; j ++) {
          D[k][j] -= rate * D[i][j];
          F[k][j] -= rate * F[i][j];
        }
      }
    }
  }
}
void matrix_mul(const Mat &A, const Mat &B, int a, int b, int c, Mat &res) {
  static Mat C;
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      C[i][j] = 0;
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      for(int k = 1; k <= b; k ++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      res[i][j] = C[i][j];
    }
  }
}
 
int first[maxn], deg[maxn];
int next[maxm << 1], to[maxm << 1];
int gcnt = 0;
void add_edge(int u, int v) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v;
}
void ins_edge(int u, int v) {
  deg[u] ++;
  add_edge(u, v);
  if(u != v) {
    deg[v] ++;
    add_edge(v, u);
  }
}
 
int atk[maxn];
R f[maxh][maxn];
R solve() {
  for(int i = 1; i <= n; i ++) {
    D[i][i] = 1.00;
  }
  for(int i = 1; i < n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(!atk[v]) {
        D[v][i] -= 1.00 / (R(deg[i]));
      }
    }
  }
  calc_inv();
  R ans = 0; static Mat C;
  f[hp][1] = 1.00;
  for(int i = hp; i >= 1; i --) {
    for(int j = 1; j <= n; j ++) {
      C[j][1] = f[i][j];
    }
    matrix_mul(F, C, n, n, 1, C);
    for(int j = 1; j < n; j ++) {
      for(int e = first[j]; e; e = next[e]) {
        int v = to[e];
        if(atk[v] > 0 && i - atk[v] > 0) {
          f[i - atk[v]][v] += C[j][1] / (R(deg[j]));
        }
      }
    }
    ans += C[n][1];
  }
  return ans;
}
 
int main() {
  scanf("%d%d%d", &n, &m, &hp);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &atk[i]);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  printf("%.8lf\n", solve());
  return 0;
}

本野蛮人竟然没做过高消期望DP，，，泪，流了下来，，，

根据期望线性性，答案就是所有边的期望被走的次数乘上边的编号的和。一条边期望经过的次数可以根据他两个端点期望经过的次数来算（但是\(n\)要特判一下），要求所有点期望走过的次数当然就可以列\(n\)个方程然后高消力。然后期望走的次数多的边编号应该小，反之亦然，所以求完每条边走的次数的期望之后就贪心一下就好力。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
const int maxn = 505;
const int maxm = maxn * maxn;
using R = double;
const R eps = 1e-9;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    return ((x < 0.00) ? -1 : 1);
  }
}
R D[maxn][maxn];
int n;
void gauss() {
#ifdef LOCAL
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n + 1; j ++) {
      printf("%.3lf ", D[i][j]);
    }
    puts("");
  }
#endif
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    assert(sign(D[r][i]) != 0);
    if(r != i) {
      for(int j = 1; j <= n + 1; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    for(int k = i + 1; k <= n; k ++) {
      R rate = D[k][i] / D[i][i];
      for(int j = i; j <= n + 1; j ++) {
        D[k][j] -= D[i][j] * rate;
      }
    }
  }
  for(int i = n; i >= 1; i --) {
    for(int j = i + 1; j <= n; j ++) {
      D[i][n + 1] -= D[j][n + 1] * D[i][j];
      D[i][j] = 0;
    }
    D[i][n + 1] /= D[i][i]; D[i][i] = 1;
#ifdef LOCAL
    printf("E[%d] : %.3lf\n", i, D[i][n + 1]);
#endif
  }
}

int E[maxm][2], deg[maxn];
R tms[maxm];
void add_edge(int u, int v) {
  if(u != n) D[v][u] += 1.00 / (R(deg[u]));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    D[i][i] = -1;
  }
  D[1][n + 1] = -1;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    deg[E[i][0]] ++; deg[E[i][1]] ++;
  }
  for(int i = 1; i <= m; i ++) {
    int u = E[i][0], v = E[i][1];
    add_edge(u, v); add_edge(v, u);
  }
  gauss();
  for(int i = 1; i <= m; i ++) {
    tms[i] = 0;
    int u = E[i][0], v = E[i][1];
    if(u != n) tms[i] += D[u][n + 1] / (R(deg[u]));
    if(v != n) tms[i] += D[v][n + 1] / (R(deg[v]));
  }
  std::sort(tms + 1, tms + 1 + m, [&](const R &i, const R &j) { return i > j; });
  R ans = 0;
  for(int i = 1; i <= m; i ++) {
    ans += tms[i] * (R(i));
  }
  printf("%.3lf\n", ans);
  return 0;
}

aji波兰题！（迫真）

啊波兰题真好康（一转）

考虑怎么去除非加油站的影响……对于每两个加油站，取他们的最短路，然后建出来一个图，这个图的MST上的路径的走法就事最优走法。

但这样显然会凉……因为\(s\)肥肠巨大，会T。然后我们考虑多源最短路，并且给每个点标记到它最近的加油站（称为来源）。那么考虑两条加油站间的路径，上面一定有一条边满足边两个端点不一样（证明考虑……如果所有边两边端点的来源都一样，那么所有边的来源会同时事那两个加油站）。

然后一个小问题事，如果一个点有多个来源，只考虑一个会出事吗？这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\)，如果说三者到一个点的最短路都一样，那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边，但现在因为这个连不了了，那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边，所以事实上没有什么笋丝。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
  static int cnt = 0;
  cnt ++; next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
  add_edge(u, v, w); add_edge(v, u, w, false);
}

using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
  memset(d, 0x1f, sizeof(d));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  for(auto p : V) {
    d[p] = 0; src[p] = p;
    Q.push(std::make_pair(0LL, p));
  }
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(d[u] + (ll(dist[i])) < d[v]) {
        d[v] = d[u] + (ll(dist[i]));
        src[v] = src[u];
        Q.push(std::make_pair(d[v], v));
      }
    }
  }
}

int p[maxn], rk[maxn];
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
void init_set() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i;
  }
}

struct Edge {
  int u, v; ll w;
  Edge(int a = 0, int b = 0, ll c = 0) {
    u = a; v = b; w = c;
  }
  bool operator <(const Edge &res) const {
    return w < res.w;
  }
};
int m; Edge E[maxm];
int ecnt;
void process() {
  dij(); ecnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(dir[j] && src[i] != src[v]) {
        E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
      }
    }
  }
  std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
  int q; scanf("%d", &q);
  init_set(); int cur = 0;
  std::vector<std::pair<Edge, int> > Q;
  for(int i = 1; i <= q; i ++) {
    int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
    Q.push_back(std::make_pair(Edge(u, v, w), i));
  }
  std::sort(Q.begin(), Q.end());
  for(auto x : Q) {
    Edge e = x.first;
    while(cur < ecnt && E[cur + 1].w <= e.w) {
      cur ++;
      merge_set(E[cur].u, E[cur].v);
    }
    ans[x.second] = is_same(e.u, e.v);
  }
  for(int i = 1; i <= q; i ++) {
    if(ans[i]) {
      puts("TAK");
    } else {
      puts("NIE");
    }
  }
}

int main() {
  int s; scanf("%d%d%d", &n, &s, &m);
  for(int i = 1; i <= s; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process(); solve();
  return 0;
}

aji波兰题！（直球）

这个题显然就是对那个排列乘上一个置换，然后置换的每一个循环事独立的，于是分别考虑每一个循环。

然后每一个循环有一种显然的构造方法就是从一个点开始，逆着边不停的交换两个点。这样的话有一个点会对答案做\(s - 1\)次贡献（\(s\)为循环大小），其他点都会只做一次循环。显然那个点选权值最小的点事坠吼的。

还有一种构造就是把全局最小值和循环最小值换一下，然后用上面的手段构造，最后再把全局最小值和循环最小值换回来。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 1000005;
int next[maxn];

using ll = long long;
ll m[maxn];
int A[maxn], B[maxn], ma[maxn];
bool vis[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &m[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); ma[A[i]] = i;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
    next[ma[B[i]]] = i;
  }
  ll ans = 0LL; ll tv = *std::min_element(m + 1, m + 1 + n);
  for(int i = 1; i <= n; i ++) {
    if(next[i] != i && !vis[i]) {
      int p = i; ll sumv = 0LL, minv = 0x7fffffffLL;
      ll cnt = 0;
      do {
        vis[p] = true; cnt ++;
        sumv += m[A[p]]; minv = std::min(minv, m[A[p]]);
        p = next[p];
      } while(p != i);
      ll delta = sumv + std::min(minv * (cnt - 2LL), minv + tv * (cnt + 1LL));
      ans += delta;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

很多人说事动态虚树……其实也不算是吧，虽然这个东西用力虚树的思路惹。

第一个想到的思路……就事动态的维护虚树，然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序（严格来说事欧拉序）排序，所以我们大致可以认为，虚树上做欧拉回路的本质就事按照DFS序扫描，换言之就事DFS一遍，然后进入和回溯事都把边记录到答案里，这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和（首尾也要额外算一遍）。

然后这样一来，我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA，然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点，问题就简单了许多……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
  G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
  add_edge(u, v, w); add_edge(v, u, w);
}

int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
  anc[x][0] = fa; dfn[x] = ++ dcnt;
  for(auto &e : G[x]) {
    int v = e.first; ll w = e.second;
    if(v != fa) {
      dep[v] = dep[x] + 1;
      dis[v] = dis[x] + w;
      dfs(v, x);
    }
  }
}
int n;
void process() {
  memset(anc, -1, sizeof(anc)); dfs(1);
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 16; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) {
      u = a;
    }
  }
  if(u == v) return u;
  for(int j = 16; j >= 0; j --) {
    int a1 = anc[u][j], a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1; v = a2;
    }
  }
  return anc[u][0];
}
ll calc_dist(int u, int v) {
  return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}

// template <typename T>
struct Comp {
  bool operator ()(const int &a, const int &b) const {
    return dfn[a] < dfn[b];
  }
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.begin()) {
    auto pre = -- suc; ++ suc;
    now += calc_dist(*pre, p);
    if(suc != S.end()) {
      now -= calc_dist(*pre, *suc);
    }
  }
  if(suc != S.end()) {
    now += calc_dist(*suc, p);
  }
  S.insert(p);
}
void del(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.end()) {
    now -= calc_dist(*suc, p);
  }
  if((*S.begin()) != p) {
    -- suc; -- suc;
    int prev = *suc;
    now -= calc_dist(prev, p);
    ++ suc; ++ suc;
    if(suc != S.end()) {
      now += calc_dist(prev, *suc);
    }
  }
  S.erase(p);
}
ll query() {
  if(S.size() <= 1) return 0LL;
  ll ret = now;
  auto las = S.end(); -- las;
  ret += calc_dist(*S.begin(), *las);
  return ret;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process();
  while(m --) {
    int x; scanf("%d", &x);
    if(sta[x]) {
      del(x);
    } else {
      add(x);
    }
    sta[x] = !sta[x];
    printf("%lld\n", query());
  }
  return 0;
}

啊啊啊爽到力，，，

过去太池沼力，没有做出来惹。现在看了看可能比较简单罢……

定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\)，然后当前的生成树已经考虑到了第\(i\)层，转移看起来很毒……

所以预处理一个点集到另一个点集只走一步边来扩展，最优解是多少，然后转移就方便力……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
  G[u][v] = std::min(G[u][v], d);
  G[v][u] = std::min(G[v][u], d);
}

int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
  for(int s = 1; s < (1 << n); s ++) {
    for(int i = 1; i <= n; i ++) {
      g1[s][i] = INF;
      for(int j = 0; j < n; j ++) {
        if((1 << j) & s) {
          g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
        }
      }
    }
  }
  for(int s = 1; s < (1 << n); s ++) {
    int k = (1 << n) - 1; k = k & (~s);
    for(int t = k; t > 0; t = (t - 1) & k) {
      g2[s][t] = 0;
      for(int i = 1; i <= n; i ++) {
        if((1 << (i - 1)) & t) {
          if(g1[s][i] == INF) {
            g2[s][t] = INF; break;
          }
          g2[s][t] += g1[s][i];
        }
      }
    }
  }
}

using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
  for(int s = 0; s < (1 << n); s ++) {
    d[1][s] = INF;
  }
  for(int i = 0; i < n; i ++) {
    d[1][(1 << i)] = 0;
  }
  for(int i = 2; i <= n; i ++) {
    for(int s = 1; s < (1 << n); s ++) {
      d[i][s] = INF;
      for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
        d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
      }
    }
  }
  ll ans = INF;
  for(int i = 1; i <= n; i ++) {
    ans = std::min(ans, d[i][(1 << n) - 1]);
  }
  return ans;
}

int main() {
  memset(G, 0x3f, sizeof(G));
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w);
  }
  process(); printf("%lld\n", dp());
  return 0;
}