在讨论《【赛时答疑】东北大学秦皇岛分校第十三届“图灵杯”程序设计竞赛》回复：

qp

[TOC] # 字符串部分 ## 一. 字符串通用算法 ### **Ⅰ. 字符串哈希** 字符串哈希封装模板（双模数哈希版本） ```cpp struct Hash { const int Mod[2] = {(int)1e9 + 7, 998244353}; const int base[2] = {233, 177…

对于离散的概率生成函数 $$ \begin{aligned} f_X(x) &= \sum_{k} P(X=k)x^{k} \\ E(X) &= \sum_{k}k\cdot P(X=k) = f'_{X}(1) \\ E(X^2) &= \sum_{k} k^{2}P(X=k) = \sum_{k}[k(k - 1)…

在文章《ABC262Ex Max Limited Sequence 题解》发表评论：

orz讲的最清晰的一篇

> 也可以从我的做题记录里查看 [https://www.luogu.com/article/zzi2vm6q](https://www.luogu.com/article/zzi2vm6q) **[CCPC2024 重庆站 D.有限小数](https://qoj.ac/contest/1840/problem/962…

#### **待筛选题目** LuoguP2178【字符串，紫】（二周目复习，强制使用 SAM 来做） CF141D【图论，\*2300】 CF960H【数据结构，\*3100】 https://codeforces.com/problemset/problem/2140/D https://codeforces.co…

在文章《第三场积分赛 yky出题部分 解题报告》发表评论：

/bx/bx/bx 最后那个武汉邀请赛G vp 的时候也把我给硬控了/ll

在文章《隐马尔可夫模型【学习笔记】》发表评论：

@zxh_qwq 学弟加油鸭，我这是大学文化课的笔记，根本记不住，所以就记到洛谷博客上了

upd on 5.25 - 修改了三处笔误 # 隐马尔可夫模型 ## 一. 隐马尔可夫模型的性质 - 具有马尔可夫性的状态序列 $X$，但这个序列是不可被直接观测的，故称之为**隐状态序列**，我们假设隐状态共有 $N$ 种取值。 - 还具有一个**证据状态序列** $E$。对于所有时刻 $t$，可观测到与隐状态 $X…

- **组别：C++ A组** # 第一轮正赛 ## Day -2 小岛大风橙色预警，说是比赛当天要刮究极大风（8 ~ 11 级说是），比赛推迟了，但时间未知。 笑点解析，学校发布的停课通知比🏀杯比赛推迟通知还要晚一天。 ~~当时我还打开群说了一句“不会撞天梯赛或者邀请赛吧”（伏笔）~~ ## Day 0 加睡！加睡…

## 关于主定理的一个简洁的证明 upd on 2025.5.10 修改了一处笔误。 ### 前言 上个赛季某次在 1121 训练时吐槽主定理难证，被翔哥听到骂了一顿，然后他给我讲了一种跟网上主流的证明方法非常不同的方法，仅用到高中学的简单的数列递推和归纳法，令我耳目一新，不过当时一带而过了，并没有记录下来。 直到今天…

令 $g_i$ 代表恰好有 $i$ 个 $2023$ 时的总方案数，$M = \lfloor\frac{n}{4}\rfloor$。 当我们遇到这种“恰好有多少个满足某个条件”的计数时，第一步大致有三种思考方向。 - 第一种就是直接计算 $g_m$。 - 第二种是考虑 $h_i = \sum\limits_{j \ge…

令 $sum_i$ 为位数为 $i$ 的所有数之和，$tot_i$ 为位数为 $i$ 的数的个数，$m$ 表示 $n$ 的位数。 令 $$ \begin{aligned} F(x) = \prod_{i = 0}^{m} (1 + 10^{i}x)^{tot_i} \end{aligned} $$ 考虑每一项的含义，$…

在文章《图灵杯主办方之会长游记》发表评论：

然而我并没有验 T13/xk，只有萌神把所有题都验完了

## 给洛谷贡献的题 ### 红 [P11461 Good Luck & Have Fun](https://www.luogu.com.cn/problem/P11461) ### 黄 [P11463 N角进攻](https://www.luogu.com.cn/problem/P11463) ### 绿 [P114…

**这里是官方题解。** 因为占领每个城堡所产生的收益是相同的，所以最优情况下一定是按照 $a_i$ 从小到大的顺序占领城堡。 假设最终兵力超过对方时，t1e 已经额外占领了 $p$ 座城堡，那么这 $p$ 座城堡一定是越早占领，产生的收益越多。 有了以上两个结论，我们可以先将 $a_i$ 从小到大排序，设 $f_i$…

**这里是官方题解。** 可以将序列分为三个部分，左边 $\lfloor \frac{n}{2} \rfloor$ 个，右边 $\lfloor \frac{n}{2} \rfloor$ 个，最中间的 $1$ 个。 容易观察到，进行恰好 $n$ 次传球后，左边的部分会完全翻转到右边，而右边的部分也会完全翻转到左边，而最中…

沉默了，长话短说。 7题，rk53，AD都没过。 队友 C 麻了，但我凭借自己的超鬼发挥错失了一次非常有希望抽到金牌的机会。（另外，这还是我们队中一位大四学长的退役之战，打完这场他就要全身心投入考研了，感觉更遗憾了） 赛前：我要加训数论（实则一直在训cf和数据结构） 赛后：训了个集贸。 我们队中并没有专精数学的大师，但…

在文章《49th ICPC南京站【游记】》发表评论：

@RedLycoris 昆明和南京都去了一车金牌队，但是昆明发的牌子稍微多一点，所以理论上南京更难打一点，但昆明强度也很高

## 省流 这是我们队 $2024$ 赛季的第一站，阵容是我，BrotherCall 和大四神犇 snowy。 根据民调，我们队赛前预测南京是今年 ICPC 强度最高的赛站，依据网络赛的排名我们队也只能排在银尾。 最终 $\text{rk}79$ 打银了。同时这也是我 ACM 生涯中第一块 ICPC 银牌，算是意料之中…

在文章《CCPC北京市赛游记》发表评论：

伟大无需多言！

在讨论《请问省队中的 A、B、C、D 以及 A1 之类的是什么意思？》回复：

- A 类是基本名额，每个省都有 $5$ 个，也就是全省 NOIP+省选 综合成绩前五名。 - B 类是奖励名额，根据每个省 NOIP 参赛人数，NOIP 平均分以及 NOIP 省一等线分别计算，具体见 [这里](https://www.noi.cn/xw/2022-02-14/755059.shtml)。 - C 类…

在讨论《【水】家长不让熬夜怎么办》回复：

确实

在讨论《【水】家长不让熬夜怎么办》回复：

而且评论里大部分人都称这场比赛为 $\text{Chinese round}$ 。

在讨论《【水】家长不让熬夜怎么办》回复：

@[StaroForgin](/user/105141) 不懂啊，台湾省的选手出题怎么就zzmg了？关于zz的事情人家一个字没提啊。

在讨论《出题人再次透露。。。》回复：

考古膜拜神仙

在讨论《关于题解的问题》回复：

@[Kobe303](/user/292300) 这个做法是没法被卡成 $kn^2$ 的。 注意到他在第二层循环前加了一个 ```cpp if(!Dist[i-1]) continue; ``` 这样第二层循环的总复杂度就是 $O(n\cdot\sum D_i)$ ，是可以过的。

在讨论《家长直呼太暴力！这些算法可能会被删除》回复：

哈哈哈哈xswl

在讨论《翻译错了啊》回复：

@[He_Ren](/user/73687) %%%

在讨论《求助》回复：

@[包思远BSY](/user/560020) 不明白为啥要用最短路啊，还有就是 $\text{SPFA}$ 的时间复杂度是 $O(nm)$ 的。 这里我们说的时间复杂度一般是最差情况下的时间复杂度，而那个 $O(km)$ 是图随机生成条件下的期望时间复杂度，手动构造数据是能卡成 $O(nm)$ 的。