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

From EOJ Wiki
Jump to navigation Jump to search
 
(25 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
Solved by Kilo_5723. 00:17:42 (+)
 
Solved by Kilo_5723. 00:17:42 (+)
 +
 +
题意:输出一个数,使得其是 $n$ 的倍数,而且每一位之和也是 $n$ 的倍数。
 +
 +
题解:输出 $n$ 个 $n$。
  
 
== Problem B ==
 
== Problem B ==
  
 
Solved by Kilo_5723. 01:27:34 (+)
 
Solved by Kilo_5723. 01:27:34 (+)
 +
 +
题意:已知 $x_0,x_1$,并且 $x_i=a \cdot x_{i-1}+b \cdot x_{i-2}$,求 $x_n$。$n$ 的位数不超过 $10^6$。
 +
 +
题解:矩阵快速幂。突破点在于快速求十进制下幂次的快速幂。
 +
 +
逐位处理。假设当前矩阵为 $B$,初始矩阵为 $A$。
 +
可以预处理 $A^0$ ~ $A^9$,每读进一位 $k$,就让 $B=B^{10}\cdot A^k$。其中十次幂的运算可以用快速幂优化。
  
 
== Problem C ==
 
== Problem C ==
  
Unsolved. (-8)
+
Upsolved Weaver_zhu. (-8)
 +
 
 +
题意:$a_i = ba_{i-1}+c$,求最小的下标 $x$ 使得 $a_x=v$
 +
 
 +
题解:$a=0,1$ 是等差数列,特判一下,其余情况可以转换为 $a_i+\frac{b}{a-1} = t(a_{i-1} + \frac{b}{a-1})$,于是就是离散对数问题了。$q\sqrt{p}$ 大概6e7 2.5s被不幸卡常,明明本地数据拉满跑1s就出来了,得优化分块的参数复杂度变成$2\sqrt{pq}$,不过实际上也就快了3倍左右。
  
 
== Problem D ==
 
== Problem D ==
  
Unsolved.
+
Upsolved by Kilo_5723.
 +
 
 +
题意:给出 $x_0,y_0$,且 $x_i=(a_x \cdot x_{i-1} + b_x)\;{\rm mod}\;p_x,y_i=(a_y \cdot y_{i-1} + b_y)\;{\rm}\;p_y$,求由 $(x_0,y_0)$ ~ $(x_n,y_n)$ 构成的凸包面积。
 +
 
 +
题解:我们发现,$x,y$ 在经过至多 $2 \cdot 10^5$ 次映射之后就会进入循环。因此先把前 $2\cdot 10^5$ 个点压入集合。设 $x,y$ 的循环节是 $r_x,r_y$。
 +
 
 +
对于之后的点,我们发现,由于映射的性质,在预处理之后,我们可以对任何 $c$ $O(1)$ 地通过 $y_i$ 求出 $y_{i+c}$。根据这个性质,我们可以通过倍增求出来每个 $y_i$ 的 ${\rm max}/{\rm min}\{y_i,y_{i+c},y_{i+2 \cdot c},\dots,y_{i+k \cdot c}\}$。
 +
 
 +
我们发现,从 $(x_k,y_k)$ 开始的 $c \cdot r_x$ 个点,一共有 $r_x$ 个可能的 $x$,而对每一个不同的 $x_{k+i}$,其对应的 $y$ 为 $y_{k+i},y_{k+i+r_x},y_{k+i+2\cdot r_x},\dots,y_{k+i+(c-1) \cdot r_x}$。根据凸包的性质,我们只需要对每个 $x$ 求出其对应的 $y$ 中最大和最小的两个值压入集合,这可以通过上面的运算得到。
 +
 
 +
用上面的做法处理 $c=\lfloor \frac{n-2 \cdot 10^5}{r_x} \rfloor$ 的情况,而对最后剩下的一些点,暴力枚举压入集合。对集合求一遍凸包就是答案。
  
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:求所有子图的最大独立集之和。
 +
 
 +
题解:$n$ 只有 $26$ 考虑状态压缩。
 +
 
 +
$f[x]$ 表示子图为 $x$ 的时候,最大独立集。
 +
 
 +
我们只考虑从最低位的转移,显然这个图的最大独立集变大了,只能是最低位加入的时候,他的相邻顶点都不在集合中,也就是状态 $x\&\sim (e[lowbit(x)])$ , $lowbit$ 表示最低位。
 +
 
 +
所以 $f[x]=max\{f[x-lowbit(x)],f[x\&\sim (e[lowbit(x)])]+1\}$ 。
  
 
== Problem F ==
 
== Problem F ==
  
Unsolved. (-15)
+
Upsolved by Xiejiadong. (-15)
 +
 
 +
题意:给出 $n$ 个数,求最大的数集,使得两两的二进制表示不同位数至少为 $2$ 。
 +
 
 +
题解:因为保证了每个数都是不同的,所以考虑将恰好有一位不同的数之间连边。
 +
 
 +
于是就相当于是求这个图的最大独立集。
 +
 
 +
可以很容易的发现这是一个二分图,如果 $x$ 和 $y,z$ 都恰好有一位不同,而因为 $y\neq z$ ,所以 $y,z$ 至少有两位不同。
 +
 
 +
二分图的最大独立集 = 点数 - 二分图匹配。
 +
 
 +
可行的方案,是通过再跑未匹配的交叉路标记来得到。
  
 
== Problem G ==
 
== Problem G ==
Line 56: Line 103:
  
 
Solved by Kilo_5723. 03:13:09 (+1)
 
Solved by Kilo_5723. 03:13:09 (+1)
 +
 +
题意:构造能卡在宽为 $w$,高为 $h$ 的矩形里,距离分别为 $a,b,c$ 的三点。
 +
 +
题解:三条边中肯定有一条边一段是 $0,0$,另一端卡在边界上,枚举剩下的点的位置判是否合法。合法解总存在于三条边的一种排列里。
  
 
== Problem J ==
 
== Problem J ==
  
 
Unsolved. (-12)
 
Unsolved. (-12)

Latest revision as of 09:58, 6 August 2019

Problem A

Solved by Kilo_5723. 00:17:42 (+)

题意:输出一个数,使得其是 $n$ 的倍数,而且每一位之和也是 $n$ 的倍数。

题解:输出 $n$ 个 $n$。

Problem B

Solved by Kilo_5723. 01:27:34 (+)

题意:已知 $x_0,x_1$,并且 $x_i=a \cdot x_{i-1}+b \cdot x_{i-2}$,求 $x_n$。$n$ 的位数不超过 $10^6$。

题解:矩阵快速幂。突破点在于快速求十进制下幂次的快速幂。

逐位处理。假设当前矩阵为 $B$,初始矩阵为 $A$。 可以预处理 $A^0$ ~ $A^9$,每读进一位 $k$,就让 $B=B^{10}\cdot A^k$。其中十次幂的运算可以用快速幂优化。

Problem C

Upsolved Weaver_zhu. (-8)

题意:$a_i = ba_{i-1}+c$,求最小的下标 $x$ 使得 $a_x=v$

题解:$a=0,1$ 是等差数列,特判一下,其余情况可以转换为 $a_i+\frac{b}{a-1} = t(a_{i-1} + \frac{b}{a-1})$,于是就是离散对数问题了。$q\sqrt{p}$ 大概6e7 2.5s被不幸卡常,明明本地数据拉满跑1s就出来了,得优化分块的参数复杂度变成$2\sqrt{pq}$,不过实际上也就快了3倍左右。

Problem D

Upsolved by Kilo_5723.

题意:给出 $x_0,y_0$,且 $x_i=(a_x \cdot x_{i-1} + b_x)\;{\rm mod}\;p_x,y_i=(a_y \cdot y_{i-1} + b_y)\;{\rm}\;p_y$,求由 $(x_0,y_0)$ ~ $(x_n,y_n)$ 构成的凸包面积。

题解:我们发现,$x,y$ 在经过至多 $2 \cdot 10^5$ 次映射之后就会进入循环。因此先把前 $2\cdot 10^5$ 个点压入集合。设 $x,y$ 的循环节是 $r_x,r_y$。

对于之后的点,我们发现,由于映射的性质,在预处理之后,我们可以对任何 $c$ $O(1)$ 地通过 $y_i$ 求出 $y_{i+c}$。根据这个性质,我们可以通过倍增求出来每个 $y_i$ 的 ${\rm max}/{\rm min}\{y_i,y_{i+c},y_{i+2 \cdot c},\dots,y_{i+k \cdot c}\}$。

我们发现,从 $(x_k,y_k)$ 开始的 $c \cdot r_x$ 个点,一共有 $r_x$ 个可能的 $x$,而对每一个不同的 $x_{k+i}$,其对应的 $y$ 为 $y_{k+i},y_{k+i+r_x},y_{k+i+2\cdot r_x},\dots,y_{k+i+(c-1) \cdot r_x}$。根据凸包的性质,我们只需要对每个 $x$ 求出其对应的 $y$ 中最大和最小的两个值压入集合,这可以通过上面的运算得到。

用上面的做法处理 $c=\lfloor \frac{n-2 \cdot 10^5}{r_x} \rfloor$ 的情况,而对最后剩下的一些点,暴力枚举压入集合。对集合求一遍凸包就是答案。

Problem E

Upsolved by Xiejiadong.

题意:求所有子图的最大独立集之和。

题解:$n$ 只有 $26$ 考虑状态压缩。

$f[x]$ 表示子图为 $x$ 的时候,最大独立集。

我们只考虑从最低位的转移,显然这个图的最大独立集变大了,只能是最低位加入的时候,他的相邻顶点都不在集合中,也就是状态 $x\&\sim (e[lowbit(x)])$ , $lowbit$ 表示最低位。

所以 $f[x]=max\{f[x-lowbit(x)],f[x\&\sim (e[lowbit(x)])]+1\}$ 。

Problem F

Upsolved by Xiejiadong. (-15)

题意:给出 $n$ 个数,求最大的数集,使得两两的二进制表示不同位数至少为 $2$ 。

题解:因为保证了每个数都是不同的,所以考虑将恰好有一位不同的数之间连边。

于是就相当于是求这个图的最大独立集。

可以很容易的发现这是一个二分图,如果 $x$ 和 $y,z$ 都恰好有一位不同,而因为 $y\neq z$ ,所以 $y,z$ 至少有两位不同。

二分图的最大独立集 = 点数 - 二分图匹配。

可行的方案,是通过再跑未匹配的交叉路标记来得到。

Problem G

Solved by Xiejiadong && Weaver_zhu. 03:42:19 (+)

题意:求字符串 $s$ 中有多少子序列(不能有前导 $0$ )满足按照数字比较比字符串 $t$ 大 。

题解:字符串 $s$ 中长度比 $t$ 大的很好处理,只要去掉 $0$ 开头的就好了。

长度相等的考虑用 dp 来做。 $f[i][j][k]$ 表示处理到第 $i$ 位,比较到了字符串 $t$ 的第 $j$ 位,前 $j$ 位是否相等 $k=0/1$ 。

暴力转移一下就好了。

读错题了。以为 $t$ 也是子序列。

数位 dp 这部分也是不需要的。

我又负输出了。

Problem H

Solved by Xiejiadong. 03:00:20 (+2)

题意:每次给出两个字母的相对关系,还原原字符串。

题解:每次给出的字母一定是包含了所有出现位置的,否则就是无解的情况。

于是我们先对所有的字母编号,然后在每次给出的顺序相邻之间连边(所有边都连的话,可能会 TLE )。

在连出的图中跑一个拓扑排序就好了。

Problem I

Solved by Kilo_5723. 03:13:09 (+1)

题意:构造能卡在宽为 $w$,高为 $h$ 的矩形里,距离分别为 $a,b,c$ 的三点。

题解:三条边中肯定有一条边一段是 $0,0$,另一端卡在边界上,枚举剩下的点的位置判是否合法。合法解总存在于三条边的一种排列里。

Problem J

Unsolved. (-12)