# NOIP 游记 [更好的阅读体验](https://www.cnblogs.com/wingheart/p/19179292) 洛谷每张图片都要重新传，嘟嘟嘟。 ## 2025.10.31 明天要考 CSP-S 了。 ![](https://cdn.luogu.com.cn/upload/image_hosting…

# NOIP2025 之组题人【数据删除】记 [更好的阅读体验](https://www.cnblogs.com/wingheart/p/19287386) 感谢管理员审核！ ## 前言 《长文警告》《消极情感警告》 > 要是有人不希望透露名字等，请告诉我。 这个标题传洛谷不知道能不能过审。实测并不行。 了解我的人应该…

可以用生成函数和多项式取模做。本质上和矩阵乘法差不多，但是更好写。 观察发现，若所有位置奇偶性相同，则用操作二可以做到合法。操作一可以看作反转相邻两个位置的奇偶性。 当且仅当奇数高度位置的个数为奇数个，且偶数高度位置的个数为奇数个，无解。否则有解。 按照 $n \times m$ 的奇偶性分类讨论。只有 $2 \mid…

在讨论《NOIP是否会对以下算法考察》回复：

@[SalN](luogu://user/371825) 不能因为形态比较像就是吧。 那么所有串串自动机算法都是 trie，因为从某种程度上完全是一样的形态吧，只是多几个指针什么的而已。笛卡尔树、FFT 等都是分治，从某种程度上形态也是一样的吧。

在讨论《NOIP是否会对以下算法考察》回复：

@[SalN](luogu://user/371825) 看成圆方树是不是有点扯，我认为不算

在讨论《NOIP是否会对以下算法考察》回复：

网络流不会，这个是省选算法吧。树剖和欧拉回路应该可以考的，其他我不清楚。

在讨论《感觉正赛时间流速比模拟赛快怎么办》回复：

@[SnowTrace](luogu://user/580036) 建议有意识地监控自己有没有上头，及时打断上头。卡题或者写了假算红温的时候强制打断自己，先看后面，平静之后再回来看。我觉得如果能去个洗手间是极好的。

在讨论《AI 已经拿下本题》回复：

打不过 AI/ll/ll/ll

在讨论《求调，样例过WA0pts》回复：

以及建议 base 大于字符集大小

在讨论《求调，样例过WA0pts》回复：

@[Furina_Saikou](luogu://user/561907) 1. 第 50 行 `tr[p]=((tr[p]+x)%k+k)%k;` 的 $x$ 应该是 $y$ 吧。 2. 第 61 行 `if(mid>=x&&mid<y)return ((query(ls,l,mid,x,y)*bas[r-mid]%…

# [CF1381D The Majestic Brown Tree Snake](https://www.luogu.com.cn/problem/CF1381D) [更好的阅读体验](https://www.cnblogs.com/wingheart/p/19223514) ## 题意 给你一棵 $n$ 个点的树。…

# [P13309 演剧](https://www.luogu.com.cn/problem/P13309) [更好的阅读体验](https://www.cnblogs.com/wingheart/p/19216720) ## 题意 A 和 B 在玩游戏。 给你一个长度为 $n$ 的序列。A 先手。 每一轮，先手会选择…

在讨论《求NOIP冲刺方法》回复：

@[asd890123](luogu://user/1074084) 这样的话，我比较建议多打打模拟赛积累经验。没有什么必要现在学新算法。 您的 CSP 这么高分，我觉得肯定有 NOIP 一等水平，对标去年难度，可以冲着切两题或者一题+打满暴力去打吧。

在讨论《求NOIP冲刺方法》回复：

@[asd890123](luogu://user/1074084) 赞同楼上。 初二而且提高知识点没有学完，如果没有人要求你 NOIP 要达到多少多少分，建议只是把 NOIP 当作一个体验。建议按照正常进度学习，赛前打一点模拟赛就差不多了。

在文章《【欢迎投稿】有奖征集 OI 小知识点，思考题和科普，包括“广为人知”但大纲未收录的内容！》发表评论：

专业！

在讨论《求今年 WC 分数线》回复：

@[_Acheron_](luogu://user/984018) 谢谢，以及我觉得参考去年 316 的水平，286 希望挺大的

在讨论《求今年 WC 分数线》回复：

cu ball，以及想问下去年是多少呢？

在讨论《洛谷超空间 CE，但在其他网站上正常过编》回复：

@[ryf_loser](luogu://user/761649) `fac[5000005]={1}` 全局变量直接在这里初始化大数组，在洛谷上会炸掉，但是在 CCF 评测机上没有问题。原因忘了。 最好不要这么写。可以在 main 里面初始化。

# AC 自动机的一些匹配板子 [原文链接](https://www.cnblogs.com/wingheart/p/19185309) ## AC 自动机介绍 参考 [OI-Wiki AC 自动机](https://oi-wiki.org/string/ac-automaton/)。 如果你已经会 AC 自动机（包括…

在讨论《关于 dijkstra 的堆》回复：

@[TallBanana](luogu://user/780698) 改了 dis，往堆里面再插入数字的时候可能会乱掉。

在讨论《萌新刚学 AC 自动机》回复：

@[oyoham](luogu://user/957618) 谢谢回答！/bx 不过应该有比 $q\sum L$ 更优的做法，以及我没有在问 CSP-S t3，因为那题不用去重吧。

在讨论《萌新刚学 AC 自动机》回复：

@[Kevin_Lsy](luogu://user/359287) 谢谢/bx/bx

在讨论《萌新刚学 AC 自动机》回复：

@[fjy666](luogu://user/366338) 谢谢/bx/bx

在讨论《萌新刚学 AC 自动机》回复：

@[TallBanana](luogu://user/780698) 欸你说的对，谢谢你/bx

在讨论《萌新刚学 AC 自动机》回复：

@[P2441M](luogu://user/1063026) 但是跑 $t$ 的时候，在 fail 树上可能是在跳横叉边而不是树边，所有 $u$ 在 fail 树上可能不是一条链，这个复杂度仍然可以证明是线性的吗？ 似乎很难卡到劣于线性？

在讨论《萌新刚学 AC 自动机》回复：

@[oyoham](luogu://user/957618) 可能是我没有讲清楚，有多个 $t_i$，每个 $t_i$ 这么做都这么做，是 $O(qL)$ 吧？还是说我理解错了您的做法？

在讨论《萌新刚学 AC 自动机》回复：

@[TallBanana](luogu://user/780698) 是指对每个 $t_i$，遍历到的每个状态 $u$，在 fail 树上把 $u$ 到根的链覆盖掉吗？但是每个 $u$ 要跳很多个 fail，复杂度是对的吗？/kel

在讨论《萌新刚学 AC 自动机》回复：

@[Lyz09](luogu://user/284013) 您指的是，把串串按照长度分类，然后哈希吗/崇拜

萌新刚学 AC 自动机，有两个问题学不明白，感谢大家帮助！/bx/bx/bx 0. 我是对着 OI Wiki 学习的，网上没有找到更全面的博文，如果有推荐博文希望分享一下，谢谢/bx 1. 对每个 $t_i$，求有多少 $s_j$ 是它的字串（注意 $s_j$ 在 $t_i$ 中多次出现之记一次）可以用 AC 自动机或…

在文章《加训串串！》发表评论：

诶诶 t1 是“然后可能 B、C 会出现人数超限的情况，再排序贪心取即可。”是根本不可能出现的情况啊，我怎么这么菜