CSP 模拟 24

T1 与和

\(a\operatorname{\&}b=x\ \ \ \ a+b=y\)，\(x\) 为 \(a\) 和 \(b\) 二进制下的公共部分，设为 \(w\)，\(a-w\) 与 \(b-w\) 无公共部分，所以 \(a+b-2w\) 与 \(w\) 无公共部分，根据这个判一下就好了。
std::cout<<(((y-2*x)&x)?"Yes\n":"No\n");

T2 函数

\(f_i(f_j(x))=a_ia_jx+a_ib_j+b_i\)，\(f_i(f_i(x))=a_ia_jx+a_jb_i+b_j\)，\(f_i(f_j(x))\ge f_j(f_i(x))\) 当且仅当 \(\frac{b_i}{a_i-1}\le\frac{b_j}{a_j-1}\)，即 \(\frac{b_i}{a_i-1}\) 越大的越应该放里面，所以对于一个选择的集合，我们知道了它的嵌套顺序，然后直接做个背包即可。

T3 袋鼠

预设性 DP 的板子，设 \(f_{i,j}\) 表示考虑了前 \(i\) 个数，有 \(j\) 个连通块（合法）的方案数，由于从小到大枚举 \(i\)，所以我们钦定了合并连续段是上凸的，并且非端点不能直接接上单独一个连续块，例如有连通块 1，\(2\) 不能直接接在 \(1\) 的后面。

• 当 \(i=s\operatorname{or} i=t\) 时，考虑放头尾，挨着不挨着，\(f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\)，因为不会有每个连通块都是上凸的，所以头尾一定比 \(i\) 小，并且他是山谷，保证合法。
• 当 \(i\ne s\operatorname{\&}i\ne t\) 时，考虑 \(i\) 新建连通块，或者连接两个联通块，\(f_{i,j}=f_{i-1,j-1}*(j-(i>s)-(i>t))+f_{i-1,j+1}*j\)，如果已经确定了端点，那么前/后是不能新建连通块的，所以 j-(i<s)-(i<t)。

初始值 \(f_{1,1}=1\)，直接转移做完了，时间复杂度 \(\mathcal{O}(n^2)\)。

T4 最短路

拿主席树优化的高精度最短路，咕咕咕

总结

这场跟题一点没对上，一点都不会，直接垫底了，T3 一直以为跟地精部落是一样的思路，硬控两个小时，T2 没仔细想确实不应该。