hdu2019多校5

发表于 2019-12-28 分类于 hdu ，多校

2019 Multi-University Training Contest 5

Problem A fraction

题意

给定一个质数 $p$ 和一个小于 $p$ 的正整数 $x$，求出最小的正整数 $b$ 使得存在至少一个正整数 $a$ 满足$a < b$ 且 $a\equiv bx(\bmod p)$

$1\leq T \leq 2\times 10^5$

$1 < x < p$

$3\leq p \leq 10^{15},p\in \mathbb{P}$

保证有解。

题解

先把 $a\equiv bx(\bmod p) (a < b )$ 换成 $a=bx-py(y>0)$的形式。

根据题意可得 $0<a=bx-py<b$

即：$py<bx,b(x-1)<py$

由 $x>1$，$y>0$，可得： $\frac{p}{x}<\frac{b}{y}<\frac{p}{x-1}$

$p,x,x-1$ 都已知，转换成 $\frac{a}{b}<\frac{x}{y}<\frac{c}{d}$ 且 $x$ 最小的问题。

当 $\frac{a}{b}$ 与 $\frac{c}{d}$ 间存在整数时，取 $y=1$ 会使得 $x$ 的最小值最小。

当不存在整数时，考虑减小范围。

不等式两边同时减去 $z$ 得：

$\frac{a-bz}{b}<\frac{x-yz}{y}<\frac{c-dz}{d}$

$z$ 的最值为 $\left \lceil \frac{a}{b} \right \rceil-1$

不等式取倒数得：

$\frac{d}{c-dz}<\frac{y}{x-yz}<\frac{b}{a-bz}$

变成更小的子问题。

正确性：递归处理同时保证 $y$ 最小的同时 $x-yz$ 最小，而 $x=(x-yz)+yz$，因此能保证 $x$ 最小。

时间复杂度为ex_gcd的时间，即 $O(\log p)$

Problem B three arrays

题意

有两个长度为 $n$ 的数组 $a,b$，任意排列 $a$ 和 $b$ 后，记 $c_i=a_i\bigoplus b_i$

求字典序最小的 $c$。

$n\leq 10^5$,$a_i,b_i< 2^{30}$

题解

一道不错的题。

首先是异或，可以想到应该是跟 01trie 有关的东西。

那么对 $a,b$ 上的数分别建一个01trie。

然后两个序列上的数字看成点，存在有向边 $(a_i,b_j)$ 当且仅当 $j$ 为使得 $a_i\bigoplus b_j$ 最小的 $j$，$(b_i,a_j)$ 同理。这样就得到了一个有向的二分图之类的东西。

若序列中的数两两不同，且同时存在 $(a_i,b_j)$ 和 $(b_j,a_i)$ 两条边，那么显然答案中一定会出现 $a_i$ 和 $b_j$ 配对的情况。因为如果不出现，交换位置一定会更优。

那么配对了以后可以在原来的序列中删去，变成了一个子问题。

如果序列中有相同的数，把这些数合并到一起就好了。

继续深挖性质。

发现不会出现长度大于 $2$ 的环。

一条边 $(x,y)$ 的意义在于 $x$ 最偏向 $y$，那么如果出现了 $(d_1,d_2),(d_2,d_3)$ 这两条边的话就说明 $d_1\bigoplus d_2 > d_2\bigoplus d_3$，如果此时连成了环 $(d_1,d_2,\cdots,d_m)$ 的话，就会有 $d_1\bigoplus d_2>d_2\bigoplus d_3>\cdots>d_{m-1}\bigoplus d_m>d_m\bigoplus d_1>d_1\bigoplus d_2$

矛盾，因此不可能出现。

那么可以dfs，用栈维护当前这条链是什么，当出现了一个长度2的环就尽量配对。当栈顶配对完了就弹出。

时间复杂度 $O(n(\log w+\log n))$，其中 $w$ 为 $a,b$ 中元素的最大值。

Problem D equation

题意

两个长度为 $n$ 的序列 $a,b$ 和整数 $C$

求下列方程所有的解，以分数形式输出。

$$\sum_{i=1}^n|xa_i+b_i|=C$$

$n\leq10^5,1\leq a_i,|b_i|\leq 10^3,C\leq 10^9$

题解

一次函数之和为一次函数，而 $|xa_i+b_i|$ 为一条折线，相当于两个一次函数。

$n$ 条这样的折线相加后，斜率和截距最多只会在 $n$ 个点处发生变化。

因此 $n$ 条折线相加后相当于 $n+1$ 个一次函数。

在每个一次函数的范围内判断一下就可以了。

Problem E permutation1

dfs模板题，签到题

Problem F string matching

扩展kmp模板题，签到题

Problem G permutation2

递推模板题，签到题