浅念づ昔夜's Blog

传送门

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表

• 分块思想

• 状态压缩

  阅读全文 »

定义

笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 $k,w$。 若只看 $k$，整颗树为二叉查找树；只看 $w$，树为堆。

如图，点在数组中的位置号码为 $k$，元素内数字为 $w$。

分析

用 $\text{map}$ 对数组离散化，防止撑爆树状数组。

从左到右扫一遍数组。$i-1$ 表示左边有 $i$ 个数。显然左边的数与 $a_i$ 构成逆序对的数量为 $i-1$ 减左边比 $a_i$ 小的数的数量。

记得去重。