Day -1 在机房背板子，突然发现把洛谷上所有我写过的模板题打开足够把 edge 卡炸，真感动啊，已经学了三年 oi 了 ^v^ Day 0 车人定了西南大学的酒店，4 点过发现没带身份证，回家拿证发现堵车了，堵了 40min 才回机房。 跟着车人坐地铁去西南大学。 车人：我们选择坐地铁是因为坐公交不保证每个人都有座 然而坐地铁每人至少站了 1.5h+ 到酒店发现及其难评，厕所门关不上，锁还被拆了…… 和 LCD 复习到 11:30 车人来把电脑收了。 Day 1 T1 发现由特殊性质可以非常自然地的得出正解，此时 10:30. 由于写了非常史的 FHQ，卡常 30min. 剩下 2h 写了最低档的暴力……废了。 下午和 LCD 进行了愉快的交流，晚饭只吃到了 LCD 买的冰汤圆，辛亏买了泡面。 晚上睡得很晚，和 LCD 进行了愉快的交流 Day 2 T1 想到了一个神秘做法，考虑把相邻的合成一个点，似乎是对的。 考虑 FHQ，但由于 Day 1 的唐诗行为，思考有没有别的方法。 然后考虑用 set 实现，但并不精通 set，遂爆炸。 T2 暴力打了 N 种写法，过不了大样例。 ...

车人去 WC 了，找了一个巴蜀毕业的哈工大大三学生来给他代课。 那就简单记录一下每天都讲了什么吧 CF GYM103470 Paimon Segment Tree 给定一个长度为 nnn 的序列 aaa，以及 mmm 次区间加操作和 qqq 次询问（在处理完所有操作后再询问）。 询问操作：假设 ai,ja_{i,j}ai,j​ 表示进行完第 jjj 次操作后 aia_iai​ 的值。给定 lk,rk,xk,ykl_k,r_k,x_k,y_klk​,rk​,xk​,yk​ 查询 ∑i=lkrk∑j=xkykai,j2\sum^{r_k}_{i=lk}\sum^{y_k}_{j=x_k} a^2_{i,j} i=lk∑rk​​j=xk​∑yk​​ai,j2​ 显然可以想到的一步是，将询问离线下来差分第二个 ∑\sum∑，就可以转化成求解历史区间平方和。 接着考虑如何维护，首先处理平方： ∑(a+k)2=∑(a2+2ak+k2)\sum (a+k)^2=\sum (a^2+2ak+k^2) ∑(a+k)2=∑(a2+2ak+k2) 则只需维护区间的 0 次，1 次，2 次和与历史区间平方 ...

题意 见原题中文题面 思路 首先考虑 O(nq)O(nq)O(nq)，可以令 dpidp_idpi​ 表示当前取到了第 iii 个点的答案，可以使用滑动窗口转移。对于必选的点可以考虑清空队列实现。 尝试优化，发现 k≤3×103k\le3\times10^3k≤3×103，考虑 O(qk)O(qk)O(qk) 做法。 将 O(nq)O(nq)O(nq) 做法中的 dp 正反跑两遍。由于修改独立，对于每一次修改可以将答案分为前后两部分，对于修改位置后面的部分储存前缀 min，然后枚举小于修改位置的部分，这部分是 O(k)O(k)O(k) 的。 code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <bits/stdc++.h>#define int long long#define chmax(x, y) x = max(x, y)#define chmin(x, y) x = m ...

题意 给定一个长度为 nnn 的字符串 TTT，按照以下规则生成一组字符串 S1∼nS_{1\sim n}S1∼n​：若 TiT_iTi​ 为小写，Si=Ti+Si−1S_i=T_i+S_{i-1}Si​=Ti​+Si−1​，否则 Si=Si−1+lower(Ti)S_i=S_{i-1}+lower(T_i)Si​=Si−1​+lower(Ti​). 给定一个长度为 mmm 的序列 ppp，qqq 次询问，求 ppp 上区间 l∼rl\sim rl∼r 中最小的为 SkS_kSk​ 的周期的数。 思路 首先发现一个关键性质，若一个长度不为 SiS_iSi​ 的周期，那它一定不为 Sj(i≤j)S_j(i\le j)Sj​(i≤j) 的周期。 令 iii 为 S[i,ti]S_{[i,t_i]}S[i,ti​]​ 的周期，可以考虑二分找到 tit_iti​. 然后可以使用线段树激活的方法，将 ppp 中的值按照 tpit_{p_i}tpi​​ 从大到小加入线段树中，将询问离线下来统计答案。 tips：本题似乎卡哈希（没试过，反正同学被卡了）。 code 1234567891011121 ...

