最后一场多校模拟赛，好像是信心赛？？不过考的不行。。最近难题比较多，对题目的难度把握不够好，经常出现简单题跳过的现象。
100+100+20+40
T1 签到题（qiandao）如果一个点的度数不是 c 的倍数，那么它的贡献至少为 1。我们一定可以构造出一种方案，使得度数是 c 的倍数的点的贡献为 0，其余的点的贡献为 1。这可以简单网络流证明，留给读者练习。
整了会这个二分图，推了好多个例子，貌似按照上面的说法都能调整出来。然后尝试着打了这10行代码，大样例一发带过。心里还是很虚但是并不会其他办法。现在正在尝试证明。
#include<bits/stdc++.h> #define N 1000500 using namespace std; int c,k,n,m,du1[N],du2[N],ans; signed main() { freopen("qiandao.in","r",stdin); freopen("qiandao.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&c); for(int i=1;i<=k;++i) { int u,v;scanf("%d%d",&u,&v); ++du1[u];++du2[v]; } for(int i=1;i<=n;++i)if(du1[i]%c)++ans; for(int i=1;i<=m;++i)if(du2[i]%c)++ans; printf("%d\n",ans); } T2 M 弟娃（magic）考虑对于一对点，将哪些点作为根会使这对点产生贡献。现在假定 1 为实际根，分两种情况：若这两个点不是祖先儿子关系，则将根选在两个点的子树里时，这对点会产生贡献；若这两个点是祖先儿子关系，令深度较深的点为 x，较浅的为 y，y 在这条链上的儿子为 z，则将根选在 x 的子树里，或是不在 z 的子树里时，这对点会产生贡献。求出 dfs 序，相当于我们只需要支持区间加，全局 max 即可。
这题读完题基本上就会了，但是思路上一个小细节调了会。
#include<bits/stdc++.h> #define N 300500 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int n,m,q,head[N],dep[N],top[N],siz[N],fa[N],dfn[N],son[N],tot,cnt,f[N][18]; const int jie=17; struct jj {int to,nxt;}bian[N<<1]; struct segment_Tree {int tag,maxn;}tree[N<<2]; inline void add(int u,int v) { bian[++tot].to=v; bian[tot].nxt=head[u]; head[u]=tot; } void dfs1(int x,int ff) { fa[x]=f[x][0]=ff;son[x]=-1;siz[x]=1;dep[x]=dep[ff]+1;dfn[x]=++cnt; for(int i=1;i<=jie and f[x][i-1];++i)f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x];i;i=bian[i].nxt) { int v=bian[i].to; if(v==ff)continue; dfs1(v,x); siz[x]+=siz[v]; if(son[x]==-1 or siz[son[x]]<siz[v])son[x]=v; } } inline int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=jie;i>=0;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; for(int i=jie;i>=0;--i) if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return fa[x]; } inline int get(int x,int y) { for(int i=jie;i>=0;--i)if(dep[f[y][i]]>dep[x])y=f[y][i]; return y; } #define int register int inline void pushup(int x) {tree[x].maxn=max(tree[x<<1].maxn,tree[x<<1|1].maxn);} inline void pushdown(int x) { tree[x<<1].maxn+=tree[x].tag; tree[x<<1].tag+=tree[x].tag; tree[x<<1|1].maxn+=tree[x].tag; tree[x<<1|1].tag+=tree[x].tag; tree[x].tag=0; } void update(int x,int l,int r,int L,int R,int val) { if(l>=L and r<=R) { tree[x].maxn+=val; tree[x].tag+=val; return ; } if(tree[x].tag!=0)pushdown(x); int mid=(l+r)>>1; if(mid<R)update(x<<1|1,mid+1,r,L,R,val); if(mid>=L)update(x<<1,l,mid,L,R,val); pushup(x); } signed main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); n=read();q=read(); for(int i=1;i<n;++i) { int u,v; u=read();v=read(); add(u,v);add(v,u); } dfs1(1,0); for(int i=1;i<=q;++i) { int x,y; x=read();y=read(); int lca=LCA(x,y); if(x==y)update(1,1,n,1,n,1); else if(lca==x) { update(1,1,n,dfn[y],dfn[y]+siz[y]-1,1); update(1,1,n,1,n,1); int del=get(x,y); update(1,1,n,dfn[del],dfn[del]+siz[del]-1,-1); } else if(lca==y) { update(1,1,n,dfn[x],dfn[x]+siz[x]-1,1); update(1,1,n,1,n,1); int del=get(y,x); update(1,1,n,dfn[del],dfn[del]+siz[del]-1,-1); } else { update(1,1,n,dfn[x],dfn[x]+siz[x]-1,1); update(1,1,n,dfn[y],dfn[y]+siz[y]-1,1); } printf("%d\n",tree[1].maxn); } } T3 变异大老鼠（arrest）考虑 SPT 上树形 dp。fi,j 表示在以 i 为根的子树中，总共放了 j 个警察，逮捕到杨吞天的最大概率。枚举当前节点放几个警察正常树形 dp 转移。
难度判断错误，读题忽略了路径唯一，自己把题目想复杂了，其实就是个傻逼背包。
#include<bits/stdc++.h> using namespace std; int dis[310][310],n,m,num,tong[310][310],cnt; double gai[310],ans[310][310],dp[310][310],tmp[310][310],lst,lin[310][310],base[310][310],ds[310]; vector<int>p[310],pp[310]; bool vis[310]; inline void dfs(int x,int fa) { for(int i=1;i<=num;++i)dp[x][i]=ans[x][i]; for(int i=0;i<=num;++i)tmp[x][i]=0; for(auto i:pp[x]) { dfs(i,x); for(int j=0;j<=num;++j)lin[x][j]=tmp[x][j]; for(int k=0;k<=num;++k)for(int j=0;j+k<=num;++j)lin[x][j+k]=max(lin[x][j+k],tmp[x][j]+dp[i][k]); for(int j=0;j<=num;++j)tmp[x][j]=lin[x][j]; } if(pp[x].size()) { for(int i=0;i<=num;++i)lin[x][i]=dp[x][i]; for(int i=0;i<=num;++i)for(int j=0;j+i<=num;++j)lin[x][i+j]=max(lin[x][i+j],dp[x][i]+(1-ans[x][i])*tmp[x][j]/(1.0*pp[x].size())); for(int i=0;i<=num;++i)dp[x][i]=lin[x][i]; } } signed main() { freopen("arrest.in","r",stdin); freopen("arrest.out","w",stdout); memset(dis,0x3f3f3f3f,sizeof(dis)); memset(base,0x3f3f3f3f,sizeof(base)); scanf("%d%d%d",&n,&m,&num); for(int i=1;i<=m;++i) { int u,v,w;scanf("%d%d%d",&u,&v,&w); dis[u][v]=dis[v][u]=base[u][v]=base[v][u]=min(dis[u][v],w); if(u!=v)tong[u][v]=tong[v][u]=1,p[u].push_back(v),p[v].push_back(u); } for(int i=1;i<=n;++i) { dis[i][i]=0;base[i][i]=0; for(int j=1;j<=num;++j)scanf("%lf",&ans[i][j]); } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j and j!=k and i!=k and dis[i][j]>dis[i][k]+dis[k][j]) { dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j]; } gai[1]=1;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(dis[1][j]+base[i][j]==dis[1][i] and i!=j and tong[i][j]) { if(j==1 and base[i][j]!=dis[i][j])continue; pp[j].push_back(i); } dfs(1,0); for(int i=0;i<=num;++i)lst=max(lst,dp[1][i]); printf("%.6lf\n",lst); } T4 朝鲜时蔬（vegetable）