CF407E k-d-sequence

首先特判 $d=0$ 的情况。否则显然一个合法的区间所有数 $\bmod d$ 都相等。

将这样的区间拉出来，一个个考察，显然可以将所有的数都 $\div d$，这样就变成了公差 $=1$ 的等差数列。一个区间 $[l,r]$ 合法，当且仅当：

• $[l,r]$ 中的数两两不同。

• $r - l + 1 + k\ge \max{a_i} - \min{a_i} (l\le i\le r)$。

第一个容易处理，直接开一个 map 记录一下每个数最后出现的位置即可。

对于第二个限制，化简变为 $r + k\ge \max{a_i} - \min{a_i} + l - 1$，开一个线段树维护右边这依托即可，修改 $\min$ 与 $\max$ 可以开两个单调栈，这是套路的。

所以每次要查询区间内第一个值 $\le val$ 的位置，采用线段树二分即可。复杂度 $O(n\log n)$。

CF587F Duff is Mad

暴力做法是建出 ACAM，每次询问时对于 $s_{[l,r]}$，每个字符串在 ACAM 上的 endpos 的 fail 树的子树内点权全部 $+1$，然后查询 $s_k$ 在 ACAM 上的所有节点点权之和。

考虑对于 $|s_k|$ 根号分治。

Day 0

早起赶到火车站，做了 4.5h 的复兴号从杭州东到北京南，然后做了 1h 地铁才到酒店，去对面吃了肉夹馍，某些人 9 元买了 7 元优惠券 /cf。

下午和晚上在酒店魔域，好像他们夜骑去面基了。。

10 点半还打了个 div2，花了 20min 写了个 E，抢了一血，很爽。口胡了个 F 就睡了（但好像假了？。

Day 1

早上 5 点半就醒了，去对面吃了馄饨和豆腐脑（第一次吃豆腐脑 /tuu）。骑车去北大报道，然后开幕式，很高效，一下就好了。

然后去试机，电脑感觉还行，虽然是 win，但是挺好用的。写了个试机题就润了（如果早知道试机代码不会被删。

下午正式比赛，先开 T1，感觉不难，稍微想了一下就会了，写了 $O(n\log n)$ 的倍增哈希被卡成了 91，改成二分就过了，大概 1h。

开 T2，不太会，写了状压 23pts。然后开 T3，也不会，写了暴力 dp 32pts。

开始疯狂思考，浪费了 1h+，直到最后 40min 才发现 T3 有 ddp 的部分分，赶紧开冲。

Day -1

学校请假，上午去机房 goose goose duck，好爽。

下午去试机，车费好贵 /fn/fn/fn。

键盘手感好评，居然和我用的完全一样。

晚上不知道在干啥。

Day 1

早起，有点没睡醒。

车上背了一下 pb_ds 的单词，相信是用不上的。

开考 20 min 先把 T1 写了，然后开始坐牢。

T2 是数数，感觉不太会，于是先开 T3，发现 $O(nq\log^2 n)$ 有点傻逼，写了一下。

Day 0

上午学长们在 NOIp，初中生没得去，在家颓废。

下午去现场看了一下，感觉还不错，被采访了，一时半会儿没答上话来。

希望明天不要太寄，睡觉！

Day 1

上午最早到，有点尴尬，不过还好过一会儿孙老师就来了，8 点比赛就开始了。

今年题目比去年人性很多，大概是给你各种类型的信息，让你 encode 和 decode，encode 后的数列长度越小分越高，你还可以写一个词典。

第一题非常困难，要输入各种语言的字符，不太会，于是先鸽了。

然后发现图片信息的题目很好做，随手写了一个就交了，但是一直格式错误，人快崩溃。还好最后瞎改改过了，打开 80pts。

然后去做其他题，主要是要找出 出现次数*长度 最大的几个子串，感觉很 hard。

Day -6

烧烧烧！38.2！！感觉要寄了！！！

Day -5

明天是 csp 前最后一场 noip 联考了，希望能好好打。

又是颓废的一天，唯一的成就是 tetr 40lines 突破到 2:05 了。

联考就打了一个题，t2 比较麻烦的初始 dp 想出来了，但是非常 ez 的修改不想写就摆烂，光荣挂成 10pts。

Day -4

虽然想好好打模拟赛，但是只想出来一题，赛后发现是 *2800，还是很欣慰的。

明天加了一场 csp 模拟赛，希望别太毒瘤呜呜呜。

又 vp 了两场 cf，AK 了一场，虽然第二场某人说全是诈骗题，但是感觉思维含量还是有的。

ShaoJia的游记

其实没有游，都在ez机房。

人生第二次打 ACM（第一次算是 THUPC 吧）。

Day1

中午去面馆吃面，会到二中已经 11:55 ，跑去机房就开始了。

一下就开了 1011 签到题，结果误以为红色是 WA，想了好久那里挂了，结果 10 分钟后有人告诉我我过了。/qd

全场就做了 1011 和 1012 两道题，成为全队最卷选手。总之把 Shaojia 和 Cxny 带飞了。

中途帮 Shaojia 调了 1007，最后竟然是因为没加 inline 而爆栈了。/qd

最后在死磕 1001，一道 KMP 毒瘤题，WA 了两发无果。

Solved 6 problems，Rank 79。