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

From EOJ Wiki
Jump to navigation Jump to search
 
(27 intermediate revisions by one other user not shown)
Line 2: Line 2:
  
 
Solved by Kilo_5723. 00:12:16 (+1)
 
Solved by Kilo_5723. 00:12:16 (+1)
 +
 +
题意:给定 $1$ ~ $n$ 共 $n$ 个结点,$i$ 和 $j$ 之间的路径长为 $i \& j$,求字典序最小的最小生成树。
 +
 +
题解:对于每一个结点 $q$,连到最小的 $2^i\&q=0$ 上,但如果 $2^i>n$ 要连到 $1$ 上。
  
 
== Problem B ==
 
== Problem B ==
Line 19: Line 23:
 
令每组的整数数量为 $m$,我们只要处理 $m=3$ 的情况就可以了,因为剩下的情况都可以处理前 $3$ 项之后转化成第一种情况。
 
令每组的整数数量为 $m$,我们只要处理 $m=3$ 的情况就可以了,因为剩下的情况都可以处理前 $3$ 项之后转化成第一种情况。
  
令 $k=3$,我们可以通过搜索找出以下规律:(第 $i$ 行第 $j$ 个数代表 $j+3 \cdot (i-1)$ 属于的集合编号)。
+
令 $m=3,k=2\cdot t-1$,我们可以通过搜索分别找出三个数分布的规律:(第 $i$ 行第 $j$ 个数代表 $j+3 \cdot (i-1)$ 属于的集合编号)。
  
$\begin | 1 | 3 | 5 |
+
\begin{array}\\
|:--:|:--:|:--:|
+
1&2&3&4&5&6&\cdots&k-5&k-4&k-3&k-2&k-1&k\\
| 1 | 3 | 5 |\end
+
t+1&t+2&t+3&t+4&t+5&t+6&\cdots&t-5&t-4&t-3&t-2&t-1&t\\
$
+
t&k&t-1&k-1&t-2&k-2&\cdots&t+3&3&t+2&3&t+1&1\\
 +
\end{array}
 +
 
 +
例如当 $k=7$ 时,应为:
 +
 
 +
\begin{array}\\
 +
1&2&3&4&5&6&7&\\
 +
5&6&7&1&2&3&4&\\
 +
4&7&3&6&2&5&1&
 +
\end{array}
 +
 
 +
根据规律输出。
 +
 
 +
能暴力跑规律的题千万不要手推。
  
 
== Problem D ==
 
== Problem D ==
Line 32: Line 49:
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
Upsolved by Weaver_zhu.
 +
 
 +
题意:求$k$个数字的八进制数满足是$p$的倍数且每个数字出现次数都是3的倍数的数字有多少个。
 +
 
 +
题解:$dp[k][i][p]$ 表示状态压缩三进制 $i$ 和模等于 $p$ 的 $k$ 位数字有多少个。然后考虑倍增+卷积运算。这里的卷积是 3进制不进位加法的卷积。有个技巧是只做首尾两次 fwt 和 rfwt,因为fwt运算只涉及到加法
  
 
== Problem F ==
 
== Problem F ==
Line 54: Line 75:
 
Solved by Xiejiadong. 01:23:54 (+)
 
Solved by Xiejiadong. 01:23:54 (+)
  
题意:询问一段区间 $a_l,a_{l+1},\cdots a_r$ 中元素 $\{|a_1-p|,|a_{l+1}-p|,\cdots ,|a_r-p|\}$ 中的 $k$ 大数。
+
题意:询问一段区间 $a_l,a_{l+1},\cdots a_r$ 中元素 $\{|a_l-p|,|a_{l+1}-p|,\cdots ,|a_r-p|\}$ 中的 $k$ 大数。
  
 
题解:利用主席树可以维护一个区间里面一段值域里面元素的个数。
 
题解:利用主席树可以维护一个区间里面一段值域里面元素的个数。
Line 72: Line 93:
 
题解:可以发现 $3982^4 > 10^{18}$ ,于是,我们可以知道 $> 3981$ 的数,指数最多为 $4$ 次。
 
题解:可以发现 $3982^4 > 10^{18}$ ,于是,我们可以知道 $> 3981$ 的数,指数最多为 $4$ 次。
  
