前言
这辈子第一次 \(rk~1\) 。
-
\(T1：\)
概率期望，本来没学过，现学的（蓝书没看懂，还是网上的博客好理解），然后发现毕竟 \(T1\) 没那么难，知道概率期望是啥还是能做的。
-
\(T2：\)
本来看 \(T1\) 概率期望想先开 \(T2\) 的，但是发现不会就去学概率期望了，后来发现树形 \(DP\) 可做，本来想贪心的但是没贪出来，听说可以贪心做法。
-
\(T3,T4：\)
没啥好说的，不会。
但是 \(T3\) 输出 \(q\) 个 \(0\) 即可得 \(1\) 分。
T1 南
-
原题：
-
前言：
本来对概率期望仅限于了解，根本不会……
但是 \(T1\) 就不会非常不甘心，开下面的题发现也不太会 \(qwq\) 。
于是就去网上找博客现学了一下（虽然学得十分不透彻）。
然后发现这题貌似没那么难，就基本的概率期望，唯独这个每次价格会改变比较恶心。
然后毕竟是现学的，还有个地方不明白：对于他每次价格都是 \(+1\) ，满足等差数列，那么总钱数理论上 \(=\dfrac{(num+1)num}{2}\) （\(num\) 是购买次数）才对啊，但是用这个式子连样例都过不去，请求大佬解释一下 \(qwq\) 。
-
简化题意：
有 \(n\) 类武器，每次买一把，买到每一类的概率均为 \(\dfrac{1}{n}\) ，第 \(k\) 次支付需要花 \(k\) 元，求总钱数的期望。
-
解法：
概率期望 \(+DP\)。
先思考每一次买都是 \(1\) 元的怎么搞。
那么钱数的期望就等于购买次数的期望。
-
什么是概率期望：
无语了 \(oi-wiki\) 上没找到。-
概率：
\(whk\) 那边都学过了，不解释了。
-
期望：
可以简单理解为加权平均数。
对于一个场景有 \(n\) 个事件，每个事件发生的概率为 \(p_i\) ，每件事的影响为 \(x_i\) 。
那么该场景总影响的期望即为 \(\sum\limits_{i=1}^nq_i\times x_i\) 。
-
-
购买次数的期望：
对于大多数的概率期望 \(DP\) 都是从后往前推比较好推的（现学现用了属于是）。
对于概率期望 \(DP\) 的基本概念（单指从后往前推）是： 已经……还需要……的期望。
定义 \(f_i\) 为已经购买了 \(i\) 类武器，还需要 \(f_i\) 的购买次数期望值。
那么根据定义显然 \(f_n=0\) 。
下面思考状态转移方程：
分两种情况讨论：
-
买到没有买到过的种类：
首先这种情况概率为 \(\dfrac{n-i}{n}\) 。
那么既然买到新的了，当前买到的种数就变为 \(i+1\) 了，还需要的期望值就是 \(f_{i+1}\) ，那么转移方程为：
\(f_i=\dfrac{n-i}{n}\times (f_{i+1}+1)\) 。
至于这个 \(+1\) ，这个 \(f_i\) 表示的为购买次数的期望，显然购买次数 \(+1\) 了。
-
买到之前已经买到过的种类：
首先这种情况概率为 \(\dfrac{i}{n}\) 。
买到重复的了，那么显然还是需要 \(f_i\) 的期望值，同时购买次数 \(+1\) ，那么转移方程为：
\(f_i=\dfrac{i}{n}\times (f_i+1)\) 。
最后将两个结合起来，就是：
\(f_i=\dfrac{n-i}{n}\times (f_{i+1}+1)+\dfrac{i}{n}\times (f_i+1)\) 。
需要给他化简一下，而且不化简是不行的，在程序里 \(f_i\) 还是初始值 \(0\) 呢，拿脚想在这个式子里他也不应该是 \(0\) ，所以需要化简成等式右面没有 \(f_i\) 的形式。
\(f_i=\dfrac{n-i}{n}\times (f_{i+1}+1)+\dfrac{i}{n}\times (f_i+1)\)
\(f_i=\dfrac{n-i}{n}\times f_{i+1}+\dfrac{n-i}{n}+\dfrac{i}{n}\times f_i+\dfrac{i}{n}\)
\(f_i=\dfrac{n-i}{n}\times f_{i+1}+\dfrac{i}{n}\times f_i+1\)
\(\dfrac{n-i}{n}\times f_i=\dfrac{n-i}{n}\times f_{i+1}+1\)
\(f_i=f_{i+1}+\dfrac{n}{n-i}\)
由此得出购买次数的期望。
-
那么对于所有价格都为 \(1\) 元的情况答案就是 \(f_0\) 了。
接下来思考他这个恶心的价格怎么搞。
本来想的是直接 \(\dfrac{(f_0+1)\times f_0}{2}\) 的，但是发现不对，也不知道为啥，求大佬教教。
需要一个新的数组 \(g_i\) 表示已经购买了 \(i\) 类武器，还需 \(g_i\) 的钱数期望值。
还是需要思考 \(DP\) 的本质，前面几次操作均会对本次操作产生影响。
那么每次买后都让价格 \(+1\) ，那么到第 \(i\) 次购买时价格就 \(+i\) 了，符合题面的价格要求。
思考怎么实现。
虽然说这个 \(DP\) 是从后往前推的，但是显然 \(1+2+3+4=4+3+2+1\) ，这个涨价的趋势反过来是没有影响的。
那不放把他理解成是每次购买价格 \(-1\) 。
那么对于最后一次购买，即第 \(f_0\) 次购买所花价格为 \(1\) ，同时 \(g_n=0\) 也是显然的。
那么对于第 \(i\) 次购买，他所花的价格便为 \(f_0-i+1\) 。
思路已经有了，怎么把他搞到转移方程里。
首先和上面类似的，先假设 \(a_{i}\) 表示第 \(i\) 次购买时的价格。
那么 \(g_i=\dfrac{n-i}{n}\times (g_{i+1}+a_{i+1})+\dfrac{i}{n}\times (g_i+a_i)\) 。
怎样将这个 \(a_i\) 转换一下，发现之前处理的 \(f\) 数组有用了。
第 \(i\) 次价格为 \(f_0-i+1\) ，也就是还需要买几次再加上 \(1\) ，发现恰好为 \(f_i+1\)，即 \(a_i=f_i+1\) 。
于是就有了 \(g_i=\dfrac{n-i}{n}\times (g_{i+1}+f_{i+1}+1)+\dfrac{i}{n}\times (g_i+f_i+1)\) 。
类似的化简过程，不再赘述，最后化简完是：
\(g_i=f_{i+1}+g_{i+1}+\dfrac{i}{n-i}\times f_i+\dfrac{n}{n-i}\) 。
最后输出 \(g_0\) 即可。
代码极为简单，核心代码仅有 \(4\) 行。
当然从前往后推也是可以的，可能比较不好想一点，代码甚至可以不用数组且 \(2\) 行实现，怎么打的去问 洛天依 。
-
点击查看代码（从后往前）
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n;
double f[N],g[N];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n);
for(int i=n-1;i>=0;i--)
f[i]=f[i+1]+(double)n/(double)(n-i);
for(int i=n-1;i>=0;i--)
g[i]=f[i+1]+g[i+1]+(double)i/(double)(n-i)*f[i]+(double)n/(double)(n-i);
printf("%.2f",g[0]);
}
洛天依的代码（从前往后）
//省略几十行 Fast IO。
int n;
double f,g,p;
signed main(){
cin>>n;
for(double x=1;x<=n;++x)
f+=(g+=n/x)*n/x;
printf("%.2f",f);
}
T2 昌
-
简化题意：
给定一棵 \(n\) 个节点的数，\(1\) 为根节点。
对于节点 \(i\) 有对应 \(a_i\) ：
-
若 \(a_i=1\) ，该点的值等于其子节点值中的最大值。
-
若 \(a_i=0\) ，该点的值等于其子节点值中的最小值。
设树上有 \(k\) 个叶子结点，每个节点的值可以为为 \(1\sim k\) ，每个数仅用一次，求根节点的最大值。
-
-
解法：
树形 \(DP\) 。
设节点 \(i\) 的值 \(\geq x_i\) 。
-
若 \(a_i=0\) ，则 \(i\) 的子节点的值必须全部 \(\geq x_i\) 。
-
若 \(a_i=1\) ，则最少有一个点的值 \(\geq x_i\) 。
我们设根节点的值 \(\geq x\) 。
为了根节点值最大，我们希望必须 \(\geq x\) 的叶子结点个数尽可能的少。
那么倘若我们求出必须 \(\geq x\) 的叶子结点个数 \(num\) ，则根节点的最大值即 \(k-num+1\) ，\(k\) 表示叶子结点的个数。
利用树形 \(DP\) ，定义 \(f_i\) 表示以 \(i\) 为根节点的子树中必须 \(\geq x\) 的叶子结点的个数。
那么显然，若 \(i\) 为叶子结点，则 \(f_i=1\) 。
接下来分类讨论：
-
若 \(a_i=0\) ：
因为其子节点的值必须全部 \(\geq x_i\) ，所以 \(f_u=\sum\limits_{v\in{son_u}}f_v\) 。
-
若 \(a_i=1\) ：
因为其子节点的值至少有 \(1\) 个 \(\geq x_i\) ，所以 \(f_u=\min_{\in{son_u}}f_v\) 。
由此跑 \(dfs\) ，到最后 \(f_1\) 表示所有叶子结点中必须 \(\geq x\) 的个数。
所以答案即为 \(k-f_1+1\) 。
-
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,sum,a[N],f[N];
vector<int>son[N];
void dfs(int x)
{
if(son[x].empty())
{
f[x]=1;
return ;
}
if(a[x]==1)
{
f[x]=0x3f3f3f3f;
for(int y:son[x])
{
dfs(y);
f[x]=min(f[x],f[y]);
}
}
else if(a[x]==0)
{
for(int y:son[x])
{
dfs(y);
f[x]+=f[y];
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
int x;
for(int i=2;i<=n;i++)
read(x),
son[x].push_back(i);
dfs(1);
for(int i=1;i<=n;i++)
if(son[i].empty())
sum++;
cout<<sum-f[1]+1;
}