LibreOJ NOI Round #2-解题报告

## T1 最开始写的线段树，后来发现矩阵行列式为-1，一定有逆，于是就把线段树删了（n出2e6多好 ## T2 这题的部分分很坑爹啊...我也不理解，就照着laofu在WC上讲的课件去模拟...没想到拿了16... 还是说一下正经的16分拿法吧 我们考虑矿工和黄金需要满足树上祖先后代的关系，这可以通过dfs维护子树信息实现。我们要做的其实就是把矿工和黄金**匹配**起来，权值就是$(w_a-d_a)+(w_b+d_b)$。我们还要支持反悔，匹配完之后我们需要把$-(w_a-d_a)$也放到堆里，表示不选。我们把黄金或者反悔的矿工放在可并堆里，如果权值和$\ge 0$贪心的匹配就行了。 52(60)分做法： 注意到动态加边的费用流不做任何特殊处理是错的。那么我们就需要手动找出图里的正环，具体实现其实和16分做法差不多，但是更有了模拟费用流的感觉。我们在每个点记一下父亲往下的流量，从加入的点开始遍历整棵树，找到增广的对象即可，这里我们认为已匹配的矿工和未匹配的黄金是等价的，反之亦然。 **注意，你是在跑费用流！树边的权也要加上！** ```cpp const int N=100005; int n; int fa[N]; int head[N],cnte,v[N],nx[N],w[N]; int fe[N],dep[N]; void pfs(int x) { for(ri i=head[x];i;i=nx[i]) { fe[v[i]]=w[i],dep[v[i]]=dep[x]+1; pfs(v[i]); } } LL ans,mx; int mxk; priority_queue<int> f[N],g[N]; int lu[N]; il void upd(int x,int y) // x -> y { int t=f[x].top(); f[x].pop(),g[x].push(-t),ans+=t; t=g[y].top(); g[y].pop(),f[y].push(-t),ans+=t; while(x!=y) if(dep[x]>dep[y]) --lu[x],ans-=fe[x],x=fa[x]; else ++lu[y],ans+=fe[y],y=fa[y]; } void finde(int x,int fr,int val) { if(!g[x].empty()) { if(mx<val+g[x].top()) mx=val+g[x].top(),mxk=x; } if(fa[x]&&fr!=fa[x]&&lu[x]) finde(fa[x],x,val-fe[x]); for(ri i=head[x];i;i=nx[i]) if(v[i]!=fr) finde(v[i],x,val+w[i]); } void finds(int x,int fr,int val) { if(!f[x].empty()) { if(mx<val+f[x].top()) mx=val+f[x].top(),mxk=x; } if(fa[x]&&fr!=fa[x]) finds(fa[x],x,val+fe[x]); for(ri i=head[x];i;i=nx[i]) if(v[i]!=fr&&lu[v[i]]) finds(v[i],x,val-w[i]); } signed main() { #ifdef M207 freopen("in.in","r",stdin); //freopen("ot.out","w",stdout); #endif int op,a,b,cq,root=1; in(n),in(cq); for(ri i=1,c;i<n;++i) { in(a),in(b),in(c); v[++cnte]=b,nx[cnte]=head[a],head[a]=cnte,w[cnte]=c; fa[b]=a; } while(root<=n&&fa[root]) ++root; pfs(root); while(cq--) { in(op),in(a),in(b); mx=0; if(op==1) { f[a].push(b); finde(a,0,b); if(mx>0) upd(a,mxk); } else { g[a].push(b); finds(a,0,b); if(mx>0) upd(mxk,a); } out(ans); } return 0; } ``` ## T3 好题...类氪金手游题。 比赛的时候先把波浪排列的写了，然后 $$O(n2^n)\to O(n^3)\to O(n^2)$$ 更神奇的是代码一个比一个短... 我们从$O(n^2)$开始，$f[i][j]$表示前i个位置填了$1-i$的排列，最后一个数为j的方案数。那么转移是前缀和的形式（可以认为去掉最后一个数后其他数重新离散化后进入子问题）。 再继续优化似乎很困难？发现我们很擅长解决只有$<$的情况：假如s只有$<,?$，我们把每个极长的<段拿出来，发现 $$ans=n!/\prod a_i!$$ 如果有$>$怎么办呢？容斥！设$cnt_i$表示前i个中有多少$>$ $$dp_i=\sum_j^{i-1}[s_j\neq<](-1)^{cnt_{i-1}-cnt_j}dp_j/(i-j)!$$ 分治NTT即可。