[LibreOJ 6433][PKUSC2018]最大前缀和

给你一个长为\(n\)的整数序列\(a\),求出将序列随机打乱之后的最大前缀和(不能选空前缀!)的期望,答案乘上\(n!\)之后对\(998244353\)输出。

\(1\leq n\leq 20, \sum_{i = 1}^n |a_i|\leq 10^9\)。

继续阅读

[UOJ 333][NOIP2017]宝藏

啊啊啊爽到力,,,

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

定义状态\(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;
}

[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,\,x}\,\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;
}