标签 Luogu 下的文章

「Luogu 4173」残缺的字符串

题目链接：Luogu 4173

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

数据范围：$1 \le m \le n \le 3 \times 10 ^ {5}$。

「Luogu 4389」付公主的背包

题目链接：Luogu 4389

付公主有一个可爱的背包，这个背包最多可以装 $10 ^ 5$ 大小的东西。付公主有 $n$ 种商品，她要准备出摊了。每种商品体积为 $V_i$，都有 $10 ^ 5$ 件。

给定 $m$，对于整数 $s \in [1, m]$，请你回答用这些商品恰好装 $s$ 体积的方案数。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le V_i \le m \le 10 ^ 5$。

「Luogu 4841」城市规划

题目链接：Luogu 4841

阿狸的国家有 $n$ 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。

为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。

换句话说，你需要求出 $n$ 个点的简单（无重边无自环）无向连通图数目。由于这个数字可能非常大，你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。

数据范围：$1 \le n \le 1.3 \times 10 ^ 5$。

「CTSC 2012」熟悉的文章

题目链接：Luogu 4022

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得眼熟，小强想出了一个评定作文「熟悉程度」的量化指标：$L_0$。小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $m$ 个 $01$ 串的标准作文库。

小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即它是标准作文库 的某个串的一个连续子串），那么它是「熟悉」的。对于一篇作文 $A$，如果能够把 $A$ 分割成若干段子串，其中「熟悉」的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是「熟悉的文章」。$L_0$ 是能够让 $A$ 成为「熟悉的文章」的所有 $L$ 的最大值。如果不存在这样的 $L$，那么规定 $L_0 = 0$。

现在小强有 $n$ 篇作文需要进行判断，请你分别求出他们的 $L_0$ 值。

数据范围：输入文件的长度不超过 $1.1 \times 10 ^ 6​$ 字节。

「HAOI 2007」修筑绿化带

题目链接：Luogu 2219

为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。

如果把公园看成一个 $M\times N$ 的矩形，那么花坛可以看成一个 $C\times D$的矩形，绿化带和花坛一起可以看成一个 $A\times B$ 的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度 $X_{i,j}$ 之和，那么，绿化带的肥沃度 = $A\times B$ 块的肥沃度 - $C\times D$ 块的肥沃度。

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

数据范围：$1\le M,N\le 1000$，$1\le A\le M$，$1\le B\le N$，$1\le C\le A - 2$，$1\le D\le B - 2$，$1\le X_{i,j}\le 100$。

「Luogu 1357」花园

题目链接：Luogu 1357

小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1$ 到 $n$。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻 $m$ 个花圃中有不超过 $k$ 个 $C$ 形的花圃，其余花圃均为 $P$ 形的花圃。

请帮小 L 求出符合规则的花园种数，答案对 $10 ^ 9 + 7$ 取模。

数据范围：$2\le n\le 10 ^ {15}$，$2\le m\le 5$，$1\le k<m$。

「Luogu 5106」dkw 的 lcm

题目链接：Luogu 5106

善良的 dkw 决定直接告诉你题面：

$$ \prod_{i_1 = 1} ^ n \prod_{i_2 = 1} ^ n \cdots\prod_{i_k = 1} ^ n \varphi(\operatorname{lcm}(i_1, i_2, \cdots, i_k)) $$

请你求上述式子，答案对 $10 ^ 9 + 7$ 取模。

其中 $\operatorname{lcm}(i_1, i_2, \cdots, i_k)$ 表示这 $k$ 个数的最小公倍数。特别地，一个数的 $\operatorname{lcm}$ 是自身。

数据范围：$1\le n,k\le 10^6$。

「Luogu 2617」Dynamic Rankings

题目链接：Luogu 2617

给定一个含有 $n$ 个数的序列 $a_i$，接下来有 $m$ 个询问，询问分为以下 $2$ 种：

• Q i j k：询问区间 $[i,j]$ 排序后的第 $k$ 个数。
• C i t：将 $a_i$ 修改为 $t$。

数据范围：$1\le n, m \le 10 ^ 5$，$0 \le a_i \le 10^9$。