1. qoj8003 Anti-Plagiarism
不难想到 dp，即 \(dp_{x,a,b}\) 表示第一棵树以 \(x\) 为根的子树能否和第二棵树中以 \(a\) 为根时 \(b\) 的子树匹配，其中 \(a,b\) 相邻。
想想怎么转移，就是把子树的 dp 值算出来，然后对于 \(x\) ，枚举一对 \(a,b\) ，发现这里其实就是二分图匹配：右边的点是 \(x\) 的儿子，左边的点是 \(b\) 除了 \(a\) 以外与之相邻的 \(c\) 。然后如果 \(dp_{v,b,c}=1\) 就从 \(v\) 往 \(c\) 连边。看左边是否满流即可。最后再枚举一个 \(t\) ，进行类似的过程来 check 以 \(x\) 为根的子树是否和以 \(t\) 为根时的第二棵树匹配。
虽然直接这样复杂度是对的，但是常数巨大，难以通过。考虑我们计算出以 \(t\) 为根时做的匹配后，如果满了就直接输出 Yes 了；否则我们通过这个来计算所有 \(dp_{x,a,t}\) 的值：如果 \(a,x\) 代表的左部点不是最大匹配的必经点，就说明 \(dp_{x,a,t}=1\) 了。这是可以在 dinic 结束后顺便求得的。这样，我们做匹配的次数变成原来的 \(\frac{1}{3}\) ，容易通过。
2. qoj8005 Crossing the Border
一个 trick 吧。首先 \(O(3^n)\) 的 dp 是容易的，即 \(s_T\le W\) 且 \(T\) 最高位大于 \(S\) 时用 \(dp_S\) 更新 \(dp_{S\cup T}\) 。考虑利用折半来优化这个过程，我们把状态表示成 \(LR\) 的形式，表示前 \(\frac{n}{2}\) 个状态拼起来和后 \(\frac{n}{2}\) 个物品的状态拼起来。核心思路就是：考虑在 \(LR'\) 处同时处理 \(LR\) 到 \(L'R'\) 的转移，其中 \(L\) 是 \(L'\) 的子集，\(R\) 是 \(R'\) 的子集。
枚举 \(X\) 和 \(Y\) ，如果 \(Y=0\) 就特殊处理一下；否则先枚举 \(Y\) 的子集 \(Y'\) ，其中 \(Y'\) 不能包含 \(Y\) 的最高位，把 \((s_{Y-Y'},dp_{XY'})\) 这个 pair 从小到大排序，并处理出前缀的信息和。
再枚举 \(X\) 的超集 \(X'\) ，找到第一个值 \(\le W-s_{X'-X}\) 的前缀，用相应的信息更新 \(dp_{X'Y}\) 即可。注意到这里我们可以预处理出 \(s_{Y-Y'}/s_{X'-X}\) 排序的结果，所以复杂度即
\(O(6^{\frac{n}{2}}+3^{\frac{n}{2}}\log n)\) 。
3. qoj970 Best Subsequence
考虑二分答案 \(m\)，把 \(\le\frac{m}{2}\) 的看成 \(1\) ，\(>\frac{m}{2}\) 的看成 \(0\) ，那可以发现 \(1\) 是会全部取的；对于 \(0\) ，考虑相邻两个 \(1\) 之间只能取至多一个 \(0\) ，我们尝试取其中最小的即可。
然后思考怎么快速的计算，首先 \(1\) 是容易的，可以主席树处理，对于 \(0\) ，设第一个 \(1\) 在 \(x\) ，最后一个 \(1\) 在 \(y\) ，我们先看 \(x,y\) 间的 \(0\) 有多少个被选的。仍然可以主席树处理：考虑 01 序列随着 \(m\) 的变化只会变化 \(n\) 次，考虑这个过程中所有存在过的相邻 \(1\) ，设这两端更大的为 \(X\) ，它们中间最小的数是 \(Y\) ，那么 \(m\in [X+Y,2Y)\) 时这一对数就能产生贡献。我们把这一对的贡献放到左边，仍然用主席树查就好了，即查 \(m\) 版本时 \([x,y)\) 的和，再加上 \(1\) 。最后是 \([x,y]\) 外的 \(0\) ，这里就单次的算即可。\(x,y\) 的位置线段树二分查即可。于是复杂度 \(O(q\log n\log V)\) 。
4.qoj971 Binary Search Tree
首先离线下来，利用扫描线转化成：对于一个序列，我们会单点修改，以及查询：对于某个位置 \(x\) ，找到序列建出的小根笛卡尔树中 \(x\) 最深的权值 \(\le v\) 的祖先 \(f\) ，并计算 \(f\) 到根的点的权值和。
很 ez，我们找到 \(i\le x\) 中最大的 \(i\) 使 \(a_i\le v\) ，\(i\geq x\) 同理，那么 \(f\) 就是两个位置中 \(a\) 更大的那个。这可以通过线段树二分计算；然后是计算 \(f\) 到根的点权和，你发现某个点 \(e\) 是 \(f\) 的祖先等同于：\(e\) 到 \(f\) 的最小值就是 \(a_e\) 。用单侧递归线段树就能计算这个东西了。 复杂度 \(O(q\log^2n)\) 。
标签：le,frac,log,复杂度,枚举,杂题,dp From： https://www.cnblogs.com/cwhfy/p/18231939