luogu专题

FHQ Treap模版（luogu P3369）

FHQ Treap模版（自用），带注释 #include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,root,idx;struct node{int l,r;int val,key,size;}tr[N];int getnew(int v){tr[++idx].val=v;//权值tr[idx].key=rand(

LUOGU P2048 [NOI2010] 超级钢琴（贪心+堆）

原题链接：[NOI2010] 超级钢琴题目大意：给出一个长度为 n n n 的数组，且 a i a_{i} ai 可正可负，再给出三个数字 k , L , R k,L,R k,L,R 。定义每个子数组的价值为其所有元素的和，你需要找到 k k k 个连续的子数组（可重叠但不可重复），且满足长度在 [ L , R ] [L,R] [L,R] 内，问你最后这 k k

每日一题~abc 367 F+luogu p10102(随机算法）

随机化的思想：充分条件的计算代价比较大，想找个计算代价小的必要条件，但必要条件可能会出错，然后通过一些手段（比如随机映射）把这个出错的概率降低。(参考园子) 添加链接描述题意：两个数组，元素均为 1~N. q 次查询，判断 a b 数组，这一区间内的元素是否相同。（排列的顺序不重要，主要是元素的种类个数相同） n,q 均在2e5 内。如果暴力，对每次查询，我们只能将这个区间内的所有数扫一

luogu-P10570 [JRKSJ R8] 网球

题目传送门： [JRKSJ R8] 网球 - 洛谷https://www.luogu.com.cn/problem/P10570 解题思路数学问题，暴力这个范围会超时。首先，找出这两个数的最大公因数，将这两个数分别除以最大公因数，则这两个数互质，判断如果有一方<=c，求出他们翻倍的倍数（ceil(c*1.0/min(a,b))），那么将他们分别乘ceil

Smart - Luogu —— 智能的洛谷

文章目录安装 Stylus谷歌Edge 安装 Smart - Luogu使用尾声安装 Stylus link 点击推荐下载，获取 crx 文件谷歌先点击右上角三个点，再点击扩展程序，然后点击管理扩展程序，进入管理扩展界面，把开发者模式选上，把 crx 文件拖入即可 Edge 先点击右上角三个点，再点击扩展，然后点击管理扩展程序，进入管理扩展界面，把开发人员模式选上

Luogu 魔法学院杯-第二弹（萌新的第一法blog）

虽然有点久远还是放一下吧。传送门：https://www.luogu.org/contest/show?tid=754 第一题沉迷游戏，伤感情 #include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;long

(Luogu) p1020导弹拦截

https://www.luogu.org/problemnew/show/P1020 dp的做法，复杂度是 O(n^2)，只能得100分，一个dp求的是最长下降子序列长度，一个dp求的是最少有多少个最长不上升序列， #include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;int f[maxn];int dp[ma

(Luogu) P1032 字串变换

题目链接 https://www.luogu.org/problemnew/show/P1032 AC代码 #include<bits/stdc++.h>using namespace std;string A,B;int N=0,maxlen=0,minlen=1e6+5;//maxlen，minlen为最长长度，最短长度 string a[7],b[7];int res=1e6

(Luogu) p1147 p1029

P1147 连续自然数和 #include<bits/stdc++.h>using namespace std;typedef long long ll;ll sum[1000000];int main(){ll n;cin>>n;for(int i=1;i<=1000000;++i){sum[i]=sum[i-1]+i;}int j=1;for(int i=2;i<=n/2+1;++i

(Luogu) 逆序队个数问题

P1908 逆序对https://www.luogu.org/problemnew/show/P1908 思路归并排序：（即使序列存在相同元素，该算法也适用，且代码不用修改）归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。在合并的过程中（设l<=i<=mid ,mid+1<=j<=h),当a[i]<=a[j]时，并不产生逆序

(Luogu) p1162 p1019

很久没做搜索题了，做了两道 1.p1162填涂颜色 https://www.luogu.org/problemnew/show/P1162 很明显的宽搜题。不过不好从要求的搜索，从边界搜索易解。 #include<bits/stdc++.h>using namespace std;int n;int a[40][40];int x[]={0,0,1,-1};int y[]={1,-

(Luogu) P1993 小K的农场 (差分约束)

传送门解题思路：这是一道差分约束的裸题，我也是第一次接触差分约束，（详细解说戳我）简单来说，就是将不等式与 spfa里的松弛操作联系起来，给予他意义，这样就可以用图的方式来解决他了，观察等式 a-b<=k ,这个式子可以变成 a<=b+k 这个式子是不很像 spfa里的松弛操作if(d[v] < d[u] + w(u,v) ) {d[v] = d[u] + w(u, v);} 我们可

(Luogu) P2922 [USACO08DEC]秘密消息Secret Message (字典树)

传送门解题思路：查询前缀的个数，典型的字典树问题（字典树入门和例题），给你一个前缀，如果单词(都称为单词了)与这个前缀的前部分重合时，res也++，这是需要注意的，例如：前缀10111，那么101也算一个答案；用一个sum数组记录到root这个点为前缀个数，同时flag数组为以root为结尾的单词的个数(flag从标记结尾，变成个数，因为可能有相同的单词数)，查询前缀时，遇到flag不为0，那

(Luogu) P2024 [NOI2001]食物链 (并查集)

传送门解题思路：将并查集分为三个部分分别是同类，猎物，天敌，取x(x属于1~n)举个栗子，与x一块的为x的同类，与x+n为一块的为x的猎物，与x+2*n为一块的为x的天敌。我们只需要同时维护这三个部分，并用来判断假话即可。由于只有A，B，C三种动物，那么A猎物的猎物就是A的天敌这需要注意维护。代码如下： #include<cstdio>#include<iostream>#inclu

(Luogu) P1525 关押罪犯 (并查集)

传送门题目大意：1~n个人，一张关系网，连线权值代表起冲突的影响力，将n个人分成两部分，求最小的冲突事件影响力。如图答案为3512. 解题思路：我们当然不希望权值大的边存在，所以将边从大到小排序，逐个处理，边所对的两方各为敌方，我们应该将一个人和他敌人的敌人并到一个集合，每一次合并都相当于去掉了这条边，从大到小去，当发现了这条边的两段已经在一个集合了，说明在前面合并去掉大边的时候，合并了

(Luogu) P1273 有线电视网 (树型dp+分组背包)

传送门题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户

(Luogu) P2279 [HNOI2003]消防局的设立

传送门解题思路：此题可以树形dp也可以贪心过，看了第一篇题解，非常nice！贪心的策略也很好想，我们从深度最大的开始，他没有孩子孙子，我们自然选择去建立他的祖父，这样可以覆盖到更多的点，我们如何去判断点是否已经被覆盖到了呢，可以开一个o数组 o[i]表示 i到最近的消防站的距离初始化为 0x3f3f3f3f 。代码如下： #include<cstdio>#include<iostream

(Luogu) P1373 小a和uim之大逃离

传送门解题思路：这里dp要开4维，dp[i][j][t][p] 代表在 (i,j) 差值为t，p为角色（0为a，1为uim）选择的方案数。这样我们只要把dp[i][j][0][1]加起来就是所求的方案数了，其实条件是 dp[i][j][a[i][j]%(k+1)][0]=1; 因为每个点都可以为起点。如何更新状态的，我们这样规定 (A-B+k+1)%(k+1)=t%(k+1) (A为小

(Luogu) P3950 部落冲突 (LCT || 树链剖分)

传送门解：LCT解决这个就非常直接了，直接断边连边，检查一下连通性就行了。 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())#define ls ch[x]

LCT动态树-基础模板（luogu P3690）

学习来自 P3690 【模板】Link Cut Tree （动态树）给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。 0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。 1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。 2：后接两个整数(x，y)，代表删除边(x，y)

(Luogu) P1879 [USACO06NOV]玉米田Corn Fields （状压dp）

传送门位运算要掌握好 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())using namespace std;typedef long long ll;

