文章

细节诸多………… $gcd$ 显然可以用线段树维护，但是如果是区间修改的话就不好办了。这个时候我们需要将原矩阵以棋盘守护者的位置为中心进行差分，那么区间修改就变为单点修改了，$gcd$ 自然好维护多了。 但是当我们整体加的时候，因为我们对原矩阵进行了拆 阅读更多…

$\texttt{HNOI2019}$ 终于改出来一道题目了…… 感谢 $JerryC$ 跟我一起讨论，不然我也看不懂题解。这题真的是 $\texttt{HNOI2019}$ 最可做的题啊，可想而知 $\texttt{HNOI2019}$ 有多么毒瘤了。(当然是我太蒟了) 这 阅读更多…

我们设 $n \leq m​$ ，然后开始推式子，我们将 $gcd(i,j)​$ 的值作为 “$d​$” 提出来： $$\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$$ $$=\prod_{d 阅读更多…

QwQ 这道题思路还算是比较好想.jpg 但是有些细节的东西比如证明复杂度我感觉我特别是 CF 比赛的时候不可能静下心来想到的 好吧我们讲题解 题解 首先我们设 $dp_x$表示 $gcd$到 $x$的时候还要期望 $dp_x$次才能到 $1$ 显然 $dp_1=0$ 对于 $x\geq 2$，我们 阅读更多…

传送门 老年鸽子选手过来暖站 题意就是求抽卡排名分布 题解 首先考虑暴力 我们枚举每个人抽到的卡，然后去用概率 dp 算出这个人排名为 $x$的概率 具体来讲，我们设 $f_{x,y}$表示前 $x$个人 (不包括它自己)，有 $y$个人比它弱的概率 得到方程 $$f_{x,y}=p_xf_{x-1 阅读更多…

题目戳我 神题一道，网上大部分做法都是叉积然后最大生成树（似乎一开始需要两次最小生成树？），我用的是线性变换最小生成树，本质应该差不多。 首先假设我们能枚举出所有的方案，每个方案用一个二维平面的点 $(\sum c, \sum t)$表示 我们要找的就是 $x \times y$最小的点，也就是在 阅读更多…

题目分析 设生成函数 $F(x)$，$f _ i$表示歌唱序列长度为 $i$的概率。 显然 $F(1)=1$。 而期望就是 $\sum_{i=0}^{ \inf } F(i)i$，也就是 $F'(1)$ 设生产函数 $G(x)$，$g _ i$表示你唱了 $i$声，并且还没有结束，还能继续唱的概率。 阅读更多…

题意: 给定一颗有边权的树 $T$，加入一条长度为 $len$的边，最小化直径。 Sol: 首先可以发现新加的边端点一定在原树的某条直径上，问题变成一个序列上的问题。 记 $pos_i$为 $i$在序列中的坐标，$h_i$为 $i​$下面挂的链长。 首先二分答案，假设新加的边的端点 $(a,b), 阅读更多…

题目戳我 这是 SAM 模板题，然而槽点其实挺多的吧 比如为啥要姓名分开，完全没意义啊 而且字符集开到 $10 ^ 4$有啥意义啊 做法很简单，用姓名串建广义 SAM 姓和名直接用一个不存在的字符（比如 $-1$）连起来就行了 字符集大用 map 就行了 然后第一问就是求点名串对应的节点是多少个姓名 阅读更多…

题目链接 又是一道有趣的题目 题意： 有两种操作： 修改数列某个位置的值 询问某个区间的值是否是连续的（即排序后是否单调递增且差都为 1）题目看起来很不可做，数据又非常非常大，所以就只能哈希了 一种比较简单的哈希方法是维护区间最大最小和区间平方和（或立方和之类的），然而用高斯整点就能卡掉这些算法 阅读更多…