Yurchiu's Blog
链接：P2679 [NOIP2015 提高组] 子串。 题意 现在要从字符串 AAA 中取出 kkk 个互不重叠的非空子串，然后把这 kkk 个子串按照其在字符串 AAA 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 BBB 相等？ 注意：子串取出的位...
链接：P1541 [NOIP2010 提高组] 乌龟棋。 题意 乌龟棋的棋盘是一行 NNN 个格子，每个格子上一个分数 aia_iai（非负整数）。棋盘第 111 格是唯一的起点，第 NNN 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 乌龟棋中 MMM 张爬行卡片，分成 4...
链接：P3629 [APIO2010] 巡逻。 题意 有一棵节点数为 nnn 的树，要求我们在树上加上 kkk 条边，使以根（111 号节点）为起点遍历时经过的”路径”最短。关于“路径”，有以下几个要求： 加的边必须且仅经过 111 次。 允许出现自环。 从 111 号节点出发，回到 11...
归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。 图示： 模板 #include<bits/std...
这里是一些关于 LCA 的题目。 P3398 仓鼠找 sugar 题意 在一棵有 nnn （≤105\le10^5≤105）个节点的树上，有 qqq （≤105\le10^5≤105）个询问，每次询问两个点对 (a,b)(a,b)(a,b)，(c,d)(c,d)(c,d) 之间的最短路径的...
倍增是根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作的一种思想。 快速幂 快速幂使用了倍增的思想。见文章数论模板。 树上倍增 最近公共祖先 树上倍增可求最近公共祖先（LCA）。个人约定：一个点向根节点方向移动称为“向上跳”。 对于一个有 nnn 个节点的有根树，我们设 f(i,j...
本文以题解为主。模板传送门。 P2504 [HAOI2006]聪明的猴子 题意 给出 nnn 个点（≤103\le10^3≤103，以坐标形式给出），mmm 个询问（≤500\le500≤500），问有几个给定的数比这 nnn 个点的最小生成树的最长边还大。即，求最小瓶颈生成树的瓶颈。 点...
本文主要以题解为主。以“关押罪犯”为例介绍并查集的用法。 P1525 [NOIP2010 提高组] 关押罪犯 2×1042\times 10^42×104 个罪犯，10510^5105 个仇恨关系，使用分在两个监狱的方式，使得最大仇恨值最小。 题解 二分答案+二分染色 似乎和并查集无关呢...
本文为树状数组模板。其中，lowbit() 在状压 dp 一文有所介绍。 单点修改，区间查询 模板题。 树状数组保存的是前缀和。 Update：修改 xxx 的值（加上 data）。 Query： 查询 [1,x][1,x][1,x] 区间：query(x) 。 查询 [l,r][l,...
改编自 Vim 入门基础。 配置 在终端输入vim ~/.vimrc 然后添加配置代码： set ts=4 set sw=4 set smarttab set number color desert syntax on set cindent set guifont=Consolas:h16...
关于基环树的东西。 一些知识 基环树：树加上一条边。点数和边数相同。它是图。可看作环上挂着一些树。 基环内向树：环上挂着的树的树根指向环。 基环外向树：环内节点指向环上挂着的树的树根。 解决方案：枚举环上断点、断边。 P5022 [NOIP2018 提高组] 旅行 题意 任意选定一个...
以下是一些关于树的直径和重心的题目，为本蒟蒻在上网课时所整理。 一些知识 树的直径 定义：树上最长链。 推论，前提是边权非负： 一棵树若存在多条直径，则必然相交于同一点。 任意一点的最远端是树上直径上的一个端点。 若多条直径只有一个公共点，必定互相平均分割。 树的重心 也叫树的质心。...
以下是一些树形 DP 题目，为本蒟蒻在上网课时所整理。 顾名思义，树形 DP 是发生在树上的，状态转移发生在父结点和子结点之间。 状态转移的方向：一般叶子结点向根结点转移，也有相反的时候。 树的结构是递归的，我们常在树上进行 dfs 控制转移发生的次序。 由叶子结点向根结点的转移是发生在递归返...
By Yurchiu.
