期望得分：45+0+10=55
实际得分：45+0+0=45
T1
状压非常好写，但是没正解好写
\(\begin{gather*}
E(1号猎人死的轮数)&=E(1号之前死的猎人数)+1\&= \sum^n_{i=2} E(i在1号之前死)+1 \&=\sum^{n}_{i=2}p(i在1号之前死)*1+1
\end{gather*}\)
每个猎人在1之前死的概率为\(\frac{w[i]}{w[1]+w[i]}\)
T2
发现肯定是先放法术再用符咒
权值线段树维护区间最左边的1,最右边的1,中间连续1的最大值，然后一路上去，边合并边统计
代码
T1
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=10000011;
const int mod=998244353;
int n,w[N];
int ans;
inline int read()
{
int s=0;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s;
}
int fma(int x,int y)
{
int as=1;
while(y)
{
if(y&1)
as=as*x%mod;
x=x*x%mod;
y>>=1;
}
return as;
}
signed main()
{
n=read();
int p=0;
int tot=1;
for(int i=1;i<=n;i++)
w[i]=read();
for(int i=2;i<=n;i++)
p=(p+fma(w[i]+w[1],mod-2)*w[i]%mod)%mod;
cout<<p+1<<endl;
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
const int N=100011;
struct qxxx{
int v,next;
}cc[N];
struct tree{
int l1,r1;
int maxx;
int lc,rc;
}tre[80*N];
int n,m,q;
int first[N],cnt;
int root[N],tot;
int ans[N];
inline int read()
{
int s=0;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s;
}
void qxx(int u,int v)
{
cc[++cnt].v=v;
cc[cnt].next=first[u];
first[u]=cnt;
return;
}
inline int max_(int a,int b)
{
return a<b?b:a;
}
void updata(int i)
{
tre[i].r1=max_(tre[tre[i].rc].r1,tre[tre[i].lc].r1);
tre[i].l1=(tre[i].lc?tre[tre[i].lc].l1:tre[tre[i].rc].l1);
tre[i].maxx=max_(tre[tre[i].rc].l1-(tre[i].lc?tre[tre[i].lc].r1:0x7ffffff)-1,max_(tre[tre[i].lc].maxx,tre[tre[i].rc].maxx));
return;
}
void insert(int &i,int l,int r,int x)
{
if(!i)
i=++tot;
if(l==r)
{
tre[i].l1=tre[i].r1=x;
return;
}
int mid=(l+r)>>1;
if(mid>=x)
insert(tre[i].lc,l,mid,x);
else
insert(tre[i].rc,mid+1,r,x);
updata(i);
return;
}
int merge(int p,int q,int l,int r)
{
if(!p)
return q;
if(!q)
return p;
if(l==r)
return p;
int mid=(l+r)>>1;
tre[p].lc=merge(tre[p].lc,tre[q].lc,l,mid);
tre[p].rc=merge(tre[p].rc,tre[q].rc,mid+1,r);
updata(p);
return p;
}
void dfs(int x)
{
for(int i=first[x];i;i=cc[i].next)
{
dfs(cc[i].v);
root[x]=merge(root[x],root[cc[i].v],1,m);
}
int qhz=(tre[root[x]].l1-1)+(m-tre[root[x]].r1);
ans[x]=max(qhz,tre[root[x]].maxx);
if((!tre[root[x]].l1)&&(!tre[root[x]].r1))
ans[x]=-1;
return;
}
int main()
{
int x,y;
n=read();
m=read();
q=read();
for(int i=1;i<n;i++)
{
x=read();
y=read();
qxx(x,y);
}
for(int i=1;i<=q;i++)
{
x=read();
y=read();
insert(root[x],1,m,y);
}
dfs(1);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}