标签 Luogu 下的文章
- 首页
- 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$。