Attention Is All You Need?

C 数列之和

  • 数列 $a$ 由 $10^{100}$ 项组成,从第一项开始有 $a_i = 2i - 2$。
  • 将数列 $a$ 中所有长度大于 $1$ 的连续子数列的元素和去重后从小到大构成一个新的数列,求这个数列的第 $k$ 项。

注意到,答案为 $2(k + \lfloor \log_2{(k + \lfloor \log_2 k \rfloor)} \rfloor)$,时间复杂度 $\mathcal O(T)$。

阅读更多

P11362 [NOIP2024] 遗失的赋值 题解

首先,需要特判 $c_i = c_j$ 但 $d_i \neq d_j$ 的情形,此时答案为 $0$。

否则,我们可以把每相邻的两条一元限制作为一个区间单独拎出来。这样做正确的原因是,每一个 $x_i$ 的取值只受前面一个数的影响。事实上,完全可以任意选取区间,只不过这样选可以利用已知的 $x_i$,依次讨论出 $a_{i+1}, b_{i+1}, a_{i+2}, b_{i+2}, \cdots$ 的可能取值,便于计算答案。

我们随便找几个数举个例子:

阅读更多

【欧拉计划】52. Permuted multiples

(本题取 $n=142857$)

【思路】从 $1$ 开始向更大的数进行枚举,利用 Python 整型字符串自由转换的功能进行判断,找到符合题意的数即可输出。

总体时间复杂度为 $\mathcal O(n)$:

阅读更多

【欧拉计划】51. Prime digit replacements

(本题取 $n=1000000$)

【思路】欧拉筛初始化后,对位数及空缺位置进行枚举,再分别判断 $0 \sim 9$ 填入之后是否为质数即可。

其中,在枚举方面,我们可以在 $0 \sim 9$ 之外新建一个特殊位 $10$,表示这个位置是待替换的。这样,我们的程序就无形之间被简化了。

总体时间复杂度为 $\mathcal O(n)$:

阅读更多

欧拉计划完整版题解

Problem 1: Multiples of 3 and 5

(本题取 $n=1000$)

【思路】$\mathcal O(n)$ 枚举所有能被 $3$ 和被 $5$ 整除的数,最后把能被 $15$ 整除的数减掉:

阅读更多

【欧拉计划】50. Consecutive prime sum

(本题取 $n=1000000$,$m$ 为不超过 $n$ 的质数个数)

【思路】欧拉筛初始化后,采用前缀和预处理,一旦超过 $n$ 就不再继续做下去,这样会减小后续枚举范围。

紧接着在所有质数中枚举作为起始质数,然后取连续的 $maxl+1$ 个质数得到它们的和(规定 $maxl$ 为当前最多质数的个数),再判断是否为质数即可。

总体时间复杂度为 $\mathcal O(n+m^2)$:

阅读更多