题意 给定一个长度为 nnn 的序列 aaa，每次删除其中一个长度为 kkk 的子段直到序列长度小于等于 kkk，最大化操作完之后序列的中位数。 思路 首先转化一下求解中位数，令当前中位数为 xxx，我们构造一个辅助数组 bbb，满足 x≤aix\le a_ix≤ai​ 时 bi=1b_i=1bi​=1，否则 bi=−1b_i=-1bi​=−1. 那么 bbb 中元素的和一定大于 000. 所以我们可以二分中位数的值，使用 dp 进行 check: 定义 dpidp_idpi​ 代表处理完 b1∼bib_1\sim b_ib1​∼bi​ 后 ∑j=1ibi\sum_{j=1}^ib_i∑j=1i​bi​ 的最大值，则有： i−1(modk)=0i-1\pmod k=0i−1(modk)=0，dpi=max⁡(dpi−k,bi)dp_i=\max(dp_{i-k},b_i)dpi​=max(dpi−k​,bi​). otherwise，dpi=max⁡(dpi−1+bi,dpi−k)dp_i=\max(dp_{i-1}+b_i,dp_{i-k})dpi​=max(dpi−1​+bi​, ...

题意 给定一个 nnn 个节点的有点权的树，求满足块中最大值与最小值之差小于等于 ddd 的联通块数。 n≤2000,d≤2000,ai≤2000n\le2000,d\le2000,a_i\le2000n≤2000,d≤2000,ai​≤2000 思路 不难想到枚举每个点作为最小值的答案，以选定的点为根进行 dp。 定义 dpidp_idpi​ 表示以 iii 为根的子树包含 iii 点的联通块数量，那么只需要考虑点权在 (art,art+d](a_rt,a_rt+d](ar​t,ar​t+d] 之间与点权等于 arta_rtar​t 但是编号小于 rtrtrt（这一步为了去重）的点。 我们令不满足上述要求的店 dpdpdp 值为零，则有转移方程： dpi=∏(dpson+1)dp_i=\prod (dp_son+1)dpi​=∏(dps​on+1) code 1234567891011121314151617181920212223242526272829303132333435#include <bits/stdc++.h>#define int long long# ...

11.27 倒计时三天。 青岛那边的回来了，车人安排了一场 oifha 的模拟赛。 因为车人的蜜汁操作延迟到下午打了……结果被模拟赛日爆了 qwq。 T1 2100 的一个无敌思维题，打了一个多小时的模拟最后差两倍常数，气得要死，最终 3h 过 T1（ T2 正解 ODT，根本不敢想。 T3 3000，困难。T4 LCT 上 DP，肥肠困难。 感觉非常难受，急需一场正常的 NOIP 模拟赛。 11.28 倒计时两天。 无敌，再次卡 T1.（我吃柠檬sb思维题） 晚上回来听教练讲述他的传奇人生： 我自信停课一个月，考场上拿了SD第二。 我回来后就每天在机房打游戏，觉得自己特别 nb，别人停了一年，我只停了一个月就SD第二。 一直玩到了第二轮，又是SD第二。 …… 打板子ing…… Misaka Mikoto 保佑我 NOIP RP++！！！ 11.29 看了看板子，下午去了 CQBZ 试机。 很难受，尤其是椅子和键盘 车人再次给我们打气！ 加油吧，在死回去补文化课前赢一把！ 感谢欧尼酱的祝福（还没有拿下抱歉 11.30 NOIP!! 早上，买了个铜锣烧准备在考场上吃 到达 CQB ...

终于要到了吗…… Day -1 考前一天 被模拟赛的结论题冲爆，感觉很累…… 下午开打板子，感觉心里踏实了一点~~ 希望能收到祝福qwq 收到了~~ Day 0 在家水了一上午之后准备上刑场了……（调了一早上负环） T1 写了 O(Nlog⁡2N)O(N\log^2 N)O(Nlog2N) 的丑陋贪心…… T2 想复杂了，等想简单了之后已经写完了……然后导致 2h 调试…… T3 写了 O(N2)O(N^2)O(N2) 后时间不够没想到性质，遗憾离场qwq…… 不会 DP 导致的…… Day 1 教练叫去吃饭，交流之后才发现考场上蠢完了，被吊打…… 看起来坠机了，有一种被 CSP 车裂的感觉…… （不得不放出才看的一方通行手撕御坂）

前言 众所周知，KMP是对于刚学习串串的新手们的第一坨屎第一个难关，而网上的各种对ne数组的讲解又非常复杂，所以本文将以DFA的视角对KMP算法进行一个解释，来解决困扰着一代又一代OIer的神秘算法。 DFA 出门右拐->自动机 - OI Wiki (oi-wiki.org) 引入 首先明确，我们的自动机是用来进行字符串匹配的，所以我们对模式串构建自动机。 放个例子(对ABC构造KMP自动机，q3q_3q3​ 为可接受状态)，可以先感性理解： 自动机构造 我们从上图也可以看出，自动机的状态 qqq 代表当前的后缀文本串与模式串所匹配的长度，可接收状态就是 ∣s∣|s|∣s∣. 接下来考虑转移 δ(q,c)\delta(q,c)δ(q,c)，分为三种情况： 当 c=S[q+1]c=S[q+1]c=S[q+1] 时，匹配长度加一。 当 q=0q=0q=0 且 s[q+1]≠cs[q+1]\neq cs[q+1]=c 时，并没有任何字符与其后缀匹配，故匹配长度仍为 0. 当 q>0q>0q>0 且 s[q+1]≠cs[q+1]\neq cs[q+1]=c 时， ...

好吧起因是考完试闲的没事，就无聊做了一个~~ 里面介绍可能比较简陋，具体操作需要摸索~~ 如果有前后文不一样请忽略，因为这个是我从我远古时期的版本改出来的~~ 下面是链接：crazydogs.lfyszy.top