显然是 vp 。

传送门 – Educational Codeforces Round 85 (Rated for Div. 2)

题目难度尚可,手速快点大概可以阿克?(虽然不会做 G

总结:做简单题的时候心态要平稳,手速要快,不要犹豫。(做后面几题的时候才提起兴趣是不好的

A

模拟,吃了三发罚时,吐力。

B

注意到可选的是一个集合而不是一个区间。如果要凑出 $i$ 个合法的数,最好的方法就是用前 $i$ 大的数凑。因此排序后扫一遍即可。时间复杂度 $O(n\log n)$ 。

C

显然是选定一个怪,将这个怪打死,然后引发爆炸,收割残血。

枚举第一个被打死的怪是哪个即可,时间复习度 $O(n)$ 。

D

手玩一发:

  • 从 $1$ 出发,走完 $2$ 至 $n-1$ 后走向 $n$,这里的序列是 121314...1n 。这个时候与 $1$ 相关的边基本走完了,最后剩下一条 $n\rightarrow 1$ 的边显然是最后走的。
  • 接着 $n\rightarrow 2$ ,然后现在有 $n-1$ 个点,仍然在最小点上开始走,这是原问题的一个子问题。按从小到大的顺序走完 $2$ 相关的边后,走向 $n$ ,然后 $n\rightarrow 3$ ,变成了更小的原问题的子问题。

最优的策略就浮出水面了,最终的答案一定是 1213..1n 2324..2n 3435..3n ..n1 这样的。

然后就枚举每一段直接算即可。

E

对于 $v|u$ 的情况,最优解一定是从 $u$ 一直向下走到 $v$ 。对于 $v\not| u$ 的情况,最优解一定是先到 $\gcd(u,v)$ 再到 $v$ ,其实和第一种是等价的。

那么最短路是怎么形成的呢?

考虑用 $(a_1,a_2,\cdots,a_n)$ 表示 $p_1,p_2,\cdots,p_n$ 的次数,走一步的意义就是将 $a_i$ 减去一。假设当前一步改变了 $a_i$ ,下一步改变了 $a_j$ ,考虑这两步的贡献以及交换后的贡献:
$$
\left(\prod_{k\not=i}a_k+(a_i-1)\prod_{k\not=i,k\not=j}a_k\right)=\left(\prod_{k\not=i}a_k+\prod_{k\not=j}a_k-\prod_{k\not=i,k\not=j}a_k\right)=\left(\prod_{k\not=j}a_k+(a_j-1)\prod_{k\not=i,k\not=j}a_k\right)
$$
发现交换两步,距离仍然是不变的。因此 $(a_1,a_2,\cdots,a_n)$ 走向 $(0,0,\cdots,0)$ 的最短路径数其实就是:
$$
\frac{(\sum a_i)!}{\prod a_i!}
$$
然后就做完了。时间复杂度 $O(\sqrt{D}+d(D)q)$ ?

F

容易想到用 $dp_i$ 表示以 $i$ 这个位置结尾的最小答案,如果 $a_i\notin {b_1,b_2,\cdots,b_m}$ 的话不做定义。

发现 $dp_i$ 的转移其实就是找 $b$ 序列中 $a_i$ 的上一个数出现的位置。不妨以 $a_i$ 为下标开桶维护贡献。定义 $sum_j$ 表示 $\min\limits_{k\leq i,a_k=j}dp_k+calc(k+1,i)$ ,然后转移显然就有:$dp_i=sum_{las(a_i)}$ ,其中 $las(i)$ 表示数字 $i$ 在 $b$ 序列中的上一个数的值。

现在更新了位置 $i$,考虑如何维护 $sum$ :

  • 对于 $b_k<a_i$ :那么必须选,$sum_k=sum_k+p_i$ 。
  • 对于 $b_k\geq a_i$ :可选可不选,$sum_k=\max(sum_k,sum_k+p_i)$ 。
  • 对于 $b_k=a_i$ :考虑上述情况后,还需要对 $dp_i$ 取 $\min$ 。

用线段树简单维护就好。时间复杂度 $O(n\log n)$ 。

G

卷积匹配,学到了。

考虑 $s_i$ 和 $t_j$ 匹配的条件是 $(s_i-t_j)(p_{s_i}-t_j)=0$ ,如果要整个串都匹配的话注意要平方一下再加起来,不然容易出问题,即 $\sum(s_i-t_j)^2(p_{s_i}-t_j)^2=0$ 意味着匹配成功。

将 $s$ 翻转后可以发现这是个卷积,然后卷一下就没了。


不过有许多细节。

首先,$\sum (s_i-t_j)^2(p_{s_i}-t_j)^2$ 可能大于模数,然后这样就变成了一个相当危险的单模哈希。处理方法有

  • 拿两个模数各跑一遍,相当于双模哈希。
  • 给每个字符赋上一个随机值。

第二种显然好写一些,然后就写了第二种(

然后,如果是用 $(s_i-t_j)^2(p_{s_i}-t_j)^2$ 来卷的话,拆开是九个式子,两个可以前缀和处理,剩下的只能 $\rm{NTT}$ ,这样就要做 $7$ 次 $\rm{NTT}$ ,本地极限数据要跑 $1.4s$ 。

不知道怎么搞,然后就学 EA 的做法信仰一波卷 $(s_i-t_j)(p_{s_i}-t_j)$,随机种子瞎打了一个交上去过了(/qiang(不过后面连着调了好几个种子都过不去 /dk

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code