Difference between revisions of "2019 Multi-University,HDU Day 5"
Xiejiadong (talk | contribs) |
|||
Line 73: | Line 73: | ||
== Problem I == | == Problem I == | ||
− | + | Upsolved by Weaver_zhu. | |
== Problem J == | == Problem J == | ||
Unsolved. | Unsolved. |
Revision as of 05:35, 6 August 2019
Problem A
Unsolved.
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
Upsolved by Weaver_zhu.
Problem J
Unsolved.