这次考试，我犯了一个错误，刚开始把题面看了一遍，当时觉得应该 1，3 ,2 开题，于是就大力搞T1，把T2仍到了最后，最后也没时间写了，结果T2差不多是一道线段树裸题，但是我当时没看出来，知道考试结束前几分钟才想到一个接近正解的思路，但是没时间打了，主要原因有两点：1是之前做过一道类似的题，但是我没什么印象，显然那道题不是靠自己调出来的，以后要避免这种情况，自己多思考，2是自己对于线段树合并的认识和掌握不是很扎实，自己理解了半天才重新弄明白线段树合并到底是什么，所以对于之前学过的知识点要抽空复习。
T1 Hunter
这道题考试的时候我打了一个暴搜，也是对于这种同时有分子和分母的暴搜的一次尝试，但是我当时忘记了期望的线性性，分数累加的时候我每次都进行通分，结果数据很毒瘤，一个点都没过，全都爆了 long long ，结束后听从varuxn的建议对于结果直接进行累加，取模，拿到了自己预估的25分暴力，但是听说利用状压+记忆化可以得到45分。
思路：1 号猎人死亡的轮数等于在 1 号之前死亡的猎人数 +1, 根据期望的线性性, 就等于每个猎人比 1 号猎人先死的概率和, 不难发现第 i 个猎人比 1号猎人先死的概率是\(\frac{w_i}{w_i+w_1}\),直接一遍 for 循环即可
25pts_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define iv inline void
#define ii inline int
using namespace std;
const int mo=998244353;
const int N=1e5+10;
int n,sum;
int a[N];
bool vis[110];
struct node
{
int up,down;
};
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii ksm(int d,int z)
{
int out=1;
while(z)
{
if(z&1)
out=out*d%mo;
z>>=1;
d=d%mo*d%mo;
}
return out%mo;
}
int dfs(int p,int cnt,int u,int d,int now)
{
if(cnt==n)
return (u%mo)*(cnt%mo)%mo*(ksm(d,mo-2)%mo)%mo;
int nu=0,nd=0,nval=0;
nval=(a[1]%mo)*(cnt%mo)%mo*(ksm(now,mo-2)%mo)%mo;
for(re i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
int use=dfs(i,cnt+1,a[i],now,now-a[i]);
nval=(nval%mo)+(use%mo)%mo;
vis[i]=0;
}
}
return (u%mo)*(ksm(d,mo-2)%mo)%mo*(nval%mo)%mo;
}
signed main()
{
n=read();
for(re i=1;i<=n;i++)
{
a[i]=read();
sum+=a[i];
}
if(n==1)
{
printf("1\n");
return 0;
}
int sd=sum,su=a[1],ans=su%mo*(ksm(sum,mo-2)%mo)%mo;
for(re i=2;i<=n;i++)
{
memset(vis,0,sizeof(vis));
vis[1]=1;
vis[i]=1;
int use=dfs(i,2,a[i],sum,sum-a[i]);
ans=ans%mo+(use%mo)%mo;
}
printf("%lld\n",(ans%mo+mo)%mo);
return 0;
}
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define iv inline void
#define ii inline int
using namespace std;
const int mo=998244353;
const int N=1e5+10;
int n,sum;
int a[N];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii ksm(int d,int z)
{
int out=1;
while(z)
{
if(z&1)
out=out*d%mo;
z>>=1;
d=d%mo*d%mo;
}
return out%mo;
}
signed main()
{
n=read();
for(re i=1;i<=n;i++)
a[i]=read();
int ans=0;
for(re i=2;i<=n;i++)
ans=(ans%mo)+(a[i]%mo*(ksm(a[1]+a[i],mo-2)%mo)%mo)%mo;
printf("%lld\n",(ans%mo+mo)%mo+1);
return 0;
}
T2 Defence
这道题是我挺失败的一道题，上面已经说了，但是这道题比较简单，考完后我又复习了一遍线段树合并，这道题思路就是假设 L 是前缀 0 的数量, R 是后缀 0 的数量, M 是最长的连续 0 的数量, 显然，答案就是\(max(L+R,M)\),直接上线段树维护即可，但是注意，我刚开始对于动态开点理解没有透彻，刚开始build出了所有点，导致TLE，解决方案就是写真正的动态开点，对于没有出现过的节点直接利用信息，就是在那份 TLE的代码上改一改，那份代码比较清晰，AC代码就是把pushup函数里分情况讨论一下,建议先阅读TLE代码。
TLE_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define head heeeadd
#define next neeete
using namespace std;
const int N=1e5+10;
int n,m,q,tot,timi;
int to[N<<1],head[N],next[N<<1],root[N],out[N];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
struct Segment_Tree
{
int maxl[N*40],maxr[N*40],maxm[N*40];
int lr[N*40],rl[N*40],ml[N*40],mr[N*40];
int lc[N*40],rc[N*40];
iv pp(int rt,int l,int r)
{
#define lc lc[rt]
#define rc rc[rt]
maxl[rt]=maxl[lc];
maxr[rt]=maxr[rc];
lr[rt]=lr[lc];
rl[rt]=rl[rc];
if(maxl[lc]==mid-l+1)
{
maxl[rt]=maxl[lc]+maxl[rc];
lr[rt]=lr[rc];
}
if(maxr[rc]==r-mid)
{
maxr[rt]=maxr[rc]+maxr[lc];
rl[rt]=rl[lc];
}
maxm[rt]=maxm[lc];
ml[rt]=ml[lc];
mr[rt]=mr[lc];
if(maxm[rc]>maxm[lc])
{
maxm[rt]=maxm[rc];
ml[rt]=ml[rc];
mr[rt]=mr[rc];
}
if(maxr[lc]+maxl[rc]>maxm[rt])
{
maxm[rt]=maxr[lc]+maxl[rc];
ml[rt]=rl[lc];
mr[rt]=lr[rc];
}
#undef lc
#undef rc
}
ii insert(int rt,int l,int r,int p)
{
#define lc lc[rt]
#define rc rc[rt]
if(!rt)
rt=++timi;
if(l==r)
{
maxl[rt]=maxr[rt]=maxm[rt]=0;
lr[rt]=l-1;
rl[rt]=l+1;
ml[rt]=l+1;
mr[rt]=l-1;
return rt;
}
if(mid>=p)
lc=insert(lc,l,mid,p);
else
rc=insert(rc,mid+1,r,p);
pp(rt,l,r);
#undef lc
#undef rc
return rt;
}
ii build(int rt,int l,int r)
{
#define lc lc[rt]
#define rc rc[rt]
if(!rt)
rt=++timi;
maxl[rt]=maxr[rt]=maxm[rt]=r-l+1;
lr[rt]=r;
rl[rt]=l;
ml[rt]=l;
mr[rt]=r;
if(l==r)
return rt;
lc=build(lc,l,mid);
rc=build(rc,mid+1,r);
pp(rt,l,r);
#undef lc
#undef rc
return rt;
}
ii merge(int p,int q,int l,int r)
{
if((!p)||(!q))
return p+q;
if(l==r)
{
if(!maxm[q])
{
maxl[p]=maxr[p]=maxm[p]=0;
lr[p]=l-1;
rl[p]=l+1;
ml[p]=l+1;
mr[p]=l-1;
}
return p;
}
lc[p]=merge(lc[p],lc[q],l,mid);
rc[p]=merge(rc[p],rc[q],mid+1,r);
pp(p,l,r);
return p;
}
ii query(int rt,int l,int r)
{
return max(maxl[rt]+maxr[rt],maxm[rt]);
}
}T;
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
iv dfs(int st)
{
for(re i=head[st];i;i=next[i])
{
int p=to[i];
dfs(p);
root[st]=T.merge(root[st],root[p],1,m);
}
out[st]=T.query(root[st],1,m);
}
int main()
{
n=read();
m=read();
q=read();
int u,v;
for(re i=1;i<n;i++)
{
u=read();
v=read();
add(u,v);
}
for(re i=1;i<=n;i++)
root[i]=T.build(root[i],1,m);
for(re i=1;i<=q;i++)
{
u=read();
v=read();
root[u]=T.insert(root[u],1,m,v);
}
dfs(1);
for(re i=1;i<=n;i++)
if(T.maxm[root[i]]!=m) printf("%d\n",out[i]);
else printf("-1\n");
return 0;
}
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define head heeeadd
#define next neeete
using namespace std;
const int N=1e5+10;
int n,m,q,tot,timi;
int to[N<<1],head[N],next[N<<1],root[N],out[N];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
struct Segment_Tree
{
int maxl[N*40],maxr[N*40],maxm[N*40];
int lr[N*40],rl[N*40],ml[N*40],mr[N*40];
int lc[N*40],rc[N*40];
iv pp(int rt,int l,int r)
{
#define lc lc[rt]
#define rc rc[rt]
if(lc and rc)
{
maxl[rt]=maxl[lc];
maxr[rt]=maxr[rc];
lr[rt]=lr[lc];
rl[rt]=rl[rc];
if(maxl[lc]==mid-l+1)
{
maxl[rt]=maxl[lc]+maxl[rc];
lr[rt]=lr[rc];
}
if(maxr[rc]==r-mid)
{
maxr[rt]=maxr[rc]+maxr[lc];
rl[rt]=rl[lc];
}
maxm[rt]=maxm[lc];
ml[rt]=ml[lc];
mr[rt]=mr[lc];
if(maxm[rc]>maxm[lc])
{
maxm[rt]=maxm[rc];
ml[rt]=ml[rc];
mr[rt]=mr[rc];
}
if(maxr[lc]+maxl[rc]>maxm[rt])
{
maxm[rt]=maxr[lc]+maxl[rc];
ml[rt]=rl[lc];
mr[rt]=lr[rc];
}
}
else if(lc)
{
maxl[rc]=(r-mid);
maxr[rc]=(r-mid);
maxm[rc] =(r-mid);
ml[rc] =mid+1;
mr[rc] =r;
lr[rc] =r;
rl[rc] =(mid+1);
maxl[rt]=maxl[lc];
maxr[rt]=maxr[rc];
lr[rt]=lr[lc];
rl[rt]=rl[rc];
if(maxl[lc]==mid-l+1)
{
maxl[rt]=maxl[lc]+maxl[rc];
lr[rt]=lr[rc];
}
if(maxr[rc]==r-mid)
{
maxr[rt]=maxr[rc]+maxr[lc];
rl[rt]=rl[lc];
}
maxm[rt]=maxm[lc];
ml[rt]=ml[lc];
mr[rt]=mr[lc];
if(maxm[rc]>maxm[lc])
{
maxm[rt]=maxm[rc];
ml[rt]=ml[rc];
mr[rt]=mr[rc];
}
if(maxr[lc]+maxl[rc]>maxm[rt])
{
maxm[rt]=maxr[lc]+maxl[rc];
ml[rt]=rl[lc];
mr[rt]=lr[rc];
}
maxl[rc]=0;
maxr[rc]=0;
maxm[rc] =0;
ml[rc] =0;
mr[rc] =0;
lr[rc] =0;
rl[rc] =0;
}
else if(rc)
{
maxl[lc]=mid-l+1;
maxr[lc]=mid-l+1;
maxm[lc] =mid-l+1;
ml[lc] =l;
mr[lc] =mid;
lr[lc] =mid;
rl[lc] =l;
maxl[rt]=maxl[lc];
maxr[rt]=maxr[rc];
lr[rt]=lr[lc];
rl[rt]=rl[rc];
if(maxl[lc]==mid-l+1)
{
maxl[rt]=maxl[lc]+maxl[rc];
lr[rt]=lr[rc];
}
if(maxr[rc]==r-mid)
{
maxr[rt]=maxr[rc]+maxr[lc];
rl[rt]=rl[lc];
}
maxm[rt]=maxm[lc];
ml[rt]=ml[lc];
mr[rt]=mr[lc];
if(maxm[rc]>maxm[lc])
{
maxm[rt]=maxm[rc];
ml[rt]=ml[rc];
mr[rt]=mr[rc];
}
if(maxr[lc]+maxl[rc]>maxm[rt])
{
maxm[rt]=maxr[lc]+maxl[rc];
ml[rt]=rl[lc];
mr[rt]=lr[rc];
}
maxl[lc]=0;
maxr[lc]=0;
maxm[lc] =0;
ml[lc] =0;
mr[lc] =0;
lr[lc] =0;
rl[lc] =0;
}
#undef lc
#undef rc
}
ii insert(int rt,int l,int r,int p)
{
#define lc lc[rt]
#define rc rc[rt]
if(!rt)
rt=++timi;
if(l==r)
{
maxl[rt]=maxr[rt]=maxm[rt]=0;
lr[rt]=l-1;
rl[rt]=l+1;
ml[rt]=l+1;
mr[rt]=l-1;
return rt;
}
if(mid>=p)
lc=insert(lc,l,mid,p);
else
rc=insert(rc,mid+1,r,p);
pp(rt,l,r);
#undef lc
#undef rc
return rt;
}
ii merge(int p,int q,int l,int r)
{
if((!p)||(!q))
return p+q;
if(l==r)
{
if(!maxm[q])
{
maxl[p]=maxr[p]=maxm[p]=0;
lr[p]=l-1;
rl[p]=l+1;
ml[p]=l+1;
mr[p]=l-1;
}
return p;
}
lc[p]=merge(lc[p],lc[q],l,mid);
rc[p]=merge(rc[p],rc[q],mid+1,r);
pp(p,l,r);
return p;
}
ii query(int rt,int l,int r)
{
return max(maxl[rt]+maxr[rt],maxm[rt]);
}
}T;
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
iv dfs(int st)
{
for(re i=head[st];i;i=next[i])
{
int p=to[i];
dfs(p);
root[st]=T.merge(root[st],root[p],1,m);
}
out[st]=T.query(root[st],1,m);
}
int main()
{
n=read();
m=read();
q=read();
int u,v;
for(re i=1;i<n;i++)
{
u=read();
v=read();
add(u,v);
}
for(re i=1;i<=q;i++)
{
u=read();
v=read();
root[u]=T.insert(root[u],1,m,v);
}
dfs(1);
for(re i=1;i<=n;i++)
if(root[i]) printf("%d\n",out[i]);
else printf("-1\n");
return 0;
}
T3 connect
一道状压好题，思路是：1 号点到 N 的路径唯一相当于存在一条 1 到 N 的链, 并且不在链上的每个联通块最多只和链上的一个点有连边.考虑状压 DP, 记录当前考虑的点集和链的末端点, 转移有两种, 一种是让链的长度增加 1, 另一种是添加一个点集并接到当前链的末端点.那我们设 \(f_{i,j}\)表示当前点集为i，结尾为j的最大长度的总长度之和，\(val_{i,j}\)表示 i，j 之间的边权，\(sum_i\)表示状态为i的边权之和，\(bu_{i,j}\)表示在集合i中，与j相连的边权之和,那么可以得到这样的状态转移方程：
\(f_{i,j|(1<<k-1)}=max(f_{1,j|(1<<k-1)},f_{i,j}+val_j,k)\) （连到末尾）
\(f_{i|k,j}=max(f_{i|k,j},f_{i,j}+bu_{k,j}+sum_k)\)
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
int n,m,tot,S;
int f[1<<17][20];
int val[20][20],sum[1<<17],bu[1<<17][20];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
signed main()
{
n=read();
m=read();
S=1<<n;
int u,v,w;
memset(val,-1,sizeof(val));
for(re i=1;i<=m;i++)
{
u=read();
v=read();
w=read();
val[u][v]=val[v][u]=w;
}
for(re i=1;i<S;i++)
{
for(re j=1;j<=n;j++)
{
if((i>>(j-1))&1)
{
for(re k=j+1;k<=n;k++)
{
if(((i>>(k-1))&1) and (val[j][k]!=-1))
sum[i]+=val[j][k];
}
}
else
{
for(re k=1;k<=n;k++)
{
if(k==j)
continue;
if(((i>>(k-1))&1) and (val[j][k]!=-1))
bu[i][j]+=val[j][k];
}
}
}
}
for(re i=1;i<S;i++)
{
if(!(i&1)) continue;
for(re j=1;j<=n;j++)
{
if(!((i>>(j-1))&1)) continue;
for(re k=1;k<=n;k++)
{
if(!((i>>(k-1))&1) and val[j][k]!=-1)
f[i|(1<<(k-1))][k]=max(f[i|(1<<(k-1))][k],f[i][j]+val[j][k]);
}
for(re k=(S-1)^i;k;k=(k-1)&((S-1)^i))
f[i|k][j]=max(f[i|k][j],f[i][j]+sum[k]+bu[k][j]);
}
}
printf("%lld\n",sum[S-1]-f[S-1][n]);
return 0;
}