// 这不是竞赛里那个多项式取模的东西,是离散课本里的特征根法
抱着在离散课装逼的心态挖了这个坑,填了两个星期
题目大意
有一棵 $n$ 个点的树,点编号 $1,\cdots,n$。有 $Q$ 次操作,操作有三种类型:
$1\ X\ L\ R$:公司 $X$ 在编号属于 $[L,R]$ 的点上各开一家商店。如果该公司曾经有过商店,则它以前的商店全部清除,只算这次的。
$2\ X$:公司 $X$ 的商店全部清除。
$3\ C\ M\ P_1\ P_2\ …\ P_M$:有个人在 $C$ 号点,他指定了他喜欢的公司为 $P_1,\cdots,P_M$,你要找到一个离 $C$ 最近的点,使得这个点有他喜欢的公司开的商店。求这个距离。
单组数据:$n \leq 50000,\ Q \leq 10^5,\ \sum m \leq 10^5$
10 组数据共 10s。
题目大意
这是一道交互题。
现在有若干只地鼠,你只知道地鼠数量 $\leq M$,你要把这个数量猜出来。
你有 18 个风扇。每天初始,你给每个风扇设定它的叶片数 $b_i$(2 到 18 之间,从 0 开始标号),然后都让 0 号叶片指向正下。接着,每只地鼠独立地、等概率地选择一个风扇,把它的叶片往前拨一位(即原来是 $j$ 号叶片向下的现在变成 $(j+1)\bmod b_i$ 号叶片向下)。
你告诉电脑 $b$ 序列,它告诉你这天结束时各风扇指向正下的叶片编号。
你要在至多 $N$ 天之内猜出来。
$Task1: N=365,\ \ M=100$
$Task2: N=7,\ \ M=10^6$
海风吹过的夏天
刚来到 sysu,打第一场选拔赛的时候,我的感受大概就是:这帮人是连点分都不会的吗??
后来,一场一场选拔,一次一次组队练习,这帮人终于露出了面目狰狞的真面孔。这里有 GDOI 出题人,有 APIO Au,有 WC Au,有 WF 选手、cf 红名,区域赛金牌、前十、奖杯数不胜数,还有人肉 oeis 、LL万氪dalao……我第一次跟某 WC Au 组队,结果写挂的都是我的;第二次跟某 GDOI 出题人组队,不到三天就被赶了出来;第三次跟某双十和绍一 dalao 组队,才被收留了。
这里打 acm 的氛围很好。在 thu,大一就已经学业繁忙了,学生们都专心学习和舞会,而且名额基本上被那群人包了(什么 ioi rank 之和等于 6 的队啦(雾)),一本 dalao 根本都轮不上。sysu 这里没有 thu 那么巨,但是也会让你有很大压力,毕竟
sysu每年都会有几个远远超出sysu水平的人。
——知乎