首页 > 其他分享 >CF1874C Jellyfish and EVA 题解

CF1874C Jellyfish and EVA 题解

时间:2023-10-01 20:27:27浏览次数:40  
标签:std typedef CF1874C 题解 valueType tt EVA 移动 节点

题意

给定一个有向无环图,对于任意一条边 \((u_i, v_i)\),有 \(u_i < v_i\)。

定义一次从节点 \(u\) 开始的移动为如下过程:

  1. \(\tt{Alice}\) 选择从 \(u\) 出发的且未被删除的一条边。

  2. \(\tt{Bob}\) 在从 \(u\) 出发的且未被删除的边中等概率随机选择一条。

  3. 若两人选择的边相同,则向这条边移动,否则继续选择。

如果不存在从当前节点 \(u\) 出发且未被删除的边,那么定义此次移动是失败的。

若 \(\tt{Alice}\) 采取最优策略,求他们实现移动 \(1 \rightarrow n\) 的概率。

(\(1 \le n \le 5000\))。

题解

定义 \(f_u\) 代表从节点 \(u\) 实现移动 \(u \rightarrow n\) 的最大化概率,那么可见答案为 \(f_1\),由于特殊的边的限制,从 \(1\) 到 \(n\) 显然是一个合法的拓扑序,逆序遍历转移一定合法,下面考虑如何转移。

设 \(d = \operatorname{degree}_u\),定义从 \(u\) 出发的所有边的终点依次为 \(v_1, v_2, \cdots, v_d\),将其按 \(f_v\) 为关键字降序排列得到序列 \(v\)。

可以发现,若 \(\tt{Alice}\) 选择边的方案钦定,那么可以得出移动到每个终点的概率,设有长度为 \(d\) 的序列 \(p\),其中 \(p_1\) 表示移动到 \(v_1\) 的概率,那么我们有

\[f_u = \sum\limits_{i = 1}^{d}f_{v_i} \cdot p_i \]

那么采取最优操作的实质即为通过改变操作序列来最大化上述和式的值。

由于在任意一次选择中,每个点被 \(\tt{Bob}\) 选择的概率相等,那么显然选择 \(f\) 值最大的终点可以获得更大的概率。这样我们就得到了最优操作的策略:选择 \(f\) 值最大的终点。

设 \(g_i\) 表示在有 \(i\) 个点的情况下的最优 \(p\) 序列,那么有

\[\begin{aligned} g_1 &= \left[1.0\right] \\ g_1 &= \left[0.5, 0.0\right] \\ \end{aligned}\]

对于 \(i > 2\) 的情况,根据上述策略,我们可以发现 \(\tt{Alice}\) 第一次选择的点一定为 \(v_1\),那么我们有

\[\begin{aligned} g_{i, 1} &= \dfrac{1}{i} && (i > 1) \end{aligned}\]

对于 \(j > 1\),那么第一次显然不可能成功移动到 \(v_j\)。若最终成功移动到了 \(v_j\),那么有第一次移动一定失败且 \(v_j\) 没有被删除。那么此时我们可以从 \(i - 2\) 个节点的状态转移答案。考虑通过枚举除 \(v_1\) 外被删除的节点来实现转移,设另外一个被删除的节点为 \(v_k\),那么有

  • 若 \(j < k\),那么 \(v_j\) 从当前的第 \(j\) 优节点转化为 第 \(j - 1\) 优节点,有转移 \(g_{i, j} \leftarrow g_{i - 2, j - 1} (j < k)\)。

  • 若 \(k < j\),那么 \(v_j\) 从当前的第 \(j\) 优节点转化为 第 \(j - 2\) 优节点,有转移 \(g_{i, j} \leftarrow g_{i - 2, j - 2} (k < j)\)。

发现具体的转移与 \(k\) 无关,通过计算 \(j < k\) 的概率和 \(k > j\) 的概率即可完成转移,有转移式

\[g_{i, j} = \begin{cases} \dfrac{1}{i} & j = 1 \\ \dfrac{j - 2}{i} \times g_{i - 2, j - 2} + \dfrac{i - j}{i} \times g_{i - 2, j - 1} & \text{otherwise.} \end{cases}\]

预处理出 \(g\) 数组即可实现转移,复杂度 \(\mathcal{O}(n^2)\),可以通过本题。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef long double realType;
typedef std::vector<realType> RealVector;
typedef std::vector<RealVector> RealMatrix;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N, M;

        std::cin >> N >> M;

        RealMatrix G(N + 1, RealVector(N + 1, 0));

        for (valueType i = 1; i <= N; ++i) {
            G[i][1] = (realType) 1 / i;

            for (valueType j = 2; j <= i && i - 2 > 0; ++j)
                G[i][j] = G[i - 2][j - 2] * (j - 2) / i + G[i - 2][j - 1] * (i - j) / i;
        }

        ValueMatrix Graph(N + 1);

        for (valueType i = 0; i < M; ++i) {
            valueType u, v;

            std::cin >> u >> v;

            Graph[u].push_back(v);
        }

        RealVector F(N + 1, 0);

        F[N] = 1;

        for (valueType i = N - 1; i >= 1; --i) {
            auto const degree = (valueType) Graph[i].size();

            RealVector to;

            to.reserve(degree);

            for (auto const &iter: Graph[i])
                to.push_back(F[iter]);

            std::sort(to.begin(), to.end(), std::greater<>());

            F[i] = 0;

            for (valueType j = 1; j <= degree; ++j)
                F[i] += G[degree][j] * to[j - 1];
        }

        std::cout << std::fixed << std::setprecision(10) << F[1] << std::endl;
    }

    return 0;
}

标签:std,typedef,CF1874C,题解,valueType,tt,EVA,移动,节点
From: https://www.cnblogs.com/User-Unauthorized/p/solution-CF1874C.html

相关文章

  • P1126 机器人搬重物 题解
    Problem题目概括$n\timesm$的网格,有些格子是障碍格。\(0\)无障碍,\(1\)有障碍。机器人有体积,总是在格点上。有5种操作:向前移动\(1/2/3\)步左转\(/\)右转每次操作需要\(1\)秒。求从\(x_1,y_1\)到\(x_2,y_2\)点的最短路。机器人有一个初始方向$......
  • P1182 数列分段 Section II 题解
    Problem考察知识点:二分、贪心。题目描述对于给定的一个数组,现要将其分成\(M\)段,并要求每段连续,且每段和的最大值最小。思路二分答案出每段和最大值的最小值,然后贪心检验是否满足。难点在\(check\)上。策略:每次开始循环,如果没有超范围,就一直选,知道选满为止,求最大值。代......
  • Codeforces 1278D 题解
    题目大意题目大意给你\(n\)(\(1\leqslantn\leqslant5\cdot10^5\))条线段\([l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\)(\(1\lel_i<r_i\le2n\))。保证每条线段的端点为整数,且\(\foralli,j\)(\(i\nej\)),不存在\(l_i=l_j\)或\(r_i=r_j\),不存......
  • P5943 [POI2002] 最大的园地 题解
    题目传送门前置知识单调栈简化题意在一个\(n\timesn\)的正方形内找到最大的由\(0\)组成的子矩形的面积。解法令\(f_{i,j}(1\lei,j\len)\)表示从\((1,j)\)到\((i,j)\)中以\((i,j)\)结尾的均为\(0\)的子串长度,即\((i,j)\)上面可延伸的最大距离(子矩形的......
  • Codeforces 1702G2 题解
    题目大意给出一个大小为\(n\)的树,\(q\)次询问,每次给出一个大小为\(m\)的点集,判断是否有一条链覆盖这些点(这条链可以经过其他点)。\(n,\summ\leqslant2\cdot10^5\),\(q\leqslant10^5\)。提示提示1思考将$m$个点按深度排序。题解题解考虑将\(m\)个点按树......
  • ABC322G题解
    这场的G怎么这么毒瘤啊/kk听说正解是DP?我爆搜头一个表示不服!statement找出三元组\((S,a,b)\)的数量,使得\(S\)在\(a\)进制下和在\(b\)进制下的差为\(X\),其中\(0\leqS_i<(min(a,b,10))\)。首先因为\(X>0\)显然\(S\)不可能为\(1\)位数。如果\(S\)......
  • 「题解」Codeforces Round 895 (Div. 3)
    A.TwoVesselsProblem题目Sol&Code签到题#include<bits/stdc++.h>typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT,a,b,c;intmain(){scanf("%d"......
  • AT_abc254_h [ABC254Ex] Multiply or Divide by 2 题解
    打篇题解巩固一下。题意给你两个集合\(A\)和\(B\),对于任意\(A\)集合中的元素,我们可以进行\(2\)种操作:\(a_i\gets\left\lfloor\frac{a_i}{2}\right\rfloor\)或\(a_i\gets2\timesa_i\)。问最少要多少次才能使\(A\)和\(B\)中的元素相等。分析首先我们可以令\(a......
  • UVA12655 Trucks 题解
    题目传送门前言中文题目可以看link。前置知识Kruskal重构树|最近公共祖先简化题意给定一个\(N\)个点\(M\)条边的有向图,共有\(S\)次询问,每次询问从\(L\)到\(H\)所有的路径中最小的权值的最大值(多组数据)。本题即最大瓶颈路问题。解法使最小的权值最大,不难......
  • Aveva Marine VBNET 编程系列===>读取drawing explorer的第一层级 view
    今天我们研究下读取drawingexpolrer的第一层级:view下面的图纸的层级目录示意图,我们今天需要获取所有的view 主要用到2个方法:1#获取第一个元素MarDrafting.ElementChildFirstGetMethod() 2#获取相邻的元素MarDrafting.ElementSiblingNextGet Method  ......