(Luogu) P2495 [SDOI2011]消耗战（虚树+动态规划）

虚树入门题目传送门虚树的主要思想就是对于一棵树，仅仅保留有用的点，重新构建一棵树。 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())using name

luogu 1990 覆盖墙壁 (状压dp)

题目描述 Description 你有一个长为N宽为2的墙壁，给你两种砖头：一个长2宽1，另一个是L型覆盖3个单元的砖头。如下图： 0 0 0 00 砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖N*2的墙壁的覆盖方法。例如一个2*3的墙可以有5种覆盖方法，如下： 012 002 011 001 011 012 112 022 011 001 注意可以使用两种砖头混合起来覆

luogu 1144 最短路计数 (堆优化Dijkstra)

题目描述给出一个N个顶点M条边的无向无权图，顶点编号为1-N。问从顶点1开始，到其他每个点的最短路有几条。输入输出格式输入格式：第一行包含2个正整数N,M为图的顶点数与边数。接下来M行，每行2个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。输出格式：共N行，每行一个非负整数，第ii行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会

luogu 2865 [USACO06NOV]路障Roadblocks (次短路堆优化Dijkstra)

题目描述 Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the wa

luogu 3398 仓鼠找sugar (LCA 在线倍增)

题目描述小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！输入输出格式输入格式：第