Difference between revisions of "2019 Multi-University,HDU Day 5"

Latest revision as of 09:45, 6 August 2019

Problem A

Upsolved by Weaver_zhu.

题意：给出 $p,x$，求最小的 $b$ 使得 $\exists a, a \equiv bx (\mod{p})$

题解：$bx-a = yp, a = bx-yp < b \Rightarrow \frac{b}{y} < \frac{p}{x-1}, a>0 \Rightarrow yp+bx>0 \Rightarrow \frac{b}{y} > \frac{p}{x}$, 得出 $\frac{p}{x} < \frac{b}{y} < \frac{p}{x-1}$ 类欧得出答案

Problem B

Upsolved by Xiejiadong. (-9)

题意：给出数组 $a$ 和 $b$ ，计算数组 $c$ 的方式是 $c_i=a_i\oplus b_i$ ，可以任意交换数组 $a$ 和 $b$ 的顺序，使得 $c$ 的字典序最小。

题解：一个显然的贪心策略是，每次取出可能产生的最小的 $c$ ，然后删除对应的 $a$ 、 $b$ ，再继续找最小的...

于是考虑用字典树维护，比赛的时候写了个优先队列维护，多了个 log ，TLE 到生活不能自理。

其实可以直接 dfs ，每次选择一个数，一定是尽量选择 $00$ 或者 $11$ 的情况，但是每次 dfs 选出来的数不一定是有序的，再排个序即可。

Problem C

Unsolved.

Problem D

Solved by Xiejiadong && Kilo_5723. 01:33:31 (+1)

题意：求方程 $\sum_{i=1}^n |a_ix-b_i|=C$ 的所有解。

题解：显然，这是一个分段函数，分段函数的断点，显然就是所有的 $\frac{-b_i}{a_i}$ 。

从前往后枚举 $n+1$ 个区间，每次向后移动一个区间，都只有一项的符号变化会对系数和常数的变化产生影响，保留修改，求解答案看是否在当前定义域内就行了。

要注意特判区间重合的情况。

Problem E

Solved by Weaver_zhu. 00:57:42 (+)

温暖的签到，据说是数据变弱了才是签到的

Problem F

Solved by Xiejiadong. 00:26:00 (+)

题意：给一个字符串，求暴力做 $lcp$ 的时候的比较次数。

题意：大概看一下就能发现了：

如果 $lcp$ 是短串的全部，比较次数就是短串长度；

否则，比较次数就是 $lcp +1$ ；

于是，问题就变成求所有后缀和全串的 $lcp$ ，抄个 exkmp 就过了。

Problem G

Solved by Kilo_5723. 00:51:52 (+)

题意：求一个全排列 $\{a_n\}$，使得 $a_1=x,a_n=y,x<y$，并且 $\left| a_{i+1}-a_i \right| \le 2$。

题解：我们发现，一段区间只能被我们经过两次。所以，除非起点是 $1$，我们前一段的行动就只能从 $x$ 走到 $1$，再从 $1$ 走到 $x+1$，后半段同理，我们就只需要处理中间的一段。

我们的问题就简化成了从 $1$ ~ $n$ 有多少不同的路径。我们发现，要么从 $n-1$ 走到 $n$，要么走 $n-3,n-1,n-2,n$，可以得出 $dp$ 方程为 $dp_n=dp_{n-1}+dp_{n-3}$。

Problem H

Solved by Kilo_5723. 03:04:27 (+5)

题意：给出一个简单多边形，求能否通过移动一个点，使其变成轴对称的简单多边形。

题解：考虑枚举对称轴。对称轴一定是多边形里两个点的垂直平分线，但在原多边形中有三个点可能没有与其配对的点：在对称轴上的至多两个点，和被移动的点。

因此，枚举前四个点与剩下的每一个点可能产生的对称轴，依次判可不可行。一般地，从枚举的点对分别朝两个方向相向出发，分别判断点对是否关于轴对称即，如果不对称就需要花费一个移动点的次数，判断总次数是否 $>1$。

但有一种特殊情况，如果两个点都位于其本应处在的半平面的两边，就无论如何都不可能通过移动一个点使多边形满足条件。特判这种情况就可以了。

Problem I