LuoGu

# [TJOI2018]碱基序列 ## 题目描述 小豆参加了生物实验室。在实验室里，他主要研究蛋白质。他现在研究的蛋白质是由$k$个氨基酸按一定顺序构成的。每一个氨基酸都可能有$a$种碱基序列$s_{i,j}$构成。 现在小豆有一个碱基串$s$，小豆想知道在这个碱基上都多少中不同的组合方式可能得到这 ......

# [SCOI2009] 迷路 ## 题目背景 windy 在有向图中迷路了。 ## 题目描述 该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。 现在给出该有向图，你能告诉 windy 总共有多少种不同的路径 ......

# 【模板】矩阵加速（数列） ## 题目描述 已知一个数列 $a$，它满足： $$ a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} $$ 求 $a$ 数列的第 $n$ 项对 $10^9+7$ ......

# 【模板】矩阵快速幂 ## 题目背景 一个 $m \times n$ 的**矩阵**是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如 $$ A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{ ......

# 矩阵乘法 ## 题目描述 计算两个矩阵的乘法。$n \times m$ 阶的矩阵 $A$ 乘以 $m \times k$ 阶的矩阵 $B$ 得到的矩阵 $C$ 是 $n \times k$ 阶的，且 $C[i][j]=A[i][0] \times B[0][j]+A[i][1] \times B ......

# [BJOI2014]大融合 ## 题目描述 小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。 在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。 ![](https://cdn.luog ......

# [FJOI2018] 领导集团问题 ## 题目描述 一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 $v_i$，且每个成员都有响应的级别 $w_i$。越高层的领导，其级别值 $w_i$ 越小。树中任何两个结点之间有边相连，则表示与结点相应的两个成员属于同一部门。领 ......

根据题目能发现一个性质，设转化前的字符串为 $s$，转化后的字符串为 $s'$，则 $s'_{|s|}$ 为 $s'$ 的中心，即 $s'_{|s|}$ 求出来的回文串左边界为 $1$ 右边界为 $|s'|$ 找出这个性质就挺简单了，考虑先对给出的 $S$ 用 $\text{manacher}$ 求 ......

# [HNOI2012]永无乡 ## 题目描述 永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干 ......

[Problem](https://www.luogu.com.cn/problem/P3073) ### Solution 和[汽车拉力比赛](https://www.cnblogs.com/SXqwq/p/17455232.html)差不多，思路都是二分，二分$d$,但是汽车拉力比赛从一个路标开 ......

[题目链接](https://www.luogu.com.cn/problem/P4119) 首切 Ynoi QAQ 调了4个小时 ## 题目描述 写个支持以下操作的数据结构： 对于长度为 $n$ 的序列 $a$， - 给定 $l,r,k$, 求序列 $a$ 在该区间的 kth - 给定 $l,r, ......

# [USACO17JAN]Promotion Counting P ## 题目描述 The cows have once again tried to form a startup company, failing to remember from past experience that cow ......

可以得到： $$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)}{\varphi(\gcd(i,j))}\gcd(i,j)=\varphi(\mathrm{lcm}(i,j))\gcd(i,j)$$ 证明考虑 $\varphi$ 的展开式。 选取中间的式子带进去化简。 ......

# [Vani有约会]雨天的尾巴 /【模板】线段树合并 ## 题目背景 深绘里一直很讨厌雨天。 灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。 虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。 无奈的深绘里 ......

# [国家集训队] 小 Z 的袜子 ## 题目描述 upd on 2020.6.10 ：更新了时限。 作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小 Z 把这 $N$ 只袜 ......

https://www.luogu.com.cn/problem/P2709#submit # 小B的询问 ## 题目描述 小B 有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。 他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求： $$\sum\limits_{i= ......

# [AHOI2013]作业 ## 题目描述 此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。 这时小 A 碰见了一道非常恶 ......

[Problem](https://www.luogu.com.cn/problem/P2895) ### Solution 显然bfs，只不过有了限定条件，有实时的流星雨 这里提供两种做法： #### Solution 1 这也是我一开始的做法 模拟实时流星，由于bfs是按层搜的，是严格按照时间递 ......

点分树是什么/yiw 定义 $s_i$ 为 $i$ 子树内的权值和，默认 $1$ 为根 首先考虑没有换根的解法 考虑把点权变换转化为加上一个数，即 $val_{x}\leftarrow y$ 转化为 $val_{x}\leftarrow val_{x} + (y - val_{x})$ 定义这个加上 ......

[题面传送门](https://www.luogu.com.cn/problem/P8497) 不好评价？ 首先我们考虑最基础的情况，当 $k=0,l_i=r_i$ 时，相当于我们需要判定一个状态能不能被消完。 这相当于我们要执行若干次 $2$ 操作，使得每个位置要么大于等于 $2$，要么为 $0$ ......

### 题目描述 [link](https://www.luogu.com.cn/problem/P1008) ### 思路 因为 $1-9$ 且不能重复使用, 所以从 $123$ 循环至 $789$, 相应的 $2$ 倍, $3$ 倍, 即为另两个数字. 对每个数字进行拆分, 所用数字使用次数 $ ......

### 题目描述 [link](https://www.luogu.com.cn/problem/P1007) ### 思路 找到独木桥的中间位置, 最少时间考虑在端点左侧的, 向左走, 在端点右侧的向右走. 最多时间考虑在端点左侧的向右走, 在端点右侧的向左走. 最少时间即为最优情况下最多的时间, ......

### 题目描述 [link](https://www.luogu.com.cn/problem/P1003) ### 思路 我们考虑倒序, 判断每块地毯是否覆盖所求坐标, 输出即可. 若未覆盖, 输出 $-1$ 即可 ### Code ``` #include const int N = 1e4 ......

[题面传送门](https://www.luogu.com.cn/problem/P4581) 好牛逼的题目！ 首先直接 bitset 啥的看看就不太行，考虑随机化啥的。 考虑给每个想法赋一个权值，并求出每个点所能走到的想法的最小值。我们知道，$k$ 个 $[1,RANDMAX]$ 范围内的最小值的 ......

题目来源https://www.luogu.com.cn/problem/P1903 # [国家集训队] 数颜色 / 维护队列 ## 题目描述 墨墨购买了一套 $N$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令： 1. $Q\ L\ R$ 代表询问你从 ......

## 题目描述 [link](https://www.luogu.com.cn/problem/P3397) ## 思路 直接暴力枚举，每次读入进行处理 ## Code ```cpp #include #include using namespace std; int n, m; int map[1 ......

## 题目 [link](https://www.luogu.com.cn/problem/P2697) ## 思路 将字符串中 $G$ 换为 $-1$, $R$ 换为 $1$, 进行前缀和处理, 若和为 $0$, 则为稳定的宝石串，比较记录最大值 ## Code ```cpp #include u ......

## 题目描述 [link](https://www.luogu.com.cn/problem/P8218) ## 思路 直接套前缀和板子 ~~水题~~ ## Code ```cpp #include #include #include using namespace std; int n, a[1 ......

## 题目描述 [Link](https://www.luogu.com.cn/problem/P1115) ## 思路 我们用一组变量记录序列 $a[i]$, 一组变量记录当前子段和 $b[i]$, 比较 $b[i-1] +a[i]$ 和 $a[i]$ 的大小, 若大于, 说明该序列数字属于子段, ......

[Problem](https://www.luogu.com.cn/problem/P3956) ### Solution DFS/BFS 需要注意去重的时候可以重复走（因为有限定条件），只要新的步数比原来的步数小就可以走，其余情况模拟即可 细节有点多，比如需要记录一下上一步的棋盘颜色（下一次搜索 ......