鱼C论坛

 找回密码
 立即注册
查看: 195|回复: 1

[学习笔记] AT_abc367 补题报告【G】

[复制链接]
发表于 2024-8-18 15:45:36 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
前言

我感觉我写这些内容对自己有很大益处,尤其是考试补题,因为补题不仅仅是一个“能多几个 AC”的作用,还是一个吸取教训、总结、提升自己的一个重要途径。从某种意义上来说这是写给自己的。

每一场(方便公开)的比赛如果改完题目(达到能力上限)就会来总结。由于 lz 水平有限,所以一些帖子的学术性问题欢迎在本贴讨论指出错误。




比赛题目:https://atcoder.jp/contests/abc367/tasks

问题 D

一个湖周围有 $N$ 个休息区。  
这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、......、 $N$ 。  
从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A_i$ 步(其中休息区 $N+1$ 指的是休息区 $1$ )。  
从休息区 $s$ 顺时针步行至休息区 $t$ 所需的最小步数( $s \neq t$ )。是 $M$ 的倍数。  
求 $(s,t)$ 可能的对数。


针对于这种循环的序列,可以将原序列拓展一份,然后问题就转换成了(转换问题才是问题最难点,尤其是 +1 -1 这种猎奇),原序列对于所有 $i\ge n$ 的位置,满足 $\sum_{k=j}^{i} A_k \equiv 0 \pmod M$ 的 $j$ 的总数,且 $j\ge i-n+1$。

显然先对 $A$ 做一遍前缀和,那么就是相等的位置的总数了,可以用桶维护。再使用类似于滑动窗口的技巧,对于一个位置如果是大于 $\ge n$ 的,那么就消除掉 $i-n$ 的影响,这样就能维护所选择区间长度为 $N$ 的性质了。

赛后:https://atcoder.jp/contests/abc367/submissions/56836246


问题 E

给定长度为 $N$ 的序列 $X$ 和 $A$,进行 $K$ 次操作:
- 令序列 $B$ 满足 $B_i = A_{X_i}$,再把 $A$ 替换。
输出序列 $A$。


如果把序列拆开,单点考虑,也就是对于每一个位置 $i$ 进行 $K$ 次操作,即令 $B=X_i$,再将 $i=B$,求最后的 $A_i$。

于是你就发现变成了一道 FCOI #3 的最后一道题 /jk,倍增板子。

场切:https://atcoder.jp/contests/abc367/submissions/56830410

问题 F

无序集合哈希板子,即判断分别从两个序列中截取出来的区间所组成的无序集合是否相同。

无序集合哈希就是把集合中的每一个元素的哈希值通过具有交换律的运算运算再一起所得到的结果就是这个集合的哈希。

容易发现我们需要设计两个哈希函数,一个是针对于值的 $f_1$,一个是针对于集合的 $f_2$。

那么就要想应该怎么做才能让正确率高了,其中一个常见的做法就是把 $f_1$ 设计为一个多次的多项式(次数越多越好),可以取模,然后 $f_2$ 设计为加或者是异或。

我使用的是 $f_1(x) = x^5$,$f_2(S) = \sum_{x\in S} x$。集合哈希和正常的哈希一样,也是可以双哈的。

场切:https://atcoder.jp/contests/abc367/submissions/56822504


问题 G

好像超纲了,说是什么 hadamard 变换,暂时不会。

总结教训

问题简单化,能拆就拆。

还有就是自己出的题不要自己搞忘 \jk。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-18 19:47:54 | 显示全部楼层
大佬ORZ%%%
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-11 05:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表