CSP-S模拟赛DAY 5

· · 个人记录

T1 距离

给你一张有向图，n 个点 m 条边，同时每个点有点权 a_i，当 a_i \land a_j =a_j 时，i 到 j 也有一条边。

问从点 1 到其他所有点分别最少经过多少条边。

n \le 2\times 10^5 ,m\le 3\times 10^5,a_i \le 2^{20}

最简单的方法就是暴力枚举两个点连边，然后想到对于每个点与它所对应的权值连无边权的双向边，然后权值对应的点之间按要求连边权为 1 的边，这样是 3^{20}，然后发现每个权值对应的点可以只向自己去掉二进制上的某一个 1 后的值连边，然后边权设为 0，把点到权值点的边中选一条设为 1 即可，由于只有 0,1，直接 bfs 。

T2 洗牌

你有 n 张牌 a_1,a_2,…,a_n，它们形成了个 1,2,…,n 的排列。你想对它们洗牌。每次洗牌操作是这样的：

首先把这 n 张牌按顺序分成非空的 k 段， D_1,D_2,…,D_k，然后把他们按照 D_k,D_{k-1},…,D_1 排列。每一段内部的牌的相对顺序不会改变。

比如 [3,6,2,1,4,5,7] 可以先分成 [3,6],[2,1,4],[5,7]，然后重新排成 [5,7],[2,1,4],[3,6]，也就是 [5,7,2,1,4,3,6]。

现在给你一副牌 a_1,a_2,…,a_n，让你用不超过 120 次洗牌操作，把它变成 1,2,…,n。

首先一个转化，将原本的操作转化为每一段内部翻转，然后再整个序列翻转一次，然后就可以发现，整体翻转可以扔到最后，判断一下即可。那么问题就变成每次分成若干段，段内翻转，怎样变有序。

考虑分治，每一次将大于中值的数扔到右边，小于等于的扔到左边，那么考虑怎么扔。

发现可以将大于的值设为 1，小于等于的设为 0，这样就变成了若干个 01 段，然后令第一个 1 段为第一段，那么就是所有的 i\bmod 4=1 的段与下一段会划分到一起，其余的段内划分即可。

每一轮会使段数除以 2，所以操作次数是 O( \log^2 n) 的。

T3 抽卡

你在玩一个抽卡游戏，一共有 n 张卡，分数分别是 a_1,a_2,…,a_n。

每次你可以花费 C 的代价，从牌堆中随机抽出一张卡。你可以选择保留这张卡，那么游戏马上结束，你会获得这张卡对应的分数。也可以选择扔掉这张卡，游戏继续进行，扔掉的卡牌不会放回到牌堆中。

你希望最大化你的期望收益，即你的最后的分数减去抽卡的总代价，问最大化的期望收益是多少。你至少需要抽一张卡。

你要回答 q 组询问，每次询问的 C 不同，而卡牌都相同。并且每组询问之间独立。

考虑对于每一种情况，如果选到了一个数，而在之前扔掉了比它大的牌，那么一定不会要它，因为