Kalorona

概率 & 数学期望

目录

  • 概述
  • 概率
    • 概率相关的概念
    • 概率的意义
    • 同时发生的概率
    • 概率的公理 & 命题
    • 条件概率
      • 概念
      • 全概率公式
      • 贝叶斯公式
      • 例题
    • 随机变量
    • 概率在 OI 中的应用
  • 数学期望
    • 数学期望的概念
    • 数学期望的线性性 & 递推
    • 数学期望在 OI 中的应用

Continue reading →

一月份总结

文化课

这个月算是狠狠补了一下文化课，数学的成绩还有待提高（这是最令我伤心的事情），英语仍然处于玄学状态，理科全部及格（对，我现在垃圾到只能寻求及格的状态了），生物 90 分令我很开心，因为周练的时候还是 68 分。不得不说这次卷子真的过年性质很明显了。

语文令人窒息，不做评价。

历史竟然混到了 30 分。Hmmm…

OI

小山整把济南围了个圈儿，只有北边缺着点口儿。这一圈小山在冬天特别可爱，好像是把济南放在一个小摇篮里，它们安静不动地低声地说：“你们放心吧，这儿准保暖和。”真的，济南的人们在冬天是面上含笑的。他们一看那些小山，心中便觉得有了着落，有了依靠。他们由天上看到山上，便不知不觉地想起：“明天也许就是春天了吧？这样的温暖，今天夜里山草也许就绿起来了吧？”就是这点幻想不能一时实现，他们也并不着急，因为这样慈善的冬天，干啥还希望别的呢！——《济南的冬天》，老舍

从雅礼回来之后就没有怎么碰过 OI 了，第一周和第二周借着打比赛的名义偷偷写了很多题，但是临近期末考试，我妈直接把我禁赛了，所以就一心往文化课里扑。

人生需要爆零，高中更应如此。——@callG

之后就是和 TURX 来清北澡堂集训了，对于我这种菜鸡来讲肯定是来受虐的。每天都有很多听不懂的神仙东西，神仙们像是来上复习课一样切题。在这里我深切地意识到了我和他们的差距，我会采取行动来弥补的，即使这是困难的、有风险性的。

不过还是很开心的，天天写代码是我梦寐以求的状态，新东西不断出现牵引着我进行学习。我不相信菜无法被弥补。WC2019 虽然跟我关系呢不大，但是当我看到了我省的获奖情况，我认识到了严峻性。只有努力才能克服啊。看到学长们没有获得非常理想的成绩，说实话，我第一反应就是觉得非常的惋惜，第二反应就是背后一凉了。哪个不是比我优秀啊，难道江西人就真的逃不过这一劫吗？不思进取的师大附中肯定帮不了我什么了，我只能自力更生。说实话，我觉得我会一直后悔我中考时没长眼睛。要是没有 XG、CrazyDave、lornd 等巨佬，我可能真的有把我眼睛扣下来的冲动。

变化

这一段时间看到一些政策的变动，和一些不和谐的声音在社会上流动。我和家庭也探讨过到底如何选择。我认为，高中的这个三年非常重要，升学的压力在中国是最大的。很多人认为升学才是最重要的，高中三年全然变成了升学的三年，无疑是最灰色的时期。

我选择不让我后悔的。认识 FZOI 的神仙、与他们一起学习我觉得一点都不后悔。

I am just doing my thing in my way. That is how human beings work.

P3846:「TJOI2007」可爱的质数题解

BSGS 算法模板题

有\(a^{x} \equiv b (mod \; p)\)，求\(x\)的值。我们可以来推下这个式子，首先，这个\(x \in [0, p]\)，我们可以设\(x=im-j\)，其中\(m=\lceil \sqrt{p} \rceil\)。显然，\(j \in [0, m], i \in [1, m]\)。式子变成这个样子：

\[a^{im}\equiv a^j b (mod \; p)\]

然后我们只需要求出后半部分，压入 map 中，再枚举前半部分即可求出。

代码

// P3846.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p, a, b;
ll quick_power(ll base, ll tim)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
map<ll, ll> hashTable;
int main()
{
    scanf("%lld%lld%lld", &p, &a, &b);
    a %= p;
    if (a == 0)
    {
        if (b == 0)
            printf("0");
        else
            printf("no solution");
        return 0;
    }
    hashTable.clear();
    ll m = ceil(sqrt(p));
    for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
        hashTable[x * b % p] = j;
    ll unit = quick_power(a, m);
    for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
        if (hashTable.count(x))
        {
            printf("%lld", i * m - hashTable[x]);
            return 0;
        }
    printf("no solution");
    return 0;
}

P2891:「USACO2007OPEN」吃饭 Dining 题解

思路

一道比较裸的最大流。我们创建源点\(s=0\)，让食物从源点连边到每一个牛，牛再创建副本节点（当然主节点和副本节点联通，这样保证只吃一个）连接饮料节点，在连接到汇点。求最大流即可。

代码

// P2891.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000, MAX_M = 10000, INF = 0x3f3f3f3f;
int head[MAX_N], current, n, f, d, tot, dep[MAX_N], s, t, tmp;
struct edge
{
    int to, nxt, weight;
} edges[MAX_M << 1];
void addpath(int u, int v, int w)
{
    edges[current].to = v, edges[current].nxt = head[u];
    edges[current].weight = w, head[u] = current++;
}
void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); }
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    do
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && !dep[edges[i].to])
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);

    } while (!q.empty());
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0)
        {
            int to = edges[i].to;
            int di = dfs(to, min(flow, edges[i].weight));
            if (di > 0)
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
        }
    return 0;
}
int dinic()
{
    int ans = 0;
    while (bfs())
        while (int di = dfs(s, INF))
            ans += di;
    return ans;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &f, &d);
    s = 0, t = n * 2 + f + d + 1;
    for (int i = 1; i <= f; i++)
        add(s, i, 1);
    for (int i = 1; i <= n; i++)
        add(i + f, i + f + n, 1);
    for (int i = 1; i <= d; i++)
        add(i + 2 * n + f, t, 1);
    for (int i = 1; i <= n; i++)
    {
        int fm, dm;
        scanf("%d%d", &fm, &dm);
        while (fm--)
            scanf("%d", &tmp), add(tmp, i + f, 1);
        while (dm--)
            scanf("%d", &tmp), add(f + i + n, tmp + 2 * n + f, 1);
    }
    printf("%d", dinic());
    return 0;
}

 

HDU3062:Party 题解

思路

一道裸的 2-SAT 模型题，可以作为模板题使用。我们来分析一下：假如第\(i\)对夫妻中的丈夫和第\(j\)对夫妻中的妻子有矛盾，那么说明第\(i\)对夫妻中的丈夫可以和第\(j\)对夫妻中的丈夫坐在一起，或是第\(i\)对夫妻中的妻子可以和第\(j\)对夫妻中的妻子坐在一起。这两种都可以对答案做贡献，所以连边。

连边之后运行 Tarjan，对联通块进行染色。如果对于任意一对夫妻在一个联通块中，那么方案不可行。因为夫妻在一个联通块意味着矛盾总会发生。

代码

// HDU-3062.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30000;
int head[MAX_N], current, n, m, tmp, st[MAX_N], cur, dfn[MAX_N], low[MAX_N], tot;
int color[MAX_N], ctot;
bool inst[MAX_N];
struct edge
{
    int to, nxt;
} edges[4000400];
void addpath(int u, int v)
{
    edges[current].to = v, edges[current].nxt = head[u];
    head[u] = current++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot, inst[u] = true;
    st[++cur] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!dfn[edges[i].to])
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        ctot++;
        do
        {
            inst[st[cur]] = false, color[st[cur]] = ctot;
        } while (u != st[cur--]);
    }
}
bool solve()
{
    for (int i = 0; i < 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 0; i < 2 * n; i += 2)
        if (color[i] == color[i + 1])
            return false;
    return true;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset(head, -1, sizeof(head)), memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low)), memset(color, 0, sizeof(color));
        memset(st, 0, sizeof(st)), memset(inst, 0, sizeof(inst));
        for (int i = 1; i <= m; i++)
        {
            int a1, a2, c1, c2;
            scanf("%d%d%d%d", &a1, &a2, &c1, &c2);
            // reverse the relationship;
            addpath(2 * a1 + c1, 2 * a2 + 1 - c2);
            addpath(2 * a2 + c2, 2 * a1 + 1 - c1);
        }
        if (solve())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}