浅念づ昔夜's Blog

传送门

Solution

并查集。在一个 $k$ 下能通过若干次交换相互得到的物品构成一个集合。

对 $q$ 个询问升序排序，离线处理。

对大小为 $n+m$ 的数组 $a_n$ 进行排序，枚举 $a_i$，二分查找在哪个询问时合并 $a_i$ 和 $a_{i+1}$ 所在集合。

一个集合包含的元素必然在有序数组 $a_n$ 中构成连续区间。

传送门

Solution

2-SAT 板子题。

设点 $u_{i}$ 为 $i=-1$，$u_{i+n}$ 为 $i=1$。

对于每一列，最少要有两个 $1$。这意味着，若一列中的一个数为 $-1$，则其余两个数必定为 $1$，这就得到了两条有向边。我们分别假设一列中的三个数为 $-1$，就得到了 $6$ 条有向边。因为有 $n$ 列，所以一共有 $6n$ 条有向边。然后跑 Tarjan，判断是否有 $u_{i}$、$u_{i+n}$ 在同一强连通分量内即可。

传送门

Solution

注意到若 $a_i \oplus a_j < 4$，则 $a_i>>2=a_j>>2$。我们将除以四后结果相同的元素分到同一组。显然，若 $a_i$，$a_j$ 可交换，$a_j$，$a_k$ 可交换，则 $a_i$，$a_k$ 可交换。所以同一组内的所有元素可相互交换，即每一组均可内部排序。

将每一组排好序后，倒序枚举原数组，将每个元素替换成所在组内的最后一个元素，并将其从组内弹出。替换完成的新数组即为答案。

问题描述：

有 $n$ 个 bool 变量，有$m$个条件，如 $\lfloor x_i$ 为 true/flase 或 $x_j$ 为 true/false $\rfloor$。求是否有方案能满足所有条件。构造出一组符合题意的解。

算法思路：

按照条件建立分层图，令 $x_i$ 为 true，$x_{i+n}$ 为 false。

传送门

Solution

首先考虑数组内已经有 $1$ 的情况。设此时有 $n_1$ 个 $1$，则答案为 $n-n_1$。

再考虑数组内没有 $1$ 的情况。要想让整个数组变成 $1$，首先要先在某一段连续的区间内进行 $\gcd$ 操作，生成第一个 $1$。然后通过 $n-1$ 次 $\gcd$，把数组的其余元素变成 $1$。设生成第一个 $1$ 的连续区间长度为 $len$，本题答案即为

传送门

Solution

设第一次操作的结果为 $x$，选定的素数为 $p_1$。第二次操作的结果为 $y$，选定的素数为 $p_2$。由题意可得

$$x-p_1+1\le y-p_2<x\le y$$

题目给出的是 $y$，所求为 $x-p_1+1$ 的最小值。要使 $x$ 最小，则要使 $y-p_2$ 最小。因此找出 $y$ 的最大质因数。再枚举 $p_1$，求出符合上文不等式的最小合法 $x$，可找出答案。

本文包括埃氏筛和线性筛。

简介

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。本文内容包括逆康托展开。

问题引入

$n$ 封信从信封拆出，现将信放回，要求每封信都不能放到原来的信封里。求信放回的方案数。

前置知识

• 笛卡尔树

• ST表

• 分块思想

• 状态压缩

  阅读全文 »