Luogu3350 ZJOI2016 旅行者 最短路、分治
传送门题意：给出一个$N \times M$的网格图，边有边权，$Q$组询问，每组询问$(x_1,y_1)$到$(x_2,y_2)$的最短路。$N \times M \leq 2 \times 10^4 , Q \leq 10^5$BZOJ原题竟然没有数据范围矩形的多组询问问题考虑分治。考虑计算矩形...
[Luogu P1564] 膜拜
Description神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.某学校有两位神牛，神牛甲和神牛乙。新入学的N 位同学们早已耳闻他们的神话。所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过M。另外，现在N位...
Luogu P4781【模板】拉格朗日插值
洛谷传送门板题…注意一下求多个数的乘积的逆元不要一个个快速幂求逆元,那样很慢,时间复杂度就是.直接先乘起来最后求一次逆元就行了.时间复杂度为这样的拉格朗日插值是预处理,插入,查询的.使用的前提是可以求逆元.CODE#include<cstdio>#include<cstri...
【Luogu2711】小行星（网络流，最大流）
【Luogu2711】小行星（网络流，最大流）题面题目描述星云中有n颗行星，每颗行星的位置是(x,y,z)。每次可以消除一个面（即x,y或z坐标相等）的行星，但是由于时间有限，求消除这些行星的最少次数。输入输出格式输入格式：第1行为小行星个数n，第2行至第n+1行为xi, yi, zi，描述第i个小...
luogu【P1378】油滴拓展 计算几何？
手贱忘记在ans+0.5那里加上括号坑了·好久。 期末考试完回来刷刷水题找下手感。 百度之星的T居然还没到。。。。。。。。 /* ***********************************************Author :BPM136Created Time :2...
Luogu1344 追查坏牛奶 最小割
题目传送门题意：给出$N$个节点$M$条边的有向图，边权为$w$，求其最小割与达到最小割的情况下割掉边数的最小值。$N \leq 32,M \leq 1000,w\leq 2 \times 10^6$$N \leq 32$emmmm求最小割直接套EK或者Dinic模板即可，但是如何求最少边数？考虑将...
【luogu P1144 最短路计数】 题解
题目链接：https://www.luogu.org/problemnew/show/P1144 #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #...
悬线法 || BZOJ3039: 玉蟾宫 || Luogu P4147 玉蟾宫
题面： P4147 玉蟾宫题解：过于板子举报了 #include<cstdio> #include<cstring> #include<iostream> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b)...
LuoGu P1168 中位数
题目描述给出一个长度为 $ N $ 的非负整数序列 $ A_i $ ，对于所有 $ 1 ≤ k ≤ (N + 1) / 2 $ ，输出 $ A_1, A_3, …, A_{2k - 1} $ 的中位数。即前 $ 1,3,5,… $ 个数的中位数。输入输出格式输入格式：第 $ 1 $ 行为一个正整数 ...
[luogu3919]可持久化数组【主席树】
链接：https://www.luogu.org/problemnew/show/P3919分析很明显我们可以用主席树来维护，所谓主席树就是可持久化线段树，能够查询历史版本而且可以实现修改操作，反正就是复制了一遍。其原理就是动态开点复制前驱版本，在复制版本中做我们需要的所有的操作，然后我们需要记录每...
[Luogu 3674]小清新人渣的本愿
Description题库链接给你一个序列 \(A\) ，长度为 \(n\) ，有 \(m\) 次操作，每次询问一个区间是否可以选出两个数它们的差为 \(x\) ；选出两个数它们的和为 \(x\) ；选出两个数它们的乘积为 \(x\) 。\(1\leq n,m,A_i\leq 100000\)Sol...
luogu P2596 [ZJOI2006]书架
传送门感觉要死在\(Splay\)里了 orz这题用\(Splay\)维护这个序列,其中的第\(k\)大点代表这个序列的第\(k\)个数第一个操作,先把那个数所在的点旋到根,然后把整个根的左子树接到右子树中最小的点,记得\(splay\)维护整棵树第二个操作类似,把第一个操作反过来就行第三个本质是两...
[LUOGU] P2886 [USACO07NOV]牛继电器Cow Relays
https://www.luogu.org/problemnew/show/P2886给定无向连通图，求经过k条边，s到t的最短路Floyd形式的矩阵乘法，同样满足结合律，所以可以进行快速幂。离散化大可不必sort+unique，因为我们甚至并不在乎相对大小，只是要一个唯一编号，可以开一个桶记录之所...
luogu1084 [NOIp2012]疫情控制 (二分答案+倍增+dfs序)
先二分出一个时间，把每个军队倍增往上跳到不能再跳然后如果它能到1号点，就记下来它跳到1号点后剩余的时间；如果不能，就让它就地扎根，记一记它覆盖了哪些叶节点（我在这里用了dfs序+差分，其实直接dfs就行..）然后对于那些叶节点没有被覆盖完全的(父亲为1号点的)子树，肯定需要一些已经到1号点的军队来走...
Luogu P1084 [NOIP2012]疫情控制
题目首先我们二分一下答案。然后我们用倍增让军队往上跳，最多先跳到根的子节点。如果当前军队可以到达根节点，那么记录一下它的编号和它到达根节点后还可以走的时间。并且我们记录根节点的叶子节点上到根节点后剩余时间最短的军队。如果不可以到达根节点，那么在它跳到的节点设置检查点。如果一个节点建立了检查点或者它的...
LUOGU P1084 疫情控制(二分+贪心+树上倍增)
传送门解题思路比较神的一道题。首先发现是最小值问题，并且具有单调性，所以要考虑二分答案。其次有一个性质是军队越靠上越优，所以我们要将所有的军队尽量向上提，这一过程我们用倍增实现。发现这时有两种军队，一种是到根之后可以继续移动，另一种不行。那么记录下来那些到根之后可以移动的点和可以继续移动的距离，存到...
【Luogu3041】视频游戏的连击（AC自动机，动态规划）
题面链接题解首先构建出AC自动机然后在AC自动机上面跑DP转移很显然从Trie树的节点跳到他的儿子节点但是要注意一个问题，在计算的时候，每一个节点加入后能够造成的贡献要加上他的子串的贡献至于DP：设f[i][j]表示已经使用了i个字母当前在Trie树的第j个节点上面能够产生的最大贡献很显然，转移到他...
Luogu4512 【模板】多项式除法（多项式求逆+NTT）
http://blog.miskcoo.com/2015/05/polynomial-division 好神啊！通过翻转多项式消除余数的影响，主要原理是商只与次数不小于m的项有关。#include<iostream>#include<cstdio>#include<cm...
luogu P1502 窗口的星星
题目链接P1502 窗口的星星题解扫描线+线段树线段树的每一个节点处理的是左边框放在当前x-1位置时的框内星星的亮度大小按照x坐标进行离散化，得到离散化后每一个坐标x的可影响的范围维护扫描线，扫到可以加某颗星星就把星星加进去，扫到该出来的时候就把星星搞出来,线段树维护一下代码#include<...
luogu P3373 【模板】线段树 2
题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.将某区间每一个数乘上x3.求出某区间每一个数的和输入输出格式输入格式：第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接...