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

From EOJ Wiki
Jump to navigation Jump to search
Line 5: Line 5:
 
== Problem B ==
 
== Problem B ==
  
Unsolved. (-9)
+
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 ==
 
== Problem C ==

Revision as of 12:03, 5 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$。

题解:我们发现,一段区间只能被我们经过两次。所以,我们前一段和后一段的行动就只能从 $x$ 走到 $1$,再从 $1$ 走到 $x+1$,后半段同理。

Problem H

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

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

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

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

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

Problem I

Unsolved.

Problem J

Unsolved.