2019 Multi-University,HDU Day 5

From EOJ Wiki
Revision as of 11:08, 5 August 2019 by Kilo (talk | contribs) (→‎Problem H)
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Unsolved. (-9)

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 (+)

Problem H

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

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

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

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

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

Problem I

Unsolved.

Problem J

Unsolved.