SDOI2017选讲

序列计数

至少有一个数是质数的情况 = 忽略质数的情况 - 无质数的情况，矩乘加速

新生舞会

很裸的分数规划 + km或费用流判是否合法，我不会km qwq。。

网络流，要计算空间啊。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e4 + 5, inf = 1e9;  // 空间要开足
const double eps = 1e-9;
int n, a[105][105], b[105][105], S, T;
int to[N], fr[N], lnk[N], cnt, nxt[N], cap[N], pre[N], rest[N];
bool inq[N];
double val[N], dis[N], ans;
queue<int> q;

void add(int x, int y, int c, double v) {
    ++cnt;
    to[cnt] = y, fr[cnt] = x, nxt[cnt] = lnk[x], lnk[x] = cnt, cap[cnt] = c, val[cnt] = v;
}

bool spfa(int S, int T, int &flow, double &cost) {
    rep(i, S, T) dis[i] = -1e18, inq[i] = pre[i] = 0;
    inq[S] = 1, rest[S] = inf, pre[S] = 0, dis[S] = 0;
    q.push(S);
    while (q.size()) {
        int x = q.front(); q.pop(); inq[x] = 0;
        for (int i = lnk[x]; i; i = nxt[i]) {
            int y = to[i];
            if (cap[i] > 0 && dis[y] < dis[x] + val[i]) {
                dis[y] = dis[x] + val[i];
                pre[y] = i;
                rest[y] = min(rest[x], cap[i]);
                if (!inq[y]) {
                    inq[y] = 1, q.push(y);
                }
            }
        }
    }
    if (dis[T] == -1e18) return 0;
    flow += rest[T];
    cost += dis[T] * rest[T];
    int x = T;
    while (x != S) {
        cap[pre[x]] -= rest[T], cap[pre[x] ^ 1] += rest[T];
        x = fr[pre[x]];
    }
    return 1;
}

bool chk(double mid) {
    cnt = 1;
    memset(lnk, 0, sizeof(lnk));
    rep(i, 1, n) {
        add(S, i, 1, 0), add(i, S, 0, 0);
        add(i + n, T, 1, 0), add(T, i + n, 0, 0);
    }
    rep(i, 1, n) {
        rep(j, 1, n) {
            double v = a[i][j] - b[i][j] * mid;
            add(i, j + n, 1, v);
            add(j + n, i, 0, -v);
        }
    }
    int flow = 0; double cost = 0;
    while (spfa(S, T, flow, cost));
    return cost >= 0;
}

int main() {
    cin >> n;
    S = 0, T = 2 * n + 1;
    rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
    rep(i, 1, n) rep(j, 1, n) cin >> b[i][j];
    double l = 0, r = 1e9;
    while (r - l > eps) {
        double mid = (l + r) / 2.0;
        if (chk(mid)) ans = mid, l = mid;
        else r = mid;
    } printf("%.6lf\n", ans);
    return 0;
}

硬币游戏

神仙题，想不出来orz

直接 AC 自动机 + 高斯消元是 O((nm)^3) 的，因为有 nm 个方程

最终复杂度应该在 O(n^3) 以内，方程数应该是 O(n) 级别的

关键点是用 N 来表示没有人获胜的状态，将方程数压缩到 n + 1 个，然后解方程

例如：A = TTH, B = HTT

N + TTH = A赢 + (B赢 + H) + (B赢 + TH)

0.125N = A赢 + 0.75B赢

n + 1 个变量，n + 1 个方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
using namespace std;

typedef unsigned long long ull;
const int N = 305;
const ull P = 131;
const double eps = 1e-7;
int n, m;
double g[N][N], bit2[N], x[N];
char s[N];
ull pre[N][N], sub[N][N], pw[N];

void Gauss(int n) {
    rep(i, 1, n) {
        int id = i;
        rep(j, i, n) if (g[j][i] > eps) id = j;
        swap(g[i], g[id]);
        rep(j, i + 1, n) {
            double t = g[j][i] / g[i][i];
            rep(k, i + 1, n + 1) g[j][k] -= g[i][k] * t;
        }
    }
    per(i, n, 1) {
        x[i] = g[i][n + 1] / g[i][i];
        rep(j, 1, i - 1) g[j][n + 1] -= g[i][n + 1] * (g[j][i] / g[i][i]);
    }
}

int main() {
    cin >> n >> m;
    bit2[0] = pw[0] = 1;
    rep(i, 1, m) bit2[i] = bit2[i - 1] * 0.5, pw[i] = pw[i - 1] * P;
    rep(i, 1, n) {
        scanf("%s", s + 1);
        rep(j, 1, m) {
            pre[i][j] = pre[i][j - 1] + (s[j] == 'H' ? 1 : 0) * pw[j];
            sub[i][j] = sub[i][j - 1] * P + (s[m - j + 1] == 'H' ? 1 : 0) * P;
        }
    }
    rep(i, 1, n) {
        g[i][n + 1] = -bit2[m];
        rep(j, 1, n) {
            rep(a, 1, m) {
                if (pre[i][a] == sub[j][a]) {
                    g[i][j] += bit2[m - a];
                }
            }
        }
    }
    rep(i, 1, n) g[n + 1][i] = 1;
    g[n + 1][n + 2] = 1;
    Gauss(n + 1);
    rep(i, 1, n) printf("%.10lf\n", x[i]);
    return 0;
}