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

From EOJ Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
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 ==
 
== 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 ==
Line 26: Line 38:
  
 
Solved by Weaver_zhu. 00:57:42 (+)
 
Solved by Weaver_zhu. 00:57:42 (+)
 +
 +
温暖的签到,据说是数据变弱了才是签到的
  
 
== Problem F ==
 
== Problem F ==
Line 45: Line 59:
 
Solved by Kilo_5723. 00:51:52 (+)
 
Solved by Kilo_5723. 00:51:52 (+)
  
题意:求一个全排列 $\{a_n\}$,使得 $a_1=x,a_n=y$,并且 $\left| a_{i+1}-a_i \right| \le 2$。
+
题意:求一个全排列 $\{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 ==
 
== Problem H ==
Line 61: Line 79:
 
== Problem I ==
 
== Problem I ==
  
Unsolved.
+
Upsolved by Weaver_zhu.
 +
 
 +
Pohlig-Hellman 算法,量身定制版题目,这份教材写的不错(虽然是英文的
 +
http://www-math.ucdenver.edu/~wcherowi/courses/m5410/ctcdlp.html
  
 
== Problem J ==
 
== Problem J ==
  
 
Unsolved.
 
Unsolved.

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

Upsolved by Weaver_zhu.

Pohlig-Hellman 算法,量身定制版题目,这份教材写的不错(虽然是英文的 http://www-math.ucdenver.edu/~wcherowi/courses/m5410/ctcdlp.html

Problem J

Unsolved.