- 博客(547)
- 收藏
- 关注
RSS订阅
原创 扩展中国剩余定理（EXCRT）【模板】
>Linkluogu P4777>Description求解一元线性同余方程组{x≡b1(moda1)......x≡bn(modan)\left\{\begin{matrix}x\equiv b_1(mod a_1)\\ ......\\ x\equiv b_n(mod a_n)\end{matrix}\right.⎩⎨⎧x≡b1(moda1)......x≡bn(modan)不保证aaa两两互质>解题思路由于模数不保证两两互质，所以我们就不能用中国剩余
2021-07-20 20:35:03
150
原创 博客板子
>Description>Input>Output>Sample Input>Sample Output>解题思路>代码
2019-03-21 16:07:52
244
1原创 [APIO2012]派遣【左偏树】
>Linkluogu P1552>Description>解题思路一个贪心的想法：对于每个节点，选择它的子树中CCC最小的几个（直到它们的和超过了MMM）使得个数最多，可以用堆来维护。在树上操作就需要把子树的堆合并起来了，但是直接合并肯定会超时，这时就要用到左偏树了。左偏树：具有左偏性质的堆有序二叉树（右偏也行），父亲的键值比儿子都小（大）。引入一个新的概念distdistdist，表示某个节点到它子树中的外节点的最近距离，外节点的定义为此节点至少有一个子树为空。左节点的
2022-02-28 09:55:28
142
原创 2-SAT 问题【模板】
>Linklugou P4782>Description>解题思路2-SAT问题如题目所示。注意到每个变量只能为真或假，也就是同一个变量真和假不能同时存在。我们可以根据题目要求满足的条件建图，把每个变量分成真假两个点，按照条件建边，比如 「x1x_1x1为真或 x3x_3x3为假」，就建一条边 (x1real,x3real)(x_1real,x_3real)(x1real,x3real)，表示起点可以推出终点。无解的情况就是同一个变量的真假互相推出了（注意是互相
2022-02-24 21:59:13
279
原创 可持久化并查集【主席树】【启发式合并】
>Linkluogu P3402>Description>解题思路直接暴力空间会爆。我们发现一次合并只会修改一个节点的信息。可持久化结构我们会想到主席树，用线段树换数组获取总体更少的空间，那我们就用主席树来储存某个时刻某个节点的父亲然后询问就直接查询两个点的祖先是否一样即可合并不压缩路径（据说会mle和tle），为了不tle，就用到启发式合并，集合深度小的并到大的（因为查询祖先的时候与集合深度有关）>代码#include <iostream>#
2022-02-24 21:51:26
183
原创 [SDOI2008] 洞穴勘测【LCT】
>Linkluogu P2147>Description要求支持连边、删边、查询两点是否连通三种操作>解题思路LCT裸题>代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 10010using namespace std;struct node{ int son[2], f, l
2022-02-24 20:17:37
68
原创 CF896C Willem, Chtholly and Seniorious【珂朵莉树】
>Linkluogu CF896C>Description>解题思路珂朵莉树，一种奇妙的数据结构使得暴力跑的飞快这种数据结构的重要就是“推平”，题目中的第二种操作。珂朵莉树把每段连续的且数值相同的区间存为一体，放入set（按照位置从小到大排序）。如果操作一个区间 [l,r][l,r][l,r]，就把 l,rl,rl,r 各自存在的区间分裂splitsplitsplit成两个区间，再进行操作。其他就是直接暴力>代码#include <iostream&g
2022-02-24 19:28:51
389
原创 青蛙的约会【同余】【扩欧】
>Linkluogu P1516>Description求关于ttt的同余方程 x+tn≡y+tm(modL)x+tn\equiv y+tm(modL)x+tn≡y+tm(modL)>解题思路把常数和未知数分开：tn−tm≡y−x(modL)tn-tm\equiv y-x(modL)tn−tm≡y−x(modL)然后同余转换成等式：tn−tm+sL=y−xtn-tm+sL=y-xtn−tm+sL=y−xt(n−m)+sL=y−xt(n-m)+sL=y-xt(n−m)+s
2022-02-24 19:20:21
57
原创 涂抹果酱【状压DP】
>Linkybtoj涂抹果酱>DescriptionN≤104,M≤5N\le10^4,M\le5N≤104,M≤5>解题思路MMM的值很小，我们很容易想到状压DP由于每个格子上面可以涂三个颜色，我们可以把每一行的状态用一个三进制数表示，fi,jf_{i,j}fi,j 就表示前 iii 行、第 iii 行填的颜色是 jjj 总共的方案数我为了降低一点时间复杂度，就预处理了合法的状态和每个状态可以匹配的状态们>代码#include <iostream&
2021-12-24 19:47:15
334
原创 约数之和【数论】【扩欧】
>Linkybtoj约数之和>Description求 ABA^BAB 所有约数之和模 990199019901>解题思路可以把 AAA 质因数分解为>代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing namespace std;const LL Mo
2021-12-18 17:25:34
86
原创 [NOIP2012 提高组] 同余方程【扩欧】
>Linkluogu P1082>Description给出 a,ba,ba,b，求 ax≡1(modb)ax≡1(modb)ax≡1(modb) 中 xxx 的最小值>解题思路题意转换，求 ax+by=1ax+by=1ax+by=1 ，xxx 的最小值由这个式子可得，111 是 gcd(a,b)gcd(a,b)gcd(a,b) 的倍数，那么 gcd(a,b)gcd(a,b)gcd(a,b) 就一定为 111所以式子变成 ax+by=gcd(a,b)ax+by=gcd(a
2021-12-18 17:14:23
165
原创 最长距离【树形DP】
>Linkybtoj最长距离>Description给出一棵树，求每个点离其他点的最远距离>解题思路树形DP，处理出 fif_ifi 每个点到它子树中的最远距离，gig_igi 每个点往上走的最远距离>代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 10010#define LL
2021-12-18 17:08:41
178
原创 [UVA10140] Prime Distance / 质数距离【欧拉筛】
>LinkUVA 10140ybtoj质数距离>Description给出若干个询问，询问 [l,r][l,r][l,r] 中相邻两个质数之间最大值和最小值l,r∈[1,231−1],r−l≤107l,r\in [1,2^{31}-1],r-l\le 10^7l,r∈[1,231−1],r−l≤107>解题思路考虑到一个合数拥有一个最小质数，这个质数肯定在 r\sqrt rr 里面，所以我们只要根据 r\sqrt rr 里的质数筛一遍 [l,r][l,r][l,r]
2021-12-15 10:15:04
88
原创 线性筛素数（欧拉筛）【模板】
>Linkluogu P3383>解题思路在埃氏筛的基础上，考虑到一个合数拥有一个它的最小质数，我们只让这个最小质数筛到它一次就行了因为每个数只被筛到一次，所以时间复杂度为 O(n)O(n)O(n)>代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 100000010using namespace
2021-12-15 10:04:40
480
原创 [ZJOI2007]最大半连通子图【tarjan缩点】【拓扑排序+DP】
>Linkluogu P2272ybtoj最大半连通子图>DescriptionN≤105,M≤106N\le10^5,M\le10^6N≤105,M≤106>解题思路强连通子图一定是半连通子图，所以考虑到把这张图进行缩点然后图就变成了一个DAG这时就会发现，题目要求求的最大半连通子图其实就是DAG上的一条链（如果是两条链组合的话，不满足要求）要注意的是，缩点以后建边要注意判重，建重边的话会似的方案数变大！！>代码#include <iostrea
2021-12-04 16:57:25
211
原创 区间修改区间查询【树状数组】
>Linkybtoj区间修改区间查询>解题思路很经典的线段树模板，其实也可以用树状数组做考虑差分，ti=ai−ai−1t_i=a_i-a_{i-1}ti=ai−ai−1，那显然 ai=∑j=1itja_i=\sum_{j=1}^it_jai=∑j=1itj把查询的区间 [l,r][l,r][l,r] 转换成查询 [1,l][1,l][1,l] 和 [1,r][1,r][1,r]suml=a1+a2+...+al=(t1)+(t1+t2)+...+(t1+t2+...+t
2021-11-19 17:25:12
129
原创 最短距离【SPFA】【最小生成树】
>Linkybtoj最短距离>Descriptionn≤105,m≤2∗105n\le 10^5,m\le 2*10^5n≤105,m≤2∗105>解题思路得出一些性质：一个白点到距离它最近的黑点，路上其它点都是白点，而且这个黑点也是这些白点距离最近的黑点跑出来大概就是一个多条链拼在一起，结束点为黑点的图。发现这样很不好处理我们建一个点 TTT，所有黑点与 TTT 连一条边权为 0 的边，这样最终得到的图就是一棵以 TTT 为根的树（所有白点最终到达 TTT）从 TT
2021-11-19 08:26:00
151
原创 斗地主题【暴力】【DFS】
>Linkybtoj斗地主题>Descriptionn≤20n \le 20n≤20>解题思路由于对面只有一张大王，我们最多可以打一张单牌。观察一下，发现形式6、9、10、11是可以忽略的，它们可以根据其它的形式打出来对子、三张牌、炸弹、三带一、四带二我们扫一遍，记录一下三张牌、炸弹的数量，就可以组合好。就差顺子的处理了一开始我是想先把其它处理完再处理顺子，但是这样其它的牌就不能全部组合起来，不然会影响顺子，所以这样做会超时（两个深搜）那就想先处理顺子再处理其它牌，
2021-11-19 08:04:28
83
原创 [SCOI2016]萌萌哒【并查集】【倍增】
>Linkluogu P3295>Descriptionn,m≤105n,m\le10^5n,m≤105>解题思路我感觉这道题的操作跟 这道题 好像一开始的想法：两个区间完全相同，说明两个区间每个对应的数字相同，可以搞一个并查集将这些数字并起来，最后并查集的数量就是可以不同的数的个数，答案用快速幂计算一下但是这样的时间复杂度为 O(n2logn)O(n^2logn)O(n2logn)，显然不行正解就是倍增优化并查集的过程正常的并查集为 faifa_ifai 表示
2021-11-18 21:12:20
147
原创 [CSP-S 2021] 回文【模拟】
>Linkluogu P7915>DescriptionT≤100,n≤105T\le 100, n \le 10^5T≤100,n≤105>解题思路麻掉了TAT 考场被T1卡了就没想后面的题，回来认真看了看没几分钟就想出来了，还是需要调整一下做题的方法，把所有题看了都想一想再开始打TAT（其实还是菜，不然也不会被卡因为一个数只会出现两次，并且最终数列为回文数列，所以如果我们在前面确定了一个数，另一个数的位置也会确定手玩一下就会发现，我们拿两个指针 l,rl,rl,r
2021-11-18 20:53:48
608
原创 [CSP-S 2021] 廊桥分配【set】【二分】
>Linkluogu P7913>Descriptionn≤105n\le 10^5n≤105>解题思路跟考场上的想法一样，不过那时候没学set，不知道怎么实现边删数边二分，然后就打了一个好麻烦的堆然后挂了TT set大法好（虽然说也有set以外的方法根据题意，想到一种方法，先处理出 fif_ifi 和 ffiff_iffi，分别表示国内/国际分到 iii 个廊桥，停靠在廊桥的飞机数量答案就为 max1≤i≤nfi+ffn−1max_{1\le i\le n}f_i
2021-11-18 20:34:37
944
原创 [CF1473E]Minimum Path【分层图最短路】【dijkstra】
>Linkluogu CF1473E>Description给出一张 nnn 个点 mmm 条边的无向图规定最短路的定义为：这条路径上的权值之和，减去最大权值，加上最小权值求 111 到其他所有的点的最短路n,m≤2∗105n,m\le 2*10^5n,m≤2∗105>解题思路这种在一条路上对路径的权值操作的，想到分层图最短路考虑最大权值、最小权值怎么搞，发现题意等同于「这条路径上的权值之和，减去一条边的权值，加上一条边权值」，因为这样求最短路，最优的情况肯定是「减去
2021-11-17 12:19:19
112
原创 [JLOI2011]飞行路线【分层图最短路】【dijkstra】
>Linkluogu P4568>Description给出一张 nnn 个点，mmm 条边的无向图。选择其中的一条路，可以最多减去其中 kkk 条路径的权值求 SSS 到 TTT 的最短路n≤104,m≤5∗104,k≤10n\le 10^4,m\le5*10^4,k\le10n≤104,m≤5∗104,k≤10>解题思路我们把点复制成 k+1k+1k+1 层，其中跨去另一层的次数为 kkk，可以在这之间搞减去的路径的权值把相邻两层之间的边权值赋为 0，每层之间正常建
2021-11-17 12:06:00
254
原创 [HDU]Glad You Came【ST表】
>Linkhdu 6356>Description一个长度为 nnn，初始全部值都为 0 的数组给出 mmm 次操作，每次操作把 [l,r][l,r][l,r] 内所有小于 xxx 的数修改成 xxx求出最终的数组n≤5∗105,m≤5∗107n\le 5*10^5,m\le5*10^7n≤5∗105,m≤5∗107>解题思路看到 mmm 的大小，O(mlogn)O(mlogn)O(mlogn)是会TLE的用ST表，把每次修改的区间 [l,r][l,r][l,r] 分
2021-11-17 11:55:31
766
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人