校内OJ 2019.4.14 NOIP 模拟赛

[mdx_warning title=”注意”]这套题目有版权,所以题面禁止复制。[/mdx_warning]

前言

一些话

炸了,细节有很多没处理好。

题目有些不明显,丢了很多不该丢的分。

P1 质因数

题面

有一个正整数数列 $a_1,a_2,…,a_n$ 。定义函数 $f(x)$ 为 $x$ 的不同的质因数数量。
求 $f(a_1),f(a_2)…f(a_n)$ 。

$n<=10^6$

思路

欧拉筛筛出素数,筛素数的时候记录下。

P2 编码

题面

一个字符串 $str$ 的 p 型编码 $a$ 的定义如下:把 $str$ 表示成 $b_1$ 个 $c_1,b_2$ 个 $c_2…b_n$ 个 c_n,然后将 $b_1,c_1,b_2,c_2,…,b_n,c_n$ 首尾拼接成的字符串中最短的字符串设为 a。例如:字符串 $122344111$ 可被描述为”1 个 1、 2 个 2、1 个 3、2 个 4、3 个 1″,因此我们说 $122344111$ 的 p 型编码为 $1122132431$ 。类似的道理, $00000000000$ 可描述为”11 个 0″,因此它的 p 型编码为 $110$ ; $100200300$ 可描述为”1 个 1、 2 个 0、 1 个 2、 2 个 0、 1 个 3、 2 个 0″,因此它的 p 型编码为 $112012201320$。很显然,一个串 $str$ 的 p 型编码是固定的,但是可能有多个串的 p 型编码相同。现在已知一个字符串 $str$ 的 p 型编码 $a$ ,但不知道原来的字符串, 求有多少种字符串的 p 型编码为 $a$ 。

$|a|<=10^6$

思路

设 $f[i]$ 为 $1 \sim i$ 这段字符串的编码方案数,则有: $$\begin{array}{l}f\lbrack i\rbrack=\left\{\begin{array}{c}1\;(i=0)\\0\;(s\lbrack i+1\rbrack=0)\\\sum_{j=0}^{i-1}\;(s\lbrack j\rbrack\neq s\lbrack i\rbrack)\end{array}\right.\\\end{array}$$

我们发现 $f[i]$ 其实就是前面所有 $f[j]$ 的和减去 $s[i]=s[j]$ 的情况,只要边算边把所有 $f$ 的和与 $s[j]$ 为特定数的和记录下就好了。

P3  八卦阵

题面

有一个八卦阵。这个阵可以认为是一个 $n$ 个点, $m$ 条边的有向图。每条边 $i$ 有一个困难 $a[i]$ 。每个点 $u$ 有八个状态: $b[u][1],b[u][2],…,b[u][8]$,这八个状态均为 $[1,8]$ 之间的整数(不一定是排列),在第 $i$ 秒中, $u$ 的状态为 $b[u][(i-1)%8+1]$。对于任意两个状态 $i,j$ 都存在一个复杂度 $c[i][j]$。现在想从 $1$ 号点走到 $n$ 号点, 在第一秒开始时在 $1$ 号点,每次可以用 $1$ 秒从当前点 $u$ 走到另一个有边相连的点 $v$。也就是说, 在第一秒内走过第一条边,在第二秒内走过第二条边……由于八卦阵极其巧妙, 必须砸出一些榔头才能走过一条边。若在第 $i$ 秒通过第 $j$ 条边从点 $u$ 走到点 $v$ ,需要砸出 $a\lbrack j\rbrack+c\lbrack b\lbrack u\rbrack\lbrack(i-1)\%8+1\rbrack\rbrack\lbrack b\lbrack v\rbrack\lbrack(i-1)\%8+1\rbrack\rbrack$ 个榔头。
请计算出至少要多少个榔头才能从点 $1$ 走到点 $n$。

$n,m<=3 \times 10^5$

思路

最简单的一道题,有 $n$ 个结点,对于一条从 $x$ 到 $y$ ,权值为 $z$ 的边,枚举状态 $i (i \in [1,8])$ ,每次新建一条 $(i-1)*n+x$ 到 $(j-1)*n+y$,长度为 $z+c[b[x][(i-1)%8+1]][b[y][(i-1)%8+1]]$ 的边即可。

注意用 $SPFA$ ,$Dijkstra$ 会超时。

考试时候没注意是单向边,分数 $100 \rightarrow 20$ 。

代码

评论

  1. qaq

    abc2337512422!

    2月前
    2019-8-31 14:10:57

发送评论


				
上一篇
下一篇