https://wiki.cvbbacm.com/ 2026-04-30T03:43:41+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-04T11:16:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:qgjyf2001:%E5%BC%82%E6%88%96%E6%96%B9%E7%A8%8B%E7%BB%84&rev=1599189363&do=diff 异或方程组 解法 发现异或方程组和普通的方程组有几乎相同的形式，只不过把加法改成了异或。解方程组的时候我们应该也只要把加法消元改成异或消元即可。比如有两个式子$x_k\oplus a_{i2}x_{k+1}\oplus\ldots\oplus a_{im}x_m=b_i$和$x_k\oplus a_{j2}x_{k+1}\oplus\ldots\oplus a_{jm}x_m=b_j$ 。我们把两式异或就可消去首项。同时我们可以考虑用bitset优化来减小常数 text/html 2020-08-14T13:43:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:qgjyf2001:%E7%BA%BF%E6%80%A7%E5%9F%BA&rev=1597383780&do=diff 线性基 定义 对于一组数 $a_1,a_2,\ldots,a_n$ ，他们的线性基为 $p_1,p_2,\ldots,p_m$ ，其中 $p_i$ 是指出现1的最高位在第 $i$ 位上的那个数。 构造方法 对于每个数，我们先找出他的最高位的1在第 $i$ 位，假如 $p_i$ 此时为零，那么将这个数假如线性基，否则异或 $p_i$$k$$2^i$$i-1$$2xor(n-|B|)$ text/html 2020-08-28T11:58:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:qgjyf2001:%E8%99%9A%E6%A0%91&rev=1598587123&do=diff 虚树 用途 用于处理一类特殊的树形dp问题 构建方法及应用——从一道题目说起 洛谷p2495 题目大意 给定一棵树， $m$ 个询问，每次询问 $k$ 个点均不与 $1$ 号点相连的最小代价和。 暴力 这道题目的朴素做法是暴力dp ，时间复杂度是 $O(nm)$$dp[now]$$dp[now]=\left\{ \begin{aligned}edge[now][fa].w,target[now]=true \\ \sum dp[v],now=1\\min(\sum dp[v],edge[now][fa].w),others\end{aligned} \right.$$\sum k$$O(2\sum k)$$now$$LCA(now,s.top())=s.top()$$s.top()$… text/html 2020-08-21T13:27:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:qgjyf2001:a_%E6%90%9C%E7%B4%A2&rev=1597987673&do=diff A*算法 A*算法是对BFS的一种改进，定义起点为 $s$ ，终点为 $t$ 。那么需要找到从起点开始到某一个点 $n$ 的估值函数 $g(n)$ 和从这个点到终点的估值函数 $h(n)$ ，然后定义函数 $f(n)=g(n)+h(n)$ ，用 $f(n)$ 重载运算符加入优先队列，然后和BFS相似的搜索方式。$g(n)$