原题链接：https://www.luogu.com.cn/problem/P2161题意解读：本题前面形式化描述已经足够清晰。解题思路：要判断线段之间是否有冲突（包含或者交叉），可以借助set，参考：https://www.cnblogs.com/jcwy/p/18447333只不过这里要统计冲突的数量，也就是允许相等的元素重复存在，可以借助multiset

原题链接：https://www.luogu.com.cn/problem/P5677题意解读：所谓好的配对，通过分析公式∣ax−ay∣≤∣ax−ai∣(i≠x)，可以得知就是一个ax与其差的绝对值最小的形成的配对，在数轴上就是距离ax最近的点ay，配对是下标（x,y），给定若干个区间[l,r]，每个区间的配对数*区间编号的累加。解题思路：

原题链接：https://www.luogu.com.cn/problem/P1908题意解读：求逆序对，前面介绍过归并排序的做法，参考：https://www.cnblogs.com/jcwy/p/184077，这里介绍树状数组的做法。解题思路：设数组a[n]里的整数只包括1~n，显然对于此题，可以通过离散化得到这样的数组。要计算逆序对，就是要计算对于

以此题单为例，首先我们在浏览器中打开，F12切换到Console，输入document.querySelectorAll(".titlea")，然后复制返回的所有内容，粘贴到VSCode里，内容大致如下：NodeList(15)[a.title.color-default,a.title.color-default,a.title.color-default,a.title.color-default,a.title

原题链接：https://www.luogu.com.cn/problem/P3368题意解读：树状数组应用-区间修改，单点求值解题思路：设原数组为s[N]，其差分数组为a[N]操作一：区间修改要对s[x]~s[y]每个数增加k，相当于对a[x]加k，对a[y+1]减k，O(n)的操作变成了O(1)的操作,利用树状数组tr[N]的add(x,k),add(y+

原题链接：https://www.luogu.com.cn/problem/P3374题意解读：树状数组模版：单点修改，区间求值。解题思路：树状数组-BinaryIndexTree可以动态维护一组数，可以O(logn)的修改一个数，也可以O(logn)的计算一段区间的和。思考一下朴素做法：如何修改一个数，计算区间和？如果是常规数组，修改操作

洛谷题单算法2-2常见优化技巧单调栈单调栈最经典的应用，就是在一个数列里寻找距离元素最近的比其大/小的元素位置。模板题，寻找每个元素右边第一个比它大的元素下标。stack<int>s;for(inti=n;i>=1;i--){while(s.size()&&a[s.top()]<=a[i])s.pop();f[i]=s.

原题链接：https://www.luogu.com.cn/problem/P1878题意解读：n个男女排列一行，每人舞蹈技术是ai，每次找到相邻男女舞蹈技术差值绝对值最小的一对出列，输出每对出列的人员编号。解题思路：设初始有8人编号为：12345678将12,23,34,45,56,67,78中是男女的配对编号以及a

P1428小鱼比可爱题目描述人比人，气死人；鱼比鱼，难死鱼。小鱼最近参加了一个“比可爱”比赛，比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排，头都朝向左边，然后每只鱼会得到一个整数数值，表示这只鱼的可爱程度，很显然整数越大，表示这只鱼越可爱，而且任意两只鱼的可爱程度可能一样

原题链接：https://www.luogu.com.cn/problem/P2085题意解读：有n个函数，函数中x取值>=1，计算所有函数能得到的值中最小的m个。解题思路：函数中x取值是>=1的整数，因此每个函数的值是f(1),f(2),f(3)....，是一个递增序列，题目本质上是要从n个递增序列中找到前m个最小的数。首先，对所有函数

【入门1】顺序结构Hello,World!#include<stdio.h>intmain(){printf("Hello,World!");return0;}输出字符菱形#include<stdio.h>intmain(){printf("*\n");printf("***\n");printf("*****\n&q

原题链接：https://www.luogu.com.cn/problem/P1168题意解读：中位数就是位于中间的数，前1个数的中位数是第1个，前3个数的中位数是第2个，前5个数的中位数的第3个...以此类推。所以，此题本质上就是动态维护一组数，每1/3/5...等奇数个取第k小的数，取一次后k++。解题思路：要动态维护数据，且每

原题链接：https://www.luogu.com.cn/problem/P2827题意解读：初始n个数，每次取最大值x，根据u/v分成两部分：x*u/v，x-x*u/v，然后其余数都增加q，整个过程重复m次。输出有两类数据：第t，2t，3t...次取出的最大值；最后剩余的数第t，2t，3t...个，从大到小输出。解题思路：直观上，通过模拟法可以实

原题链接：https://www.luogu.com.cn/problem/P1801题意解读：动态维护一组序列，并随时可以求第k小的值，每次求第k小的顺序是递增的，比如第一次取第1小，然后是第2小，以此类推。解题思路：对于求第k小的问题，已经介绍过几种方案：1、快选算法，每次查询时间复杂度logn，传送门：https://www.cnblogs

原题链接：https://www.luogu.com.cn/problem/P3378题意解读：实现二叉堆。解题思路：二叉堆本质上一棵完全二叉树，根节点称为堆顶，根据特性不同分为有两种：大根堆：所有父节点的值大于子节点，根节点最大小根堆：所有父节点的值小于子节点，根节点最小主要作用：动态维护序列，并快速找到最大/最

原题链接：https://www.luogu.com.cn/problem/P6824题意解读：已知整数序列a[i]，i在1~n，有整数k，求一个整数x，要求a[i]^x<=k，使得符合要求的a[i]数量最多，求这个数量。解题思路：1、确定x的范围由于a[i]^x<=k，因此，x的有效二进制位不可能超过a[i]，而a的取值范围<=1000000，因此x差不多

原题链接：https://www.luogu.com.cn/problem/P3369题意解读：平衡树的基本操作，模版题。解题思路：1、二叉搜索树-BST二叉搜索树满足这样的性质：每一个节点的权值大于它的左儿子，小于它的右儿子。对BST进行中序遍历，将得到一个从小到大的有序序列，因此BST是为了维护一个有序序列的动态

原题链接：https://www.luogu.com.cn/problem/P4735题意解读：已知长度为n的数组a[]，要在l~r范围找到一个p，使得a[p]^a[p+1]^...^a[n]^x最大，求这个最大的异或值。解题思路：1、利用前缀和将问题转化设s[]是a[]的前缀异或数组，要计算a中一段范围l~r的异或，可以借助于s由于s[r]=a[0]^a[

原题链接：https://www.luogu.com.cn/problem/P2922题意解读：已知M个01串，给出N个01串，对于N个串的每一个，求在M个串中有多少与其有公共前缀，且前缀长度是两个串中较小者。解题思路：用Trie树存储M个01串，用cnt1[]记录某个节点结束的01串个数，cnt2[]记录经过某个节点的01串的数量对于N个0

原题链接：https://www.luogu.com.cn/problem/P2375题意解读：计算字符串所有子串的不重叠相同前后缀数量。解题思路：1、KMP+暴力通过Next数组，可以计算所有子串相同前后缀的数量然后枚举Next数组，通过回跳Next[j]、Next[Next[j]-1]、Next[Next[Next[j]-1]-1]......来统计长度小于

原题链接：https://www.luogu.com.cn/problem/P3435题意解读：定义字符串a是b的周期，当a是b的真前缀，且b是aa的前缀。给定字符串s，求s每一个前缀的最大周期长度之和。解题思路：针对字符串babababa进行样例模拟：前缀子串  最大周期  周期长度b空0ba空0babba2

原题链接：https://www.luogu.com.cn/problem/CF25E https://codeforces.com/contest/25/problem/E题意解读：给定a，b，c三个字符串，求包含a、b、c的最短字符串长度。解题思路：要得到包含a、b、c的字符串，可以通过a、b、c连接形成，而要使得连接后的字符串最短，可以尽可能的利用重叠部分

原题链接：https://www.luogu.com.cn/problem/P1470题意解读：求s最长前缀长度，使得可以拆解成p集合中的字符串解题思路：动态规划：设s字符串下标从1开始，p集合用set<string>保存所有的元素状态表示：设f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素状态计算：对于j=i-1开始往后倒

原题链接：https://www.luogu.com.cn/problem/P5283题意解读：n个整数，每次从从取l~r的数进行异或得到美味值，一共取k次，并计算这k个美味值之和的最大值。解题思路：1、如何O(1)的计算l~r数的异或，得到美味值可以借助前缀和思想，a[i]为第i个数，s[i]表示a[1]~a[i]每个数的异或值，要计算l~r的