我们先把 $4000$ 以内的数暴力处理掉,剩下的数就只能是某个数的整数次方了,直接判断开 $x$ 次方是不是整数就好了。
+
我们先把 $4000$ 以内的数暴力处理掉,剩下的数就只能是某个数的整数次方了,从大到小判断开 $x$ 次方是不是整数就好了。

Latest revision as of 10:03, 6 August 2019

Problem A

Solved by Kilo_5723. 00:12:16 (+1)

题意:给定 $1$ ~ $n$ 共 $n$ 个结点,$i$ 和 $j$ 之间的路径长为 $i \& j$,求字典序最小的最小生成树。

题解:对于每一个结点 $q$,连到最小的 $2^i\&q=0$ 上,但如果 $2^i>n$ 要连到 $1$ 上。

Problem B

Unsolved.

Problem C

Upsolved by Kilo_5723. (-3)

题意:$1$ ~ $n$ 的整数,分成 $k$ 组,使得每组的和以及每组的数的个数都相同,求可行解。

题解:首先,如果每组有偶数个整数,显然将首尾的数不断成对压进每组就能满足条件。

如果每组有奇数个整数,此时如果 $2 \mid k$,则 $k \not \mid \frac{n\cdot (n+1)}{2}$。我们只要做 $k$ 为奇数的情况就行了。

令每组的整数数量为 $m$,我们只要处理 $m=3$ 的情况就可以了,因为剩下的情况都可以处理前 $3$ 项之后转化成第一种情况。

令 $m=3,k=2\cdot t-1$,我们可以通过搜索分别找出三个数分布的规律:(第 $i$ 行第 $j$ 个数代表 $j+3 \cdot (i-1)$ 属于的集合编号)。

\begin{array}\\ 1&2&3&4&5&6&\cdots&k-5&k-4&k-3&k-2&k-1&k\\ t+1&t+2&t+3&t+4&t+5&t+6&\cdots&t-5&t-4&t-3&t-2&t-1&t\\ t&k&t-1&k-1&t-2&k-2&\cdots&t+3&3&t+2&3&t+1&1\\ \end{array}

例如当 $k=7$ 时,应为:

\begin{array}\\ 1&2&3&4&5&6&7&\\ 5&6&7&1&2&3&4&\\ 4&7&3&6&2&5&1& \end{array}

根据规律输出。

能暴力跑规律的题千万不要手推。

Problem D

Unsolved.

Problem E

Upsolved by Weaver_zhu.

题意:求$k$个数字的八进制数满足是$p$的倍数且每个数字出现次数都是3的倍数的数字有多少个。

题解:$dp[k][i][p]$ 表示状态压缩三进制 $i$ 和模等于 $p$ 的 $k$ 位数字有多少个。然后考虑倍增+卷积运算。这里的卷积是 3进制不进位加法的卷积。有个技巧是只做首尾两次 fwt 和 rfwt,因为fwt运算只涉及到加法

Problem F

Unsolved.

Problem G

Solved by Xiejiadong && Weaver_zhu. 02:45:41 (+1)

题意:判断十五数码问题是否无解。

题解:在 Xiejiadong 的强行误导下, Weaver_zhu 写了两个小时 A* 。

直接大力猜结论,大概模拟一下 $0$ 位置的变动。

根据 $0$ 所在位置的行列奇偶性和分行和列的逆序对数量奇偶行相同即可。

Problem H

Solved by Xiejiadong. 01:23:54 (+)

题意:询问一段区间 $a_l,a_{l+1},\cdots a_r$ 中元素 $\{|a_l-p|,|a_{l+1}-p|,\cdots ,|a_r-p|\}$ 中的 $k$ 大数。

题解:利用主席树可以维护一个区间里面一段值域里面元素的个数。

对于每个询问二分答案,假设当前答案为 $mid$ ,那么我们需要查询区间里面值域为 $[p-mid,p+mid]$ 的元素个数,元素个数恰好为 $k$ 的就是答案。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723 && Xiejiadong. 04:09:28 (+1)

题意:求整数 $n$ 分解质因数以后,最小的指数。

题解:可以发现 $3982^4 > 10^{18}$ ,于是,我们可以知道 $> 3981$ 的数,指数最多为 $4$ 次。

我们先把 $4000$ 以内的数暴力处理掉,剩下的数就只能是某个数的整数次方了,从大到小判断开 $x$ 次方是不是整数就好了。