Difference between revisions of "2018 Multi-University, Nowcoder Day 7"

From EOJ Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
Solved by zerol. 00:22 (+)
 
Solved by zerol. 00:22 (+)
 +
 +
题意:求一个 1~n 到 1~n 的匹配,使得位与的和最小。
 +
 +
题解:首先猜想答案一定是 0(考虑每一位,0 的个数都不小于 1 的个数,所以不排除答案是 0 的可能性)。然后开始构造,发现 $2^k+i$ 和 $2^k-i-1$ 匹配是极好的,然后就找到当前不超过 n 的最大的 k,这样大于等于 $(2^k - 1)-(n-2^k)$ 的就搞定了,然后接着处理变小了的 n 就好了。
  
 
== Problem B ==
 
== Problem B ==
Line 22: Line 26:
  
 
* 首先最惨的情况是 $a=1$ 就有解了。那么有 $(x + nb) \bmod p = t$,由于 $n$ 是想选什么就选什么,所以要么 $x=t$,要么 $\text{gcd}(n,p)=1$ 即 $n \bmod p \ne 0$。所以无解的条件是 $x \ne t$ AND $p | n$(条件 0)。
 
* 首先最惨的情况是 $a=1$ 就有解了。那么有 $(x + nb) \bmod p = t$,由于 $n$ 是想选什么就选什么,所以要么 $x=t$,要么 $\text{gcd}(n,p)=1$ 即 $n \bmod p \ne 0$。所以无解的条件是 $x \ne t$ AND $p | n$(条件 0)。
* 其次 $a>1$。那么有 $(a^n x + \frac{a^n-1}{a-1} b) \bmod p = t$。那么有解条件就是:$a^n x \equiv t \pmod p$ OR $\frac{a^n-1}{a-1} \bmod p \ne 0$,即 $a^n \ne 1 \pmod p$。所以 $b$ 无解的情况是 $a^n x \ne t \pmod p$ AND $a^n \equiv 1 \pmod p$,注意到如果 $n = p - 1$ 的话,那就什么都有解了,为了让 $a$ 小的时候无解,$n$ 坚决不能等于 $p-1$(条件 1),其次可以令 $x=p, t=1$,这样的话无解的第一个式子就满足,这时候只需要考虑第二个式子。就是(条件 2)要求一个不是 $p-1$ 的倍数的数 $n$,使得 $a'^n \equiv 1 pmod p$(对于 $a' < a$)。然后最后这个 $n$ 求出来了以后我们只要验证一下有解条件成立就好了(条件 3)。至于这个 $a$ 的话,'''根据原根的定义可以知道''',肯定不会比原根大的。
+
* 其次 $a>1$。那么有 $(a^n x + \frac{a^n-1}{a-1} b) \bmod p = t$。那么有解条件就是:$a^n x \equiv t \pmod p$ OR $\frac{a^n-1}{a-1} \bmod p \ne 0$,即 $a^n \ne 1 \pmod p$。所以 $b$ 无解的情况是 $a^n x \ne t \pmod p$ AND $a^n \equiv 1 \pmod p$,注意到如果 $n = p - 1$ 的话,那就什么都有解了,为了让 $a$ 小的时候无解,$n$ 坚决不能等于 $p-1$(条件 1),其次可以令 $x=p, t=1$,这样的话无解的第一个式子就满足,这时候只需要考虑第二个式子。就是(条件 2)要求一个不是 $p-1$ 的倍数的数 $n$,使得 $a'^n \equiv 1 \pmod p$(对于 $a' < a$)。然后最后这个 $n$ 求出来了以后我们只要验证一下有解条件成立就好了(条件 3)。至于这个 $a$ 的话,'''根据原根的定义可以知道''',肯定不会比原根大的。
  
 
然后我们就是要找一个符合 0,1,2,3 这四个条件的 $n$,要把比 $a$ 小的所有的 $a'$ 在模 $p$ 意义下的阶,以及 $p$ 本身做一次 lcm,边做便要验证条件 1,做完了以后再验证下条件 3 就好了。实现起来其实挺容易的,但是如果暴力的话时限其实有点紧。(不过反正可以交表嘛。。。)
 
然后我们就是要找一个符合 0,1,2,3 这四个条件的 $n$,要把比 $a$ 小的所有的 $a'$ 在模 $p$ 意义下的阶,以及 $p$ 本身做一次 lcm,边做便要验证条件 1,做完了以后再验证下条件 3 就好了。实现起来其实挺容易的,但是如果暴力的话时限其实有点紧。(不过反正可以交表嘛。。。)
Line 39: Line 43:
  
 
== Problem F ==
 
== Problem F ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:定义一个集合的 mindiff 是相邻元素差的最小值,maxdiff 是最大减最小。求 $1$ 到 $n$ 所有子集的 mindiff * maxdiff 之和。
 +
 +
题解:枚举 $d$,令 $\text{mindiff } \ge d$,然后枚举集合中的元素个数 $k$(这两层枚举保证了时间复杂度是 $O(n \log n)$),我们要计算这些集合的 maxdiff 之和。由插板法,先把相邻元素间的多余的元素拿掉,于是令 $m = n - (k-1)(d-1)$。拿掉了这些元素后,等于把原集合缩紧了,maxdiff 就变成了 $\sum_{t=k-1}^{m-1} t(n-t) \binom{t-1}{k-2} = \frac{(m+1)!}{k(k+1)(m-k)!(k-2)!}$。另外 maxdiff 还要把原来的那些拿掉的部分给加上,总共 $\binom{m}{k}$ 个集合,每个集合损失了 $(k-1)(d-1)$。然后做一次差分就可以求出 mindiff 恰好是 $d$ 的 maxdiff 之和。求下点积即可。
  
 
== Problem G ==
 
== Problem G ==
Line 48: Line 58:
 
== Problem I ==
 
== Problem I ==
  
Unsolved. (-13)
+
Upsolved by zerol. (-13)
 +
 
 +
题意:求树上的点集个数使得其直径(相距最远的两个点之间的距离)为 D。
 +
 
 +
题解:直径不唯一,但直径的中点唯一。为了避免奇偶的讨论,开两倍点。设枚举的直径中点为 u,设距离 u 小于等于 D 的点数是 a,小于 D 的是 b,每个方向的距离恰好为 D 的是 $c_v$,那么贡献是 $2^a-2^b-2^b \sum_v 2^{c_v}$。距离每个点距离不超过 k 的点的个数可以用点分治做。先当有根树,u 每个儿子遍历前后增加的深度为 dep[u]+D 的点的个数也很容易统计,从 u 上面过来的个数就是 $a-b-\sum_v c_v$。
 +
 
 +
但是,卡常。如果你写得好,那么现在已经过了。我只能把两倍点去掉,偶数很简单。奇数就是中点在边上,好处就是只有两个方向可以伸展,坏处就是需要求距离 u 或 v 距离不超过 D 的点的个数,这个问题见 [[2018 Multi-University, HDU Day 5]]。
  
 
== Problem J ==
 
== Problem J ==
  
 
Solved by kblack. 01:38 (+2)
 
Solved by kblack. 01:38 (+2)
 +
 +
题意:求一个 $1000^2$ 的字母矩阵里类数独矩阵(每行每列的元素各不相同)的数量。
 +
 +
题解:大小写一共52个,预处理向上向左最大距离,枚举右下角/上下边界,可以很轻松的做到 $52n^2$。

Latest revision as of 16:39, 12 August 2018

Problem A

Solved by zerol. 00:22 (+)

题意:求一个 1~n 到 1~n 的匹配,使得位与的和最小。

题解:首先猜想答案一定是 0(考虑每一位,0 的个数都不小于 1 的个数,所以不排除答案是 0 的可能性)。然后开始构造,发现 $2^k+i$ 和 $2^k-i-1$ 匹配是极好的,然后就找到当前不超过 n 的最大的 k,这样大于等于 $(2^k - 1)-(n-2^k)$ 的就搞定了,然后接着处理变小了的 n 就好了。

Problem B

Problem C

Solved by ultmaster. 02:14 (+3)

题意:给一个长度为 $2^n$ 的字符串,每次用 AND, OR, XOR 中的一种操作把相邻的两个合并。求最后合并结果是 1 的操作方案数。

题解:暴力就好了,维护一个可选的集合,和集合中每个产生的方案数。复杂度是 $\sum_{x=0}^{18} 2^{18 - x} \cdot \min(3^x, 2^{18-x}) \approx 1.4 \times 10^7$。由于还要带上数据结构的常数 / log,可能时限很紧。需要常数优化,能少开的地方尽量少开,unordered_map 可以卡过。

Problem D

Upsolved by ultmaster. (-1)

题意:有关于 $b$ 的方程 $t = a^n x + b (\sum_{i=0}^{n-1} a^i) \bmod p$。请构造一组 $(x,n,t,p)$ 使得:$p \le M$ 且使 $b$ 有解的 $a$ 尽可能大(即存在 $a$ 满足代入之后 $b$ 有解,且满足所有 $a' < a$ 代入之后都无解)。

题解:这种题就是属于做不出来的。比赛的时候甚至连上面的题意都没分析出来。切入点是从小到大枚举 $a$ 的情况分析 $b$ 的有解条件(就是枚举着枚举着突然有一天 $b$ 就有解了,我们要让这一天尽可能来得晚)。注意到只有 $p$ 是有限制的,所以这个方程里的 $x,n,t$ 都是想选什么就选什么。

  • 首先最惨的情况是 $a=1$ 就有解了。那么有 $(x + nb) \bmod p = t$,由于 $n$ 是想选什么就选什么,所以要么 $x=t$,要么 $\text{gcd}(n,p)=1$ 即 $n \bmod p \ne 0$。所以无解的条件是 $x \ne t$ AND $p | n$(条件 0)。
  • 其次 $a>1$。那么有 $(a^n x + \frac{a^n-1}{a-1} b) \bmod p = t$。那么有解条件就是:$a^n x \equiv t \pmod p$ OR $\frac{a^n-1}{a-1} \bmod p \ne 0$,即 $a^n \ne 1 \pmod p$。所以 $b$ 无解的情况是 $a^n x \ne t \pmod p$ AND $a^n \equiv 1 \pmod p$,注意到如果 $n = p - 1$ 的话,那就什么都有解了,为了让 $a$ 小的时候无解,$n$ 坚决不能等于 $p-1$(条件 1),其次可以令 $x=p, t=1$,这样的话无解的第一个式子就满足,这时候只需要考虑第二个式子。就是(条件 2)要求一个不是 $p-1$ 的倍数的数 $n$,使得 $a'^n \equiv 1 \pmod p$(对于 $a' < a$)。然后最后这个 $n$ 求出来了以后我们只要验证一下有解条件成立就好了(条件 3)。至于这个 $a$ 的话,根据原根的定义可以知道,肯定不会比原根大的。

然后我们就是要找一个符合 0,1,2,3 这四个条件的 $n$,要把比 $a$ 小的所有的 $a'$ 在模 $p$ 意义下的阶,以及 $p$ 本身做一次 lcm,边做便要验证条件 1,做完了以后再验证下条件 3 就好了。实现起来其实挺容易的,但是如果暴力的话时限其实有点紧。(不过反正可以交表嘛。。。)

ultmaster: 一早就过了这个题拿了一血的 oxx 说其实就是原根,乱搞一下就好了。并且对题解没有采用他的代码表示很不满。然后我直接当原根乱搞一下 WA 了。求到原根以后又枚举了一下(其实是两下)才过。可能就是太菜了吧。事实上如果题解采用了 oxx 的代码我可能连怎么死的都不知道(少枚举了一次只炸了一个但死活看不出来)。

Problem E

Solved by ultmaster. 03:07 (+1)

题意:构造一个不超过 75 个点的图,使得刚好有 $n$ 个 $K_4$ 子图。

题解:不失一般性,我们只讨论最大的情况。分成 70 个点,和 5 个点。70 个点构成完全图有 $\binom{70}{4}$,然后五个点分别射进去 $x_1,x_2,\ldots,x_5$ 个,就可以多得到 $\binom{x_1}{3}, \ldots, \binom{x_5}{3}$ 个 $K_4$。故 $\binom{70}{4} + \binom{x_1}{3} + \cdots + \binom{x_5}{3} = n$,其中 $0 \le x_i \le 70$。暴力验证表明,这个方程刚好可以 cover 所有的不超过 $\binom{71}{4}$ 的整数。然后五个未知数就是一个经典套路,中途相遇就好了。

ultmaster: 这个题做法大概很多,假做法大概更多。一上来看到这题,智障的某人以为是签到。

Problem F

Upsolved by ultmaster.

题意:定义一个集合的 mindiff 是相邻元素差的最小值,maxdiff 是最大减最小。求 $1$ 到 $n$ 所有子集的 mindiff * maxdiff 之和。

题解:枚举 $d$,令 $\text{mindiff } \ge d$,然后枚举集合中的元素个数 $k$(这两层枚举保证了时间复杂度是 $O(n \log n)$),我们要计算这些集合的 maxdiff 之和。由插板法,先把相邻元素间的多余的元素拿掉,于是令 $m = n - (k-1)(d-1)$。拿掉了这些元素后,等于把原集合缩紧了,maxdiff 就变成了 $\sum_{t=k-1}^{m-1} t(n-t) \binom{t-1}{k-2} = \frac{(m+1)!}{k(k+1)(m-k)!(k-2)!}$。另外 maxdiff 还要把原来的那些拿掉的部分给加上,总共 $\binom{m}{k}$ 个集合,每个集合损失了 $(k-1)(d-1)$。然后做一次差分就可以求出 mindiff 恰好是 $d$ 的 maxdiff 之和。求下点积即可。

Problem G

Problem H

Unsolved. (-2)

Problem I

Upsolved by zerol. (-13)

题意:求树上的点集个数使得其直径(相距最远的两个点之间的距离)为 D。

题解:直径不唯一,但直径的中点唯一。为了避免奇偶的讨论,开两倍点。设枚举的直径中点为 u,设距离 u 小于等于 D 的点数是 a,小于 D 的是 b,每个方向的距离恰好为 D 的是 $c_v$,那么贡献是 $2^a-2^b-2^b \sum_v 2^{c_v}$。距离每个点距离不超过 k 的点的个数可以用点分治做。先当有根树,u 每个儿子遍历前后增加的深度为 dep[u]+D 的点的个数也很容易统计,从 u 上面过来的个数就是 $a-b-\sum_v c_v$。

但是,卡常。如果你写得好,那么现在已经过了。我只能把两倍点去掉,偶数很简单。奇数就是中点在边上,好处就是只有两个方向可以伸展,坏处就是需要求距离 u 或 v 距离不超过 D 的点的个数,这个问题见 2018 Multi-University, HDU Day 5

Problem J

Solved by kblack. 01:38 (+2)

题意:求一个 $1000^2$ 的字母矩阵里类数独矩阵(每行每列的元素各不相同)的数量。

题解:大小写一共52个,预处理向上向左最大距离,枚举右下角/上下边界,可以很轻松的做到 $52n^2$。