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

From EOJ Wiki
Jump to navigation Jump to search
Line 53: Line 53:
  
 
Solved by kblack. 01:38 (+2)
 
Solved by kblack. 01:38 (+2)
 +
 +
题意:求一个 $1000^2$ 的字母矩阵里类数独矩阵(每行每列的元素各不相同)的数量。
 +
 +
题解:大小写一共52个,预处理向上向左最大距离,枚举右下角/上下边界,可以很轻松的做到 $52n^2$。

Revision as of 13:46, 10 August 2018

Problem A

Solved by zerol. 00:22 (+)

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

Problem G

Problem H

Unsolved. (-2)

Problem I

Unsolved. (-13)

Problem J

Solved by kblack. 01:38 (+2)

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

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