题解 | #和的期望#
和的期望
https://ac.nowcoder.com/acm/contest/71320/A
A
数学
对于选择k个，期望可以写作∑(ai+..ak)/(n..n-k+1),对于分子的求和，考虑每个元素的出现次数，在所有的情况中,乘法定理可以说明ai共出现了k(n-1..n-k+1)次，与分母约简后，可以化简为 k/n∑ai,对于除法，使用费马小定理保证，a/bmodp=a*b^mod-2,次方利用快速幂进行计算。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define maxx 310000
#define mod 998244353
#define int long long
int all[maxx];
int v,e,k,a,b,n,m,t,x,y,l,r,neww,neww1,w,ans,x1,x2;
int sum;
int poww(int i,int j)
{
if(j==0) return 1;
if(j==1) return i%mod;
int q=poww(i,j/2);
if(j%2==0) return (q*q)%mod;
else return ((q*q)%mod*i%mod)%mod;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>all[i];
sum=(sum+all[i])%mod;
}
for(int i=1;i<=n;++i)
cout<<((i%mod*sum%mod)%mod*poww(n,mod-2))%mod<<" ";
}
B
动态规划
约定0为A，1是B。
dp[i][j]表示已被(j+1)%2捡走了当前位置的，到树根的最大/小值(0/1),dp1[i][j]表示以i的子孙为根的dp[i][j]的最小/最大值，后者用于前者的转移。
然后依照题目所述进行转移，其中到子孙的每一个位置直接使用dp1[i][(j+1)%2]一步代替,转移顺序可以由深到浅，深度可以dfs计算。
输出dp[1][0]
#include<bits/stdc++.h>
using namespace std;
#define INF 1e20
#define maxx 310000
#define mod 998244353
#define int long long
int dp[maxx][2];
int dp1[maxx][2];
int val[maxx];
int fa[maxx];
int v,e,k,a,b,n,m,t,x,y,l,r,neww,neww1,w,ans,x1,x2;
int sum,mxc;
vector<int> G[maxx];
vector<int> ceng[maxx];
void dfs(int i,int cg)
{
ceng[cg].push_back(i);
mxc=max(mxc,cg);
for(int j=0;j<G[i].size();++j)
dfs(G[i][j],cg+1);
}
void solve()
{
for(int i=mxc;i>=1;--i)
for(int j=0;j<ceng[i].size();++j)
{
int x=ceng[i][j];
dp[x][0]=dp1[x][0]=INF;
dp[x][1]=dp1[x][1]=-INF;
}
for(int i=mxc;i>=1;--i)
for(int j=0;j<ceng[i].size();++j)
{int x=ceng[i][j];
for(int k=0;k<G[x].size();++k)
{dp[x][0]=min(dp[G[x][k]][0],dp[x][0]);
dp[x][1]=max(dp[G[x][k]][1],dp[x][1]);
}
if(G[x].size()==0)
{
dp[x][0]=dp1[x][0]=-val[x];
dp[x][1]=dp1[x][1]=val[x];
continue;
}
dp1[x][0]=dp[x][1]-val[x];
dp1[x][1]=dp[x][0]+val[x];
dp[x][0]=min(dp1[x][0],dp[x][0]);
dp[x][1]=max(dp1[x][1],dp[x][1]);
}
}
signed main()
{
cin>>t;
for(int i=1;i<=t;++i)
{
cin>>n;
for(int i=2;i<=n;++i) cin>>val[i];
for(int i=2;i<=n;++i)
{cin>>fa[i];
G[fa[i]].push_back(i);
}
dfs(1,1);
solve();
cout<<dp1[1][0]<<"\n";
for(int i=1;i<=mxc;++i)
ceng[i].clear();
for(int i=1;i<=n;++i)
G[i].clear();
}
}
树的直径...
，那举办了
投递小米集团等公司10个岗位
韶音科技开奖67人在聊