10.29 写题

CF388D

对于一个不同的线性基,对应着一种不同的 Perfect Set 。只要线性基能异或出来的数都得在 Perfect Set 里面。

于是考虑一个数位 $dp$ ,设 $dp[i][j][0/1]$ 表示当前考虑到了第 $i$ 位,已经有 $j$ 个位的线性基填过数,到现在最高位是否贴着上界的方案数量。

我们考虑第 $i-1$ 位。

  • $k = 0$

    这一位可以随便填或者不填。如果这一位填了 $1$ ,那么之前位的这一位都不能有值。转移系数是 $1$ 。如果这一位不填 $1$ ,之前可以任意填,转移系数 $2^j$。

  • $k = 1$

    如果填入这一位,则仍然是卡着上界的。转移系数是 $1$ 。

    如果不填,则如果之前这一位上有偶数个 $1$ ,那么就不再卡着上界了。转移系数是 $\binom n 0 + \binom n 2 + \dots = 2^{j-1}$ ,因为对于所有选择偶数个数的方案,我们只要把第一个位置给反转一下,就一定可以得到一个选择奇数个数的方案,并且明显方案一定两两对应。

    如果之前这一位上有奇数个 $1$ ,那么仍然卡着上界,系数是 $2^{j-1}$ 。

Gym 100543L / P4766

为什么我就是想不到呢

可以把人看作一条 $(a_i,d_i) \to (b_i,d_i)$ 的线段。

考虑区间 $dp$ ,设 $dp[l][r]$ 表示被 $[l,r]$ 完全包含的区间全部被干掉最小的代价。

我们每次从区间内部选择一个最高的区间,然后把它砍掉同时分成两个区间即可。

复杂度 $O(n^3)$ 。

CF584E

首先,我们可以变成一个给排列排序的问题。设 $p_i$ 表示当前 $i$ 位置最终需要到达的位置。

答案是有下界的。总共需要移动的代价至少是 $\sum |i - p_i|$ ,即使每一步都最优地操作,也只能让当前需要的代价减少 $2|i-j|$ ,也就是两个数都像自己的目标点移动了 $|i-j|$ ,所以答案的下界是 $\frac{\sum |i-p_i|}{2}$。

一定取得到这个下界吗?考虑从小到大还原数。设我们当前还原到了 $t$ ,处于的位置是 $pos_t$ 。那么 $1\sim t$ 这些位置的值一定已经被还原好了。我们可以从 $pos_t$ 往前找一个数 $q$ ,使得 $p_q > pos_t$ ,然后交换这两个数,不难发现这样就可以让代价减少 $2|i-j|$ 。一定可以找到这样的数吗?如果找不到,说明 $t \sim pos_t-1$ 的数只需要内部交换就可以全部归位。但是 $t$ 这个东西需要到达 $t$ ,也就是说从 $t$ 到 $pos_t-1$ 的可以用的位置总是比数的个数少 $1$ 的,所以必然不能全部归位,所以一定可以找到这个数 $q$ 。一直这么找下去,必然可以把 $t$ 归位,同时每步操作都是尽量优秀的。

APOJ ACPC13

就边权从小到大加入来保证路径权值递增,然后设个 $dp[u][i]$ 表示当前到了 $u$ ,经过了 $i$ 条边的最小代价,对每个起点跑一次 $dp$ 即可。因为经过的边数肯定是不超过 $n$ 的,所以复杂度 $O(n^2m)$ 大概。

染色

image.png

神仙题。

考虑差分一下,变成同色点间距离 $\ge k$ 。

然后按照 $\text{BFS}$ 顺序加入点。这样加点的时候每轮都加入的是一个叶子。然后结论就是,加入一个点对方案的贡献就是 $m-t$ 其中 $t$ 是当前与这个点距离不到 $k$ 的点的个数。

为啥这样是对的呢?啥时候这样会炸,就是有两个点,它们到加入的叶子距离都不到 $k$ ,但是它们之间的距离超过了 $k$ 。事实上,这种情况是不存在的。我们考虑这个点的一个祖先,如果有两个点到这个点的路径在这个祖先交汇。

image.png

也就是 $dis_1 + dis_2 \ge k , dis_1 + dis_3 < k, dis_2 + dis_3 < k$ 存在了。

也就是说 $dis_1 > dis_3 , dis_2 > dis_3$ 存在。但是我们是按照 $\text{BFS}$ 顺序加入的,加入是按照到根的 $dis$ 顺序来的,所以不存在。

唯一一条有可能大于等于 $k$ 的路径就是这个祖先向根方向走的路径了。但是这种路径只有一条,所以也不存在这种情况。

于是拿点分树维护一下即可。

CF1188C

去年做的题现在忘了。。。

考虑枚举一下最终的最小差值,然后求相邻两项的差值都必须大于等于这个差值的方案数量。

设 $dp[i][k]$ 表示当前正在选择第 $i$ 个数,已经有 $k$ 个数被选进序列。转移就是一个双指针 + 前缀和。

不难发现,最小差值不超过 $\frac v k$ ,所以复杂度其实是 $O(nv)$ 的。。。

P5405 氪金手游

考虑如果所有边都是从根向下的,那么对于一个点,它必须在子树内所有点之前被取。这个点被取的概率是 $a$ ,子树内的点被取的概率是 $b$ 的话,那么概率就是

在这里,我们知道一个点被取的概率是 $\frac{a}{S}$ 子树的某个点被取的概率是 $\frac{s_u - a_u}{S}$ ,那么总的来说,这个点比子树内的所有点都先取的概率就是 $\frac{a}{s_u}$ 。于是我们可以树形背包解决全是根向下的边的情况,记 $dp[u][x]$ 表示 $u$ 子树之中所有数的权值和位 $x$ 的概率即可。边界是最开始给 $dp[u][1,2,3]$ 分别放初值 $p_{u,1,2,3} \times 1,2,3$ 这些东西,最后给 $dp[u][k]$ 除以 $k$ 即可。

考虑反向边的情况,我们可以钦定一些反向边不合法,剩下的反向边任意,容斥系数显然是 $(-1)^k$ ,算出来的就是恰好 $0$ 个反向边不合法的方案数量。

某个题

数点 $x \le a,y \le b,x+y\le c$。

考虑如果 $a+b \le c$ ,那么我们只数前两个条件即可。

否则,如果 $a+b>c$ ,考虑容斥前两个条件,钦定一些不合法,那么算的就是:

这四个情况中前三个都是二维数点。最后一个,由于 $x+y > a+b > c$ ,必然不存在。

于是复杂度 $O(n\log n)$ 。

文章作者: yijan
文章链接: https://yijan.co/2020/11/08/1029-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog