题目分类整理

几何 线段 线段与多边形

题意：求各线段与多边形的公共长度

- F -

思路：考虑向量与每条边的关系，类似扫描线求解

线段与点

题意：线段每碰到点之后会延长一段，问每个线段能碰到多少点

- F -

思路：通过线段树维护每个线段

题意：输出每段被覆盖了k次的线段

- D -

思路：类似扫描线处理，做一个前缀和

线段与线段

题意：两线段是否相交

思路：取线段低端点最大以及高端点最小判断即可

题意：将若干线段放到大线段上或从上面拿走，若有多个位置符合条件，放坐标最小的

Lot - 洛谷

思路：通过set去维护

圆 圆与圆

题意：求两圆的公共面积

- D -

思路：先判断两圆的关系，然后求解

向量 向量与向量

题意：求两两向量间的最小夹角

- C -

思路：转化成角度，进行排序

点

题意：已知点坐标，计算平行四边形数量

- D -

思路：排序后，通过map储存向量即可

题意：在一个三角中，有若干点，找到离斜线上每个点最近的点

- E - ( by Menci)

思路：考虑每个点最近的点，贪心

题意：给定2*n个点，输出所有能使其中n个点变成另外n个点的增量

2023杭电多校3 - Judge

思路：数据随机的情况下可以暴力或凸包

题意：给定n个点，询问给定矩阵内有几个点

[] 园丁的烦恼 - 洛谷

思路：二维数点板子，按横坐标排序后通过数据结构维护

题意：从A点推B点的箱子到C点的最小步数

思路：B到C的曼哈顿距离必定有，要考虑的是是否要转弯，A到B有横纵两种策略，取最小

字符串 单串 构造

题意：修改最少数量的字符，然后可以更改字符顺序，问最小字典序的回文串是什么

- C -

思路：统计数量，由小到大修改

题意：长为n的字符串，每次可以删除s的最后一个字符，或将字符串s变成ss，问使得整个串的长度为k时的字典序最小字符串

Erase and (Hard ) - 洛谷

思路：定义已构成的最小字典序字符串为0~p-1，那么每次比较i和i%p的字符大小即可得到答案

题意：最少操作次数使得字符串相邻两位不同

- C -

思路：暴力

题意：给定一个只有三个字母组成的字符串，找到一个长度至少为其一半的回文子序列

- 1178E - ( by Menci)

思路：根据鸽巢定理，每次选择四个，必有两个是重复的

题意：每个字符属于两个人中的一个，且都有一个权值，可以翻转前缀或后缀的归属，问某个人的值最大能是多少

- B -

思路：预处理前后缀求值

计数

题意：计算4的倍数的子串，可含前导零

- B -

思路：100是4的倍数，判断两位即可

题意：计算9的倍数的子序列，可含前导零

登录—专业IT笔试面试备考平台_牛客网

思路：dp[i][j]为以i结尾的余数为j的方案

题意：标记不相邻的一些位置，删除其它位置，问最后形成的字符串本质有几个不同的

F -

思路：定义dp[i][j]表示选择了前i个，结尾为j。设前一个为k，当

，等于该项，否则等于i-2项+1

题意：选择一些字符组成序列，要求对于任意i

E - Chain

思路：定义dp[i][j]表示选择了第i项，状态为j的方案数。从i转移到j，若相等，那么j直接加上i的方案，否则要求i的状态中j没出现过

回文

题意：计算满足左半边等于右半边，且都是回文串的子串数量

#/C

思路：预处理然后暴力，或回文树+hash判断

题意：当一个字符串是k阶回文，那么它前一半是k-1阶回文，问字符串的每个前缀是几阶回文

- 洛谷

思路：定义dp[i]表示前缀i是几阶回文，递推

题意：求出k阶回文串的数量，k阶回文串，满足本身是回文，左右为k-1阶回文

- 洛谷

思路：区间dp或者哈希暴力或者回文自动机

题意：将回文串分成k+1段后合并，要求合并后的回文串不同于原来的，输出最小k

- B -

思路：暴力判断k=1的情况

前后相等

题意：给定s和t，要求构造同等长度的p和q，使得p+s+q+t前后相等，输出方案数

登录—专业IT笔试面试备考平台_牛客网

思路：s和t的位置不影响结果，假定|s|>|t|，分类讨论，当s不会覆盖到自己，那么有|s|-|t|的位置可以随便放，否则通过Z函数判断前后缀是否相同

题意：可以将字符串的相同子串删除，问剩余的最小字符串长度是几

- 洛谷

思路：定义dp[i][j]为将i~j的字符串缩成的最小值，通过kmp求解最小的周期

题意：要求对于每个前缀i，求出其前缀等于后缀且不重合的方案数

[] 动物园 - 洛谷

思路：先kmp求出每个答案，构建树，然后在树上快速求解

题意：计算既是前缀又是后缀的字符串在整串中出现的次数

and - 洛谷

思路：Z函数求出哪几个符合条件，然后后缀和求解

题意：m次询问，求出给定两个前缀的最长

【模板】失配树 - 洛谷

思路：构建失配树，求lca

题意：字符串仅包含0、6、8、9，可以将任意区间翻转180度，问有几个不同的字符串

- C -

思路：总数减去区间端点为00、88或69组合，特殊的当字符串全是6或者9的时候，不管怎么翻都和原来的不同，所以要去掉串本身

题意：给定s，问经历多少次操作使得s变空。每次操作有一个空串t，依次添加

个

到t后面，然后将s变成t

E -

思路：当相邻两个数字都大于1的时候，操作会无限下去。第i个字符会复制前一个字符串

次，定义

为i到n操作了几次

判断

题意：给定一个字符串，问能否由若干个中心对称串构成

登录—专业IT笔试面试备考平台_牛客网

思路：预处理，然后判断

题意：只包含A、B、C的字符串，每一秒A变成BC、B变成CA、C变成AB，问t秒后第k个位置什么

D - ABC

思路：第t秒k位是什么可以从t-1秒k/2转移过来，通过递归实现

方案

题意：输出满足既是前缀又是后缀又在中间出现过的最长字符串

- 洛谷

思路：kmp找到前后缀的最长字符串，然后在中间找一个最大的

题意：字符串每次将首个字母移动到末尾，对所有字符串排序，输出按顺序的最后一位组成的字符串

[] 字符加密 - 洛谷

思路：将原串扩展一倍，用后缀数组求解

题意：给定原串s1，删除s1的一个字符得到s2，使得s2字典序最小，依次操作直到字符串为空，将所有的字符串连接，输出第p位字符

- C - ( by Menci)

思路：先找到p是第几个字符串，然后删除的方式可以通过栈实现

双串

题意：计算[a, b]中满足条件的数

- D -

思路：数位dp

题意：最长公共子序列

F - LCS

思路：dp[i][j]表示第一个串前i位，第二个串前j位的最长公共子序列

题意：找k组相同的子串，长度最大

思路：dp[i][j][k]第一个串前i个第二个串前j个选k组的最大值

题意：删除第二串最短的一段子串，使得剩下的字符串是第一个字符串的子序列

- C -

思路：预处理第一串前i个能匹配第二串的最大前缀，以及后i个能匹配的最大后缀，输出方案

题意：求b和b每个后缀的lcp长度以及b与a每个后缀的lcp

【模板】扩展 KMP/exKMP（Z 函数） - 洛谷

思路：第一个是z函数，第二个是求b+a的z函数

多串 构造

题意：将所有字符串连接起来，输出字典序最小的那个

思路：自定义快速排序

题意：构造字符串，使得每个串与其至多有一个不同

Spy- - 洛谷

思路：暴力枚举每个串哪一位不同

题意：构造删除序列，按照序列删除对应的所有字符，在过程中要求每一串都不相同

H题

- 2023 Xian - ( by Menci)

思路：逆过程考虑，只要最后留下的那个字符数量不同，其它字符随意摆放

计算值

题意：计算串在所有串中出现次数*权值*长度

思路：后缀自动机计算出现次数以及权值

题意：多次计算串在部分串出现的次数

Mike and - 洛谷

思路：先构建fail树，利用树状数组维护前缀和求解

题意：刚开始集合中有k个串，有三种操作，+、-表示将编号i的字符串加入集合或从集合中删除，若已经存在或已经删除则不变，？表示询问集合中有多少个字符串作为子串在当前字符串中出现

- 163E -

思路：构建AC自动机，每次操作即插入或者删除，查询过程暴力过不了，将fail树拍平成链，通过树状数组加快计算进程

题意：有三种操作，在字符串中加入一个字符或者删除末尾一个字符或者将字符串输出到屏幕中，寻味第x个串在y个串中出现的次数

[] 阿狸的打字机 - 洛谷

思路：构建fail树后，答案即输出y子树中所有包含x的数量，离线询问后，通过树状数组维护答案

题意：给定n个只含0、1、？的字符串，问有多少个字符串至少和其中一个匹配

登录—专业IT笔试面试备考平台_牛客网

思路：根据字符串长度分治

题意：给定n个只包含0、1、2的字符串，问有多少个合法五元组，定义合法三元组为三个字符串每位满足全相同或两两不同，定义合法五元组为包含一个以上合法三元组

Meta-set - 洛谷

思路：暴力计算三元组数量，然后求五元组数量

树 子树 无修改

题意：已知每个节点颜色，询问每个节点为根的子树最多的颜色是什么

- E -

思路：树上启发式合并

题意：已知每个点的颜色，m次询问，每次询问u子树内>=k的颜色有几种

Tree and - 洛谷

思路：树上启发式合并

有修改

题意：已知每个节点颜色，每次修改某个子树的所有颜色或询问某个子树最多的颜色是什么

- E -

思路：颜色数量少，线段树维护信息

题意：n个点，m次操作，操作一将所有点变绿，将深度>=x的点变黄，操作二将查询x的子树有多少个黄色节点

[传智杯 #4 初赛] 小卡与落叶 - 洛谷

思路：每次询问的结果跟上次的修改有关，将树按照dfs序重构，转化为与深度还有dfs序的二维数点，数据结构维护黄色点的数量

题意：每个点有一个权值，每次可以选择一个点，将其子树异或上一个c，代价是c*siz[u]，问每个点作为根的时候，使得整个树的权值相同的最小代价

- D -

思路：实现最小代价，需要将所有值都变成根节点的权值，求出1之后，可以通过换根转移到其他点

链

题意：已知每个点的权重，要求每一个条路径的异或和不为0，可以将一个点修改成任何一个值，问最少修改几次

XOR Tree - 洛谷

思路：从根节点做异或前缀和，可以得到关系，然后贪心修改，启发式合并

题意：每条边有一个字母，问子树内有多少条链排序后是回文串

Arpa’s - tree and ’s -kosh paths - 洛谷

思路：启发式合并，维护最大深度

题意：每个点有点权，求出树中所有直链的gcd之和

- 1210C - ( by Menci)

思路：因为gcd最多只有40个，在dfs的过程中暴力传下一个map

题意：求出每条链最大值之和

D - Sum of

思路：按照权重排序，从小到大每次合并连通块

整树

题意：每个点每次可以向父节点移动，除根节点外，若有多个子节点则选择一个移动到父节点，问最少多少次移动

- E -

思路：贪心计算

题意：询问经过每条边的最小生成树

- E -

思路：计算出总的最小生成树，将边也作为点连入树中，进行树剖，线段树维护信息

题意：树染黑白两色，问对于每个点染黑色，且所有黑色点为一个连通块的方案数

- 洛谷

思路：定义f[i]为染i及其子树的方案，定义g[i]为染i及以上的方案，答案就是f[i]*g[i]，g[i]可由换根dp得到，需要预处理前后缀优化

题意：刚开始全是白色，每次将某个点染成黑色，问子树中既有白色也有黑色的点的数量

K题

- 2023 Xian - ( by Menci)

思路：离线求出每个子树全染成黑色的时间，前缀和求解

图 无向图 染色

题意：使得相邻两点的颜色不同且使用颜色最少的方案

- F -

思路：二分图思想，最大度即是最小的颜色数量

题意：黑白染色，使得染完后个颜色连通块数量之和最小

about:blank

思路：每连上一条边会使连通块数量减一，所以答案为点数*2 - 边数，要保证每个颜色染完后没有环才会使结果最小，先染一棵生成树，如果剩下的出现环，那么选择一条边然后重新染

判断

题意：二分图中找四元环

F - Find 4-cycle

思路：将两个图合一，当有边重复时就说明有

题意：n个点，m条带权边，q次询问，问u到v是否存在路径，路径权值按位和的值>=V

思路：枚举满足条件的值，用并查集思想维护

题意：n个点，m条公交路线，从s+0.5的时间从a出发，在t+0.5的时间到b，q次询问，在x时从y出发，问z的时候在哪里

F -

思路：对于每个点找到可以坐的公交，通过倍增优化暴力的做法

计数

题意：d张图，每张有n个点，开始时没有边，每次将第k张图加入u-v的一条边，并询问有多少点在所有图中都连通

[] - 洛谷

思路：将d张图的连通状态通过字符串表示，变为哈希值，通过启发式合并操作

构造

题意：构造图，n个点，边权不大于

，要求每个点对间最短路径长度不同

G题

- 2023 Xian - ( by Menci)

思路：构成一条链，值从大到小输出，结论可证明

题意：n个点，m条边，将所有点分成三组，组内点不直接相连，组间点之间相连，输出方案

- 洛谷

思路：同一组的点连的边相同，随机为点赋值，判断有几组点集

最值

题意：连通的点可以交换，问最大的字典序序列

思路：暴力

题意：n个点，每条边有两个值ai和bi，记生成树的值为

，求最小生成树

King - POJ 2728 - Judge

思路：二分答案，用prim判断值，小于0则该答案可以实现

有向图

题意：判断点u能不能到达点v，对于u&v=v，有一条u指向v的有向边

- 1491D - ( by Menci)

思路：位运算的本质

题意：每条边权值为0或1，从1开始dfs，可以遍历重复点，求形成的序列的逆序对

- C - ( by Menci)

思路：当遍历了重复的点的时候，序列已经，定义dp[i][0/1/2]表示序列0的数量，1的数量以及逆序对的数量，通过dfs求解

题意：计算最小环及数量

2023杭电多校4 - Judge

思路：Floyd过程中计算

题意：计算从1到n两点间的两条路径并的最小值

K题

- 2023 Xian - ( by Menci)

思路：要实现最小，肯定是从1先到x，然后x到y有两条不同的路径，接着从y到n，由此，需要求出1到x，y到n的最短路，以及x到y的最短路和次短路，通过拓扑求解

排列 输出方案

题意：构造

最小的序列，序列满足所有1 ~ n出现两次，其中

表示两个相同数出现的位置差

- D -

思路：根据等式性质，进行奇偶构造

题意：构造满足m个限制的排列，每个限制要求区间[l, r]中逆序对的数量为奇或偶，限制之间要么相离要么包含

登录—专业IT笔试面试备考平台_牛客网

思路：因为有包含关系，所以可以抽象为树的问题，通过递归解决

题意：选择一些位置删除，删除的下标组成的序列等于剩下的序列，输出方案

- C - ( by Menci)

思路：如果是排列，间隔选，否则，必定有几个不能删除。对于第i个位置，将

删除，剩余的是环

题意：给定置换两次后的序列，问原序列

- E -

思路：建图，转化成环问题，结论

计数

题意：要求相邻两位间有大小关系，问总共有多少排列符合条件

- 洛谷

思路：定义dp[i][j]为前i个第i个为j的方案数，通过前缀和优化

判断

题意：若满足

p_i > p_{i + 1}" src=";%201%7D" />，可以交换i-1和i+1位元素，问能否使得排列变成有序

[] of ! - 洛谷

思路：可证，交换当且仅当

。构造序列

，若相邻三位为0，No，否则按照两位相同的将序列划分，对于每个区间，判断最长递减序列是不是大于2，是就No，其它都为Yes

括号序列 修改问题

题意：给定包含4种括号的括号序列，不同类型但相同方向的括号可以相互转化，问最少次数使得括号合法

- C -

思路：单调栈处理

构造

题意：以最少翻转次数使得原序列合法

Bring - 洛谷

思路：0次暴力，1次找首尾第一个不符合的最大值，2次即1到最大值，最大值+1到结尾。

序列 单序列 最值

题意：任意连续m个元素中要至少选择2个，问最小代价

2023杭电多校2 - Judge

思路：dp[i][j]表示选择了i之后，前一个元素是i-j，通过前缀和优化dp

题意：n个物品，已知体积，承重和价值，问选择其中的一些进行摆放的最大价值

Tower - 洛谷

思路：根据贪心排序后01背包

题意：n个人，第i个人的速度为vi，重量为wi，每个人至多可以背起一个人，若自身重量大于背上的人，速度不变，否则减去重量差，问最大速度是多少

- D - ( by Menci)

思路：二分最大速度，大于最大速度的可以背人，小于的只能被背

题意：n个石头，从i跳到j的代价是

，求跳到n的最小代价

Frog 3 - 洛谷

思路：定义dp[i]是跳到第i个石头的最小代价，通过斜率优化求

题意：m个石头，mx，哪一位开始=x的数量

所有值

题意：n种元素，选择k个元素，输出所有方案

- E -

思路：所有值减去最小值，进行dp

单值

题意：找到序列中与当前值按位和为0的值

思路：位运算性质

题意：刚开始总和为0，每次按顺序加上序列的值，要确定一个k使得最后的值最大，只要总和到k就不会低于k

- D -

思路：预处理后缀最大值，求解

题意：q次操作，每次将第i位乘上一个x，每次输出整个序列的gcd9+7的值

GCD of an Array - 洛谷

思路：欧拉筛预处理最小质因数，然后通过求解

题意：将序列赋值n份，选择一个未知的k，如果对k序列操作，选择i、j，两个位置元素减1，i-1、j+2加1，对其他序列操作，选择i、j，两个位置元素减1，i-1、j+1加1，给定操作完的n个序列，求出k和对k序列的操作次数

Array - 洛谷

思路：定义一个序列的值为i*ai，那么可以发现对于k序列以外的操作，值不变

输出方案

题意：输出最长子序列，其最小公倍数小于等于指定值

- D -

思路：指定值较小，暴力枚举所有因数

题意：输出最长子序列，使得两两间互质

思路：分类讨论

题意：构造长为n的序列，使得其所有连续子序列中中位数出现次数最大值最小

#/D

思路：思维构造

题意：构造严格单调递增的序列，要求

思路：构造1，3，5...，使得两数和为偶数，3倍答案为奇数

题意：要求将其中一段区间替换为它们的乘积，输出一种方案使得最后序列总和最大

思路：如果乘积大于1e9，那么除了两头的1其它直接乘，否则枚举区间端点，暴力

题意：若有一段左右相同的区间，将其左半边及左边全部元素删除，从最小的开始删起，若有多个最小，先删最左的那个，输出最后的序列

of - 洛谷

思路：每个数出现次数有限，通过hash判断是否相同，然后按要求删除

题意：输出一个方案

思路：因为和的上限有限，因此暴力枚举，记录和即可

计数

题意：每个数有m种选择，问形成的序列的本质不同的子序列之和

- E -

思路：某个数出现的位置假定后，通过组合数学计算

题意：从n个数中选择k次，要求相邻的两个异或和后二进制下1的个数为3的倍数，输出方案

Xor- - 洛谷

思路：定义dp[i][j]表示第i个数选择

的方案，可以由所有与自己符合条件的i-1转移过来，预处理两数间是否合法，通过矩阵优化dp

题意：由给定序列发散，每次可以*2+1或者*4，问不超过

的数有几个

- 1635D -

思路：首先数量符合斐波那契数列的增长，按照二进制的思想，进行去重然后计算

题意：计算按位或的值为0的子序列数量

思路：高维前缀和，定义g[i]为按位和之后至少为i的子序列的数量

题意：计算gcd为1的子序列的数量

- 洛谷

思路：F(x)表示gcd为x的数量，f(x)表示gcd为x的倍数的数量，可以通过莫比乌斯反演求解

判断

题意：给定序列，刚开始只包含1，每次将一个子序列的和添加进序列中，问能否得到给定序列

- G2 - ( by Menci)

思路：求前缀和判断

题意：要求构造长为n的序列使得序列元素的倒数之和为1

C - Mean

思路：递归构造，每次取最小值拆分

题意：判断是否存在满足限制且不是原序列的子序列

- C - ( by Menci)

思路：预处理每个字符后移的位置，贪心找最大

双序列 相对位置固定

题意：可以交换两序列的元素k次，计算总和差绝对值最小

- D -

思路：交换次数少，暴力枚举，二分答案计算

题意：两个序列长度都为2*n-1，选择其中n个使得每个序列之和都大于总和一半，输出方案

- 23C -

思路：选择数量大于一半，按照其中一个排序后，选择奇或者偶

题意：每个序列选择一个子序列，每次可以让选出的序列某个值+1，记使得两个序列完全相同的操作数是k，计算k的总和

登录—专业IT笔试面试备考平台_牛客网

思路：考虑每个位置的贡献，选择第一个序列第i个，第二个序列第j个，前面的贡献是

，后面同理

题意：选择k个元素，使得

最大

tests - POJ 2976 - Judge

思路：二分答案，记答案为c，那么第i个元素的值变成

，只需要满足最大的k个元素和大于0即可

题意：选择若干个元素，使得

最大，要满足