Jellyfish and EVA
EVA，出击！
算法本质
思维、dp
题目大意
给定有向图，其中保证边：
- 由编号较小点 指向 编号较大点
现在玩家和Alice一起从点1前往点n，玩家和Alice需要各自选择一条出点为当前点的边，Alice会随机选择（且玩家选择前不知道Alice的选择）：
- 选择道路一致
玩家和Alice沿着选择边前进 - 选择道路不一致
选择的两条道路被破坏
输出最大化两人抵达n点的概率。
n <= 5e3
m <= 2e5思路推演
稍加模拟可以发现，dp做法，需要从后向前推。
核心在于，假设前方存在3个点，每个点的胜率不一致，当前玩家应该如何抉择。
朴素的想，我们肯定希望尽可能地走胜率高的点，由于Alice的随机选择，核心在于计算出去不同点的概率。
稍加模拟，发现并不存在一个简单的计算规律。
但是有2个点提醒了玩家，n的范围给的相对奇怪，且每次失败会破坏2条道路。
这实际上在提示玩家使用递推的方式去计算走不同点的概率。
这里值得一提的是，在赛时，我们力求将走通概率最高的点分配给胜率高的点，实际上在计算走通概率时，完全没有必要。
我们可以计算出所有点的走通概率之后，再排序就好。当时思路不够清晰。
假设之后存在n个点可走。
首先第一个点无论如何选择，其走通概率是1/n，考虑失败的情况，则需要在剩余n-1个点中选择一个点作为同样失败的点。
如果第二个点选择的n-1个点中的第x个点，则剩余的n-2个点，就可以套用n-2的情况概率一一对应即可。
考虑x的不同还有先前概率等细节，就可以递推求出不同点的概率了。
求出之后，倒着dp即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>m;
vector<vector<double>> pi(n+5, vector<double>(n+5)); // 这里记录了胜率情况
for (int i=1; i<=n; i++) // 递推处理
{
double base = 1.0/i;
if (i%2) // 奇数层比较特殊，其胜率均分
{
for (int j=1; j<=i; j++)
pi[i][j] = base;
continue;
}
pi[i][1] = base;
int cntl=0, cntr=i-2;
for (int j=2; j<=i; j++) // 这里递推公式看着有些复杂，实际不难，可以自行推导
{
// cntl cntr表示第j个元素左右元素个数，如果去掉右侧元素，则其对应的为上一层的j-1位置，去掉左侧对应的是j-2位置
pi[i][j] = pi[i-2][j-1]*cntr + pi[i-2][j-2]*cntl; // 这里注意对应关系
pi[i][j] *= base;
cntl++, cntr--;
}
}
vector<vector<int>> g(n+5), g2(n+5); // g2记录反向图
vector<int> chu(n+5);
vector<double> dp(n+5);
while (m--)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g2[v].push_back(u);
chu[u]++;
}
dp[n] = 1;
queue<int> q;
for (int i=1; i<=n; i++)
if (chu[i]==0)
q.push(i);
while (q.size())
{
int u=q.front();
q.pop();
int num = g[u].size();
vector<double> nxt; // 下一个点的胜率
for (int v:g[u])
nxt.push_back(dp[v]);
sort(nxt.begin(), nxt.end());
nxt.push_back(0); // 维持1下标
reverse(nxt.begin(), nxt.end()); // 胜率大的在前
for (int i=1; i<=num; i++) // 当前点的胜率 = 选择下一个点的概率 * 下一个点的胜率
dp[u] += pi[num][i]*nxt[i];
for (int v:g2[u]) // 倒着向前topo
{
chu[v]--;
if (chu[v]==0)
q.push(v);
}
}
double ans = dp[1];
cout<<fixed<<setprecision(12)<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)