UOJ Logo harryhe的博客

博客

标签

停课训练day13 -- 高爸的题解

2018-10-31 14:09:11 By harryhe

Poker

http://zhengruioi.com/problem/119

有 $n$ 张牌,点数分别为 $a_1 \cdots a_{n}$。小 $\text{M}$ 和小 $\text{D}$ 从牌堆中随机抽 $\dfrac{n}{2}$ 张牌并按顺序排列。然后,他们按顺序出牌,如果小 $\text{M}$ 的牌的点数大于小 $\text{D}$ 牌的点数,则小 $\text{M}$ 加一分。否则小 $\text{D}$ 加一分。问两人的期望得分。

分析

可以认为一开始两个人的得分为 $\dfrac{n}{4}$,然后对于每对相同的牌,如果它被分到两个不同的牌堆里 $\left(概率 = \dfrac{\dfrac{n}{2}}{n - 1}\right)$ 并且在同一时间的时候出牌 $\left(概率 = \dfrac{1}{n}\right)$,那么小 $\text{M}$ 减一分,小 $\text{D}$ 加一分,所以我们只要统计相同牌的对数即可。

代码

http://zhengruioi.com/submission/52384

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5, P = 1e9 + 7;
int n, a[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    int X = n / 2;
    for (int i = 2; i <= n - 2; i++) {
        X = 1ll * X * i % P;
    }
    int M = 1ll * X * (n - 1) % P * (n / 2) % P, D = M;
    int cnt = 0, sum = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] == a[i - 1]) {
            ++cnt;
            sum = (sum + 1ll * X * cnt) % P;
        } else {
            cnt = 0;
        }
    }
    printf("%d %d\n", (M - sum + P) % P, (D + sum) % P);
    return 0;
}

Label

http://zhengruioi.com/problem/120

给定一个 $n$ 个点 $m$ 条边的带权无向图,有的点的点权已经给定,剩下的点的点权要你来确定。求 $\sum_{i = 1}^{m} {w_i \times (val[u_i] - val[v_i])^2}$ 的最小值。

分析

发现第 $i$ 个点的点权取到周围的一圈点的带权平均数最优。于是高斯消元解一下方程即可。

代码

http://zhengruioi.com/submission/52649

#include <cstdio>

const int maxn = 505;
const int maxm = 6e4 + 5;
int n, m, N, u[maxm], v[maxm], w[maxm];
int id[maxn], ID[maxn], val[maxn];
int tot, lnk[maxn], nxt[maxm], ter[maxm], wei[maxm];
double a[maxn][maxn], b[maxn], x[maxn], nv[maxn];

void addEdge(int u, int v, int w) {
    nxt[++tot] = lnk[u];
    lnk[u] = tot;
    ter[tot] = v;
    wei[tot] = w;
}

double abs(double x) {
    return x < 0 ? -x : x;
}

void gauss() {
    for (int i = 1; i <= N; i++) {
        int idx = i;
        for (int j = i + 1; j <= N; j++) {
            if (abs(a[j][i]) > abs(a[i][i])) {
                idx = j;
            }
        }
        for (int j = i + 1; j <= N; j++) {
            double d = a[j][i] / a[i][i];
            for (int k = i; k <= N; k++) {
                a[j][k] -= d * a[i][k];
            }
            b[j] -= d * b[i];
        }
    }
    for (int i = N; i >= 1; i--) {
        x[i] = b[i] / a[i][i];
        for (int j = 1; j < i; j++) {
            b[j] -= a[j][i] * x[i];
        }
    }
}

double sqr(double x) {
    return x * x;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &u[i], &v[i], &w[i]);
        if (u[i] == v[i]) continue;
        addEdge(u[i], v[i], w[i]);
        addEdge(v[i], u[i], w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &val[i]);
        if (val[i] == -1) {
            id[i] = ++N;
            ID[N] = i;
        }
    }
    for (int i = 1; i <= N; i++) {
        int u = ID[i], s = 0;
        for (int e = lnk[u]; e; e = nxt[e]) {
            s += wei[e];
        }
        a[i][i] = -1;
        for (int e = lnk[u]; e; e = nxt[e]) {
            int v = ter[e], w = wei[e];
            if (val[v] == -1) {
                a[i][id[v]] += w;
            } else {
                b[i] -= 1ll * w * val[v];
            }
        }
        for (int j = 1; j <= N; j++) {
            a[i][j] /= s;
        }
        b[i] /= s;
        a[i][i] = -1;
    }
    /*
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            printf("%lf ", a[i][j]);
        }
        printf("%lf\n", b[i]);
    }
    */
    gauss();
    for (int i = 1; i <= n; i++) {
        nv[i] = val[i];
    }
    for (int i = 1; i <= N; i++) {
        nv[ID[i]] = x[i];
    }
    double ans = 0;
    for (int i = 1; i <= m; i++) {
        ans += w[i] * sqr(nv[u[i]] - nv[v[i]]);
    }
    printf("%.9lf\n", ans);
    return 0;
}

/*
3 2
1 2 3
2 3 1
0 -1 1
*/

Coin

http://zhengruioi.com/problem/121

有一个 $n\times m$ 的棋盘,一个格子中有至多一个正面 / 反面朝上的硬币。小 $\text{M}$ 和小 $\text{D}$ 轮流操作,每次一个人可以选一个没有操作过的行 / 列,并将整行 / 列的硬币翻过来。当所有硬币正面朝上或者所有行列都被选择,游戏结束。最后一次操作的人得 $1$ 分。如果所有硬币正面朝上,小 $\text{M}$ 和小 $\text{D}$ 都会获得额外 $2$ 分的收益。如果两人都按最优策略操作,求小 $\text{M}$ 最后的得分。

分析

如果硬币不能全都正面朝上,那么答案就是 $n + m \bmod 2$。

先考虑判断硬币是否可以全部正面朝上。对于每个硬币 $(i, j)$,要求 $第\ i\ 行是否被翻过 \oplus 第\ j\ 列是否被翻过 = 硬币 (i, j) 是否反面朝上$。于是,我们使用类似二分图染色的方式即可判断。

那么如何判断先手是否必胜呢?每个连通块都是一个独立的平等游戏,所以可以考虑求它的 $\text{SG}$ 值。记一个染色后有 $a$ 个 $0$,$b$ 个 $1$ 的联通块为 $a - b$ 联通块。分情况讨论。

  • $偶 - 偶$ 联通块转移到的 $sg$ 值为 $1$,因此本身的 $sg$ 值为 $0$。
  • $奇 - 奇$ 联通块转移到的 $sg$ 值为 $0$,因此本身的 $sg$ 值为 $1$。
  • $奇 - 偶$ 联通块转移到的 $sg$ 值为 $0, 1$,因此本身的 $sg$ 值为 $2$。

最后看看所有联通块的 $sg$ 值异或起来是否为 $0$ 即可。

代码

http://zhengruioi.com/submission/52703

#include <cstdio>

const int maxn = 105;
const int maxv = 205;
const int maxe = 20005;
int T, n, m, a[maxn][maxn];
int tot, nxt[maxe], lnk[maxv], ter[maxe], wei[maxe];
int col[maxv], cnt, sg[maxn], xs;
char s[maxn];

void addEdge(int u, int v, int w) {
    nxt[++tot] = lnk[u];
    lnk[u] = tot;
    ter[tot] = v;
    wei[tot] = w;
}

bool dfs(int u, int &x, int &y) {
    if (col[u] == 0) {
        x++;
    } else {
        y++;
    }
    for (int e = lnk[u], v, w; e; e = nxt[e]) {
        v = ter[e], w = wei[e];
        if (col[v] == -1) {
            col[v] = col[u] ^ w;
            if (dfs(v, x, y) == true) {
                return true;
            }
        } else if (col[v] != (col[u] ^ w)) {
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            for (int j = 1; j <= m; j++) {
                a[i][j] = s[j] == 'e' ? -1 : s[j] == 'o' ? 0 : 1;
            }
        }
        tot = 0;
        for (int i = 1; i <= n + m; i++) {
            lnk[i] = 0;
            col[i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] != -1) {
                    addEdge(i, j + n, a[i][j]);
                    addEdge(j + n, i, a[i][j]);
                }
            }
        }
        cnt = 0, xs = 0;
        for (int i = 1; i <= n + m; i++) {
            if (col[i] == -1) {
                int x = 0, y = 0;
                col[i] = 0;
                if (dfs(i, x, y) == true) {
                    printf("%d\n", (n + m) & 1);
                    goto theEnd;
                } else {
                    if (x % 2 == 0 && y % 2 == 0) {
                        sg[++cnt] = 0;
                    } else if (x % 2 == 1 && y % 2 == 1) {
                        sg[++cnt] = 1;
                    } else {
                        sg[++cnt] = 2;
                    }
                }
            }
        }
        for (int i = 1; i <= cnt; i++) {
            xs ^= sg[i];
        }
        if (xs == 0) {
            puts("2");
        } else {
            puts("3");
        }
        theEnd:;
    }
    return 0;
}

/*
1
2 5
exexe
xeoex
*/

普及组五连测day3~day5题解

2018-10-26 15:39:35 By harryhe

ZROI 暑期D班7.26考试C题 有出处!!

2018-07-26 18:20:47 By harryhe

ZR day 1 题解

2018-07-23 19:57:46 By harryhe
共 4 篇博客