- 博客(321)
- 收藏
- 关注
RSS订阅原创 Codeforces Round 846 (Div. 2) E. Josuke and Complete Graph 详解 数论分块
【代码】Codeforces Round 846 (Div. 2) E. Josuke and Complete Graph 详解 数论分块。
2023-10-15 16:42:37
161
原创 Codeforces Round 892 (Div. 2) - E. Maximum Monogonosity 思维dp 详细解析
好久没有写题了复健一下qwq。
2023-09-29 18:26:08
257
7
原创 前缀和 + ST表 ---- CF 1556 E. Equilibrium(两个序列 + - 操作使得每位相等) 详解
题目连接题目大意：就是给你两个长度为nnn的a,ba,ba,b数组，给你q∈[1,1e5]q\in[1,1e5]q∈[1,1e5]次询问，每次询问一个区间[l,r][l,r][l,r]你对这个区间里面的数可以进行一下操作取出偶数个位置l≤pos1<pos2<....<posz≤r∣[z%2==0]l\leq pos_1<pos_2<....<pos_z\leq r|[z\%2==0]l≤pos1<pos2<....<posz≤r∣[z%
2022-03-04 16:14:39
334
原创 最小割 ---- 2021 ccpc 威海 H city-safety(最大利润 = 最大收益 - 最小花费(最小割))
题目链接题目大意：一棵树，加强第 iii 个点有 wiw_iwi 的花费，而如果距离某个点 ≤p≤ p≤p 的所有点都加强了，则会有 vpv_pvp 的收益，求最大净收益。解题思路：树形dp做法想不明白为啥是对的？？qwq大佬的代码仅供参考，有看懂的聚聚留言qwq#include<bits/stdc++.h>using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(0
2021-11-26 10:41:44
1683
9
原创 分类讨论 ---- 2021 icpc 沈阳 L Linear Fractional Transformation (思维题)
题目链接题目大意给你一个线性变换函数f(z)=az+bcz+df(z)=\frac{az+b}{cz+d}f(z)=cz+daz+b,现在把取值范围扩展到复数域。给你3个等式f(z1)=w1f(z_1)=w_1f(z1)=w1f(z2)=w2f(z_2)=w_2f(z2)=w2f(z3)=w3f(z_3)=w_3f(z3)=w3问你f(z0)f(z_0)f(z0)是多少？解题思路：题目有个很有意思的地方就是它保证了解是唯一的！！现在有3个等式只能确定3个变量，那么对于第
2021-11-25 10:20:42
989
原创 容斥 + 树形dp ---- 2021 icpc 沈阳 L Perfect Matchings
题目链接题目大意：就是给你一个2n2n2n个点的完全图，从这个图里面抽出2n−12n-12n−1条边，这些边形成一颗树，现在问你剩下的图里面点进行完美匹配有多少种方案？解题思路：一开始被完美匹配給限定死了思维。其实我们知道实际上就是对原图进行选边，有的边不能选而已，那么其实我们直接容斥就行了怎么容斥呢？就是对于上面那些树边，我们目的是要求不选，并且两两匹配，如果我们不考虑这个直接全部选的话，那么我们就可能会选到1条树边，2条树边，3条树边依次类推，那么我们就可以直接减就好了我们定义一定选其
2021-11-24 13:04:28
673
8
原创 组合计数 ---- 2020 EC final B. Rectangle Flip 2(枚举+组合计数)
题目大意题目大意：给你一个n×mn\times mn×m的矩阵问你可以截取出多少个不同的矩阵然后每次会有一个点变成无效点动态输出每次剩余可挖的矩阵是多少?解题思路：首先我们可以这么搞就是对于每个点我们维护它上面最近的无效点，然后暴力枚举包含当前即将变成无效点的矩阵有多少个暴力减掉就行了具体实现就是在固定了xxx值之后，我们枚举矩阵左上角和右下角所在的y值就行了直观上面复杂度是O(n4)O(n^4)O(n4)的但是不是每个点最多被访问nnn次，总的复杂度是O(n3)O(n^3)O(n3)
2021-11-22 20:59:20
485
原创 组合计数 ---- 2020 icpc 上海 The Journey of Geor Autumn(思维划分问题计数+预处理优化)
题目链接题目大意：就是你有一个nnn的全排列，现在问你去重排这个排列使得对于给定的kkk,满足对于任意的ai，i>ka_i，i>kai，i>k的都有ai>min(ai−1,...,ai−k)a_i>min(a_{i-1},...,a_{i-k})ai>min(ai−1,...,ai−k)求排列数解题思路：这里很妙的一点就是我们知道对于最小的数肯定是一定要放到[1,k][1,k][1,k]里面去的，然后最小的数肯定会把数列切成两半，前面那一半是随便选，
2021-11-22 20:19:21
218
原创 分类讨论 ---- 2020 icpc 上海 Walker (二分 or 思维分类讨论)
题目链接题目大意：就是两个人在坐标轴上面，有起始的坐标p1,p2p1,p2p1,p2,和速度v1,v2v1,v2v1,v2,问你访问完这长度为nnn的数轴最短时间是多少？解题思路：大佬有直接二分的做法。我就想分类讨论出来qwq首先我们知道肯定两个人最多相遇一次那么我们可以分类讨论两个人开始的时候出发的方向：两个人一个相向而行1.1 两个人相遇之后，是否改变方向？两个人同向而行2.1 同时向左2.1.1 右边的那个人何时调头2.2 同时向右2.2.1 左边的人何时调头两个人
2021-11-22 16:55:15
575
原创 数位dp ---- 2020 icpc 上海 Sum of Log（枚举高位的二进制数位dp）
题目链接题目大意 :解题思路：这里有个很核心的地方就是log2(i+j)\text{log2(i+j)}log2(i+j)本质上就是看看i+j\text{i+j}i+j的二进制高位在哪里？那么上面的式子本质上就可以化简成所以i&j==0i\&j==0i&j==0的情况下那些i+ji+ji+j二进制高位之和但是这么求比较麻烦：我们可以转化一下：就是去枚举高位看看在二进制高位固定死的情况下有多少对i&j==0i\&j==0i&j==0假设是xhx
2021-11-22 16:39:16
103
原创 二分图 ---- 树的二分图性质 2020icpc 济南 J Tree Constructer（构造）
题目链接题目大意：就是给你一颗树，你要对树上点进行赋值，使得相邻两个有边的点的权值或是260−12^{60}-1260−1,任意两个没边的两个点的或不能为260−12^{60}-1260−1n∈[1,100]n\in[1,100]n∈[1,100]解题思路：很明显题目就是要把点分成两个集合，每个集合里面的点两个或的值不为260−12^{60}-1260−1。那么我们可以用二进制里面的最高位进行集合的区分，就是高位是1，低位全是0的一个集合高位是0，低位全是1的一个集合对于高位是0的集合
2021-11-22 16:09:13
131
原创 数位dp ---- 暴力 + 二进制的数位dp 2020济南 L Bit Sequence
题目链接题目大意f(x)=x的二进制中1的个数f(x)=x的二进制中1的个数f(x)=x的二进制中1的个数给你一个数组[a1,a2,a3...,am]m∈[1,100][a_1,a_2,a_3...,a_m]m\in[1,100][a1,a2,a3...,am]m∈[1,100]问你有多少x∈[1,1e18]x\in[1,1e18]x∈[1,1e18]满足f(x+i)%2=aif(x+i)\%2=a_if(x+i)%2=ai解题思路：首先我们发现m∈[1,100]m\in[1,10
2021-11-22 15:25:49
266
原创 树形dp --- 2020 icpc 南京 M Monster Hunter
题目链接题目大意：解题思路：首先我们分析一下每个点状态是怎么？1.1: 对于这个点我们删除的代价我们要看一下它儿子有多少个没被删除（指没用）因为父亲节点没删这个点呀删除不了1.2: 那么这个点下面用了多少次魔法。1.3: 这个点是否使用用魔法去删除那么dpdpdp方程就很显然了dp[i][j][0/1]dp[i][j][0/1]dp[i][j][0/1]表示第i个点为子树里面用了j次魔法并且第i个点是否用魔法去删除并且删除完整个子树的最小代价是多少？那么dpdpdp转移方程就有了
2021-11-22 12:33:41
279
原创 容斥 + 爆搜打表 ---- 2020年南京icpc H.Harmonious Rectangle
题目链接题目大意：就是给你一个二维平面{(x,y)∣1≤x≤n,1≤y≤m}\{(x,y)|1\leq x\leq n,1\leq y \leq m\}{(x,y)∣1≤x≤n,1≤y≤m},你现在有3种颜色，你可以给写平面的点涂上颜色，问你至少存在4个点(x1,y1),(x2,y2),(x1,y2),(x2,y1)(x1,y1),(x2,y2),(x1,y2),(x2,y1)(x1,y1),(x2,y2),(x1,y2),(x2,y1)使得color(x1,y1)=color(x1,y2)&
2021-11-12 16:31:24
636
原创 并查集 ---- 扩展域并查集判二分图 + 循环模拟字典树 The 2020 ICPC Asia Macau Regional Contest C. Club Assignment (详解)
题目链接题目大意：有n个数，现在要把他们拆分成两个集合，假设S为集合，有如下定义：f(S)={min(x⊕y)∣x,y∈S,and x!=y}f(S)=\{min(x\oplus y)|x,y\in S,and\;x!=y\}f(S)={min(x⊕y)∣x,y∈S,andx!=y}将n个数拆分为两个集合A,B，要求最大化min(f(A),f(B))m i n ( f ( A ) , f ( B ) )min(f(A),f(B)),并输出划分集合的方案，如果有多种，则输出任意一个.解题思
2021-11-03 11:15:38
3343
原创 树上启发式合并问题 ---- 2019icpc南昌 K. Tree （树上启发式合并 + 动态开点线段树)
题目链接题目大意：就是给你一颗树，每个点有个权值viv_ivi，问你有多少对(x,y)(x,y)(x,y)满足：xxx不是yyy的祖先yyy也不是xxx的祖先xxx和yyy的距离不超过kkkxxx和yyy最近公共祖先：zzz,满足vx+vy=2vzv_x+v_y=2v_zvx+vy=2vz解题思路：首先我一开始以为是点分治，但是发现点分之后公共祖先维护不了！！那么我们树的结构肯定变不了，那么我们可以固定公共祖先zzz,那么就是在zzz这个子树里面，找到两个子树里面点x,yx
2021-10-30 17:00:17
118
原创 后缀数组 + Hash + 二分 or Hash + 二分 + 双指针 求 LCP ---- 2017icpc 青岛 J Suffix (假题！！)
题目链接题目大意：就是给你n个串每个串取一个后缀,要求把串拼起来要求字典序最小！！sum_length_of_n≤5e5sum\_length\_of\_n\leq 5e5sum_length_of_n≤5e5MY Slove :首先我们知道对于最后一个串肯定是取最小后缀的那么我们可以把最后一个串的结果接到倒数第二个串上面在求一次最小后缀就可以得倒数第二个串的结果，依次以此类推就好了。但是这样我们算算复杂度：假如我们每次都把答案拼到下一个串上面求个后缀数组那么我们假设最坏就是a
2021-10-28 10:46:43
164
原创 最小费用最大流 ---- 2017icpc青岛现场赛 K Our Journey of Xian Ends (拆点控制原图点度 + 中间必经过的点设置成源点 + 起点设成汇点)
题目链接题目大意：题目贼恶心难读就是你出发地是"Xian"西安，现在你要出发到上海然后再去青岛，然后回到上海飞机场限制：就是每个机场只能降落和起飞一次上海的限制：上海有两个机场，叫虹桥和浦东机场，你要是要是降落在浦东机场只能到虹桥出发去青岛并且你最后还要回到虹桥再回到浦东！！如果是降落在虹桥就没有限制，你最后回到浦东机场就好了给你所有的航线信息：问你最小花费是多少？解题思路：首先要最小花费那么肯定要最小费用流对于每个飞机场只能起飞降落一次我们可以进行拆点进行限制：每个点uuu拆成u
2021-10-26 20:12:03
195
原创 树形dp ---- gym101655 D - Delta Quadrant 树上连通块思维换根 + 树形dp
题目链接题目大意：给你一颗NNN个节点的树，树上每条边有边权就是遍历的时间，你可以从任意节点出发遍历N−kN-kN−k个点并且回到出发点，问你最短的时间是多少？k∈[0,min(N,20)],N∈[1,1e4]k\in[0,min(N,20)],N\in[1,1e4]k∈[0,min(N,20)],N∈[1,1e4]解题思路：思维误区：一开始我对于这个任意节点出发以为是要换根，但是子父之间的关系不好找！！，而且我定义的状态方程是dp[i][j]dp[i][j]dp[i][j]从iii这个子树里
2021-10-24 13:26:02
136
原创 树形dp ---- gym101667 A(贪心 + 树形dp + 两个dp方程组维护)
题目链接题目大意：就是一棵5e35e35e3的树，可以选择一些点，放上基站，如果uuu上的基站价值为ddd，那么距离uuu小于等于ddd的点都会被覆盖，问使得整棵树被覆盖需要的最小价值。解题思路：一开始我是这么想树形dp的 dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值但是这里有两个问题就是如果
2021-10-22 16:22:19
94
原创 有源汇上下界最小费用可行流 ---- P4553 80人环游世界（拆点 + 有源汇上下界最小费用可行流）
题目链接题目大意：解题思路：又是一道裸题 。首先它要求第iii个点只经过ViViVi那么我们就拆点ai,ai+na_i,a_{i+n}ai,ai+n一个点为入点，一个为出点这条边的流量范围是[Vi,Vi],费用为0[V_i,V_i],费用为0[Vi,Vi],费用为0。对于两个点之间的航道我们假设是ai→aja_i\rightarrow a_jai→aj那么就是ai+n→aja_{i+n}\rightarrow a_jai+n→aj,流量为[0,INF][0,INF][0,I
2021-10-20 15:12:11
134
原创 有源汇上下界最小费用可行流 ---- P4043 [AHOI2014/JSOI2014]支线剧情（模板）
题目链接题目大意：解题思路：有源汇上下界最小费用可行流模板题目来着先建出一个有源汇上下界可行流的图，然后注意建图的时候要把每条边的下界的费用提前加到ans里面然后再对图跑费用流，就是补齐费用AC code#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 4010;const ll INF = 0x3f3f3f3f3f3f3f3f;int n, m
2021-10-20 13:01:45
186
原创 树上问题 ---- E. Fib-tree(斐波那契数的性质 + 暴力模拟 + 认真计算复杂度)
题目大意：一个树是FIBFIBFIB树得是节点个数为斐波那契数，且(注意这个且)！！此外满足下面条件一个：1.只有一个点2.可以切一条边使得分出的两个子树都是FIBFIBFIB树。给你一棵树，问是否是FIBFIBFIB树注意这是个递归定义来着解题思路：首先我们知道n=fib[i]=fib[i−1]+fib[i−2]n=fib[i]=fib[i-1]+fib[i-2]n=fib[i]=fib[i−1]+fib[i−2]那么fib[i]fib[i]fib[i]只能划分成fib[i−1]和fi
2021-10-18 20:19:47
169
原创 树形dp ---- C. Karen and Supermarket(子树选择类型dp + 注意dp更新顺序)
题目链接题目大意：解题思路：如果你要打折某个商品那么它到1的路径上所以点都要买并且打折有点像树上背包了，我们对于最大购买量做dp不是很好dp,但是我们可以用背包的思想就是：我们可以求出在买xxx个物品的情况下需要的最小花费？那么我们dp方程就很好想了dp[i][j][1/0]:第i个子树里面买了j个商品并且第i个商品是否打折了需要的最小花费dp[i][j][1/0]:第i个子树里面买了j个商品并且第i个商品是否打折了需要的最小花费dp[i][j][1/0]:第i个子树里面买了j个商品并且第i
2021-10-18 19:33:42
101
原创 图论 ---- C. Graph Transpositions（数据分阶段分层图最短路(二维) + 贪心）
题目链接题目大意：对于给你一个有向图，你有两次操作你单前在uuu点从u→vu\rightarrow vu→v花费1s1s1s你可以把整个图的边都反向！！就是u→vu\rightarrow vu→v变成u←vu\leftarrow vu←v的你第KKK次操作花费的代价是2K−1s2^{K-1}s2K−1s问你从1号点到n号点最短时间是多少？解题思路：首先我们知道如果存在一条路径的话那么最少时间是n−1(s)n-1(s)n−1(s)那么218≤200000<2192^{18}\l
2021-10-16 15:31:32
147
原创 图论 ---- F. Useful Edges(不等式移项优化预处理 + 路径和简单路径的区别 + 最短路)
题目链接题目大意：给出由 nnn 个点构成的无向图，再给出 qqq 个三元对 (u,v,l)( u , v , l )(u,v,l)，现在问有多少条边 (i,j)( i , j )(i,j) 可以和至少一个三元对匹配，可以匹配的条件是：从点 uuu 到点 vvv 且包含边 (i,j)( i , j )(i,j) 的最短路的长度需要小于等于 lll解题思路：注意这里path指的是路径，你可以重复经过某些点对于一条边我们看看它是否成立我们是这样看的就是设dist[i][j]dist[i][j
2021-10-15 19:41:40
137
原创 图论 ---- E. Bear and Forgotten Tree 2(判补图的联通性技巧 图遍历的优化 条件拆分)
题目大意题目大意：给你nnn个点，mmm对关系表示(ai,bi)(a_i,b_i)(ai,bi)之间是没有边的问你能否构建出一颗树满足111号点的度数为kkk?解题思路：如果没有后面的条件就是判断这个图的补图的连通性？但是怎么判呢？这里就是我们直接对点进行bfs每个点只访问一次。因为直接用边转移的话那么复杂度是O(n+m)m∈[0,n2],n∈[1,1e5]O(n+m)m\in[0,n^2],n\in[1,1e5]O(n+m)m∈[0,n2],n∈[1,1e5]不可以结束我们可以直接去枚
2021-10-15 19:25:49
116
原创 树上动态插点 ---- F. Imbalance Value of a Tree（树上动态插点 + 并查集）
题目链接题目大意：定义I(x,y)为x到y路径上最大值和最小值之差I(x,y)为x到y路径上最大值和最小值之差I(x,y)为x到y路径上最大值和最小值之差现在叫你求∑i=1n∑j=inI(x,y)\sum_{i=1}^{n}\sum_{j=i}^nI(x,y)i=1∑nj=i∑nI(x,y)解题思路：首先我们可以这么看对于一个点我们可以去看看假设这个点是路径上面的最大值，有多少条路径？然后我们再去看看这个点是多少路径上的最小值贡献相减就可以了！！但是怎么求？我们可以把点按照权值进行升
2021-10-13 16:15:48
101
原创 根号均摊 ---- E. Xenia and Tree(树形dp + 暴力根号均摊)
题目大意题目大意：你有一颗树：树开始时候1号点是红色的现在就是你有两次操作：1 u 把u点涂成红色2 u 询问离u点最近红点在哪里？数据范围是n,m∈[1,1e5]n,m\in[1,1e5]n,m∈[1,1e5]时间限制是5s5s5s如果直接查询我们是可以直接树形dpO(n)O(n)O(n)去查询，跟新是O(1)O(1)O(1)如果直接去维护每个点的答案是跟新就是O(n)O(n)O(n)查询是O(1)O(1)O(1)的？那么我们可以考虑去均摊两个复杂度O(nm)O(n\sqrt m)
2021-10-13 15:38:38
120
原创 线段树分治 ---- F. Extending Set of Points(线段树分治 + 可撤销并查集)
题目链接题目大意：你有个点集合SSS，每次往集合里面加点或者删点(如果要加的点出现过),如果(x1,y1),(x2,y1),(x1,y2),(x2,y2)(x1,y1),(x2,y1),(x1,y2),(x2,y2)(x1,y1),(x2,y1),(x1,y2),(x2,y2)只要出现其中3个第4个就会出现？问你最终这个点集会变成多少个点在里面解题思路：很明显的一点4个点连线会构成一个环，我们对这个点我们可以直接用并查集去维护行和列拆开例如(x1,y1)(x1,y1)(x1,y1)我们直接把
2021-10-13 14:55:35
90
原创 树套树 ----- P1975 [国家集训队]排队(树状数组套权值线段树求动态逆序对)
解题思路：首先我们知道交换两个数a[l]和a[r]a[l]和a[r]a[l]和a[r]影响到的区间是[l+1,r−1][l+1,r-1][l+1,r−1]对于a[l]a[l]a[l],我们要减去[l+1,r−1][l+1,r-1][l+1,r−1]里面比a[l]a[l]a[l]大的，加上比a[l]a[l]a[l]小的。对于a[r]a[r]a[r]同理反过来就好了。如果a[l]>a[r]:ans++a[l]>a[r]:ans++a[l]>a[r]:ans++如果a[r]>a
2021-10-09 10:51:29
130
原创 图论 ---- C. Nastya and Unexpected Guest（图上最短路dp + 01bfs）
题目链接题目大意：给你一条长度为 n 的马路（可以将马路视为一个数轴），你要从 0 位置开始到达 n 位置，你每秒走 1 个长度单位。在马路上有 m 个安全岛，它们的位置已给定。该马路的绿灯亮 g 秒，红灯亮 r 秒，第 0 秒时信号灯刚由红灯变为绿灯。绿灯亮时，你必须一直向前走，到达一个安全岛时，你可以选择调头。红灯亮时，你必须一直停在某个安全岛处，直到绿灯再次亮起。求你最快需要多少秒能从马路的 0 位置到达 n 位置（无法到达则输出 -1）解题思路：本质上就是一个最短路，但是这里面有个限制
2021-10-09 10:24:06
151
原创 图论 ---- E. Minimum Path（分层图最短路 用分层图对边权操作进行选择）
题目链接题目大意：两点间最短路的定义变成:所有的边之和−max+min所有的边之和-max+min所有的边之和−max+min解题思路：这里很明显就是变成了最短路的时时候就是把路径上边权最小值乘2，然后把最大值去掉？相当于免费？是不是很像分层图？就是你有两次机会：1.你可以把一条路径上的边权变成0。2.是把边权翻倍为什么跑分层图最短路就是答案呢？因为根据最短路的性质肯定是去大边，翻倍小边我们一共有4种状态:1.两个机会都没用2.用了第一个条件，第二个没用3.用了第二个条件，第一
2021-10-08 20:55:40
124
原创 图论 ---- F. The Shortest Statement (最短路的性质 + 任意两点间最短路 + 图转树)
题目链接题目大意：给你一个nnn个点mmm条边的无向图，就是动态询问任意两点间的最短路n,m∈[1,1e5],m−n≤20n,m\in[1,1e5],m-n\leq20n,m∈[1,1e5],m−n≤20解题思路：这里有个很重要的点就是m−n≤20m-n\leq20m−n≤20这让我们很容易联系到先求一个树。那么最多会多出212121条边但是这又有什么用呢？我们知道在树上面两点间的最短路径就是唯一的。那么如果不是那么一定是进过了若干条非树边。我们知道对两点间最短路径上面的点到这两个点
2021-10-08 20:09:28
84
原创 贪心 ---- 贪心 + STL维护 + 划分集合 L. Neo-Robin Hood（好题）
题目链接题目大意：题意：你是劫富济自己的罗宾汉，有n个富人，第i个人有m[i]元财富，收买他需要p[i]元。对每个人你都可以选择1.抢他，你获得m[i]元，2.不对他进行操作，3.花p[i]元收买他，他为你开脱你的一件抢劫罪行。你有一个奇怪的目标：抢的人数越多越好，但是你的每一个罪行都必须被开脱。翻译一下就是抢k个人，收买另外k个人，抢来的钱要足够收买的花费，最大化的k。解题思路：首先我们发现如果j<kj<kj<k并且kkk是合法的话那么jjj肯定是可以的那么这样子就答案
2021-10-06 23:51:47
279
原创 线段树 ---- H. AND = OR (或和与的性质之1的个数 + 线段树)
题目链接题目大意：给你一个序列{a}\{a\}{a},每次询问一个区间[l,r][l,r][l,r]问你这个区间里面的数是否可以分成两部分使得一部分的AND=AND=AND=另一部分的OROROR解题思路：这个题思路很妙：首先我们知道对于&\&&操作数越多只会越&\&&越小，而∣|∣就是相反的那么我们可以假设这个区间里面的数可以分成两部分，那么假设最后的答案是ansansans假设ansansans中有xxx个1,那么对于区间里面数包含的
2021-10-06 20:51:17
335
原创 树形dp ---- 2018年杭电多校第二场 H travel
题目大意：就是给你一个带点权的树，找到3条独立互不相交的路径使得权值和最大解题思路：很经典的树形dp我们设dp[root][j][k]dp[root][j][k]dp[root][j][k]表示在rootrootroot这个子树里面选出了jjj条路径，其中我们有kkk条路径经过了rootrootroot。j∈[0,4],k∈[0,2]j\in[0,4],k\in[0,2]j∈[0,4],k∈[0,2]看代码注释#include <bits/stdc++.h>#define mi
2021-10-04 21:40:15
69
原创 Splay ---- 2018牛客多校第三场 区间翻转搞区间位移 或者 rope可持久化块状链表
题目链接题目大意：就是每次把牌堆中若干个连续的牌放到堆顶，问你最后牌的序列。解题思路：Splay 区间翻转的模板题：对于一个区间[1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8]你要把[3,4,5][3,4,5][3,4,5]拿到前面去我们可以这么搞先把[1−5][1-5][1−5]翻转·一下[5,4,3,2,1,6,7,8][5,4,3,2,1,6,7,8][5,4,3,2,1,6,7,8]然后我们发现只要把[5,4,3][5,4
2021-10-04 10:53:02
123
原创 线段树分治 ---- CF1217F - Forced Online Queries Problem（假离线 可撤销并查集 + 线段树分治）详解
题目链接题目大意解题思路：我一开始想到可以用可撤销并查集去维护这种删边加边的操作，但是有个缺点是每次撤销都有把后面的边全部撤销复度是O(n2)O(n^2)O(n2)首先我们考虑这种动态加边删边的问题，如果是离线的话，那就是线段树分治+可撤销的并查集的模板题但是这是强制在线，但是这是虚伪的强制在线就是，每次个操作最多有两种的结果。lst={0,1}lst=\{0,1\}lst={0,1}， 最多也就2×m2\times m2×m个操作就是我们有条有若干段存在的时间，我们插进线段树里面，用
2021-09-29 20:55:27
183
原创 线段树 ---- CF452F. Permutation（线段树维护序列Hash）
题目链接题目大意：就是给你一个全排列，问你是否存在一个c=a+b2c=\frac{a+b}{2}c=2a+b满足ccc的位置在a,ba,ba,b之间解题思路：首先我们先按顺序遍历，我们假设遍历到的数是中间那个数就是ccc,那么它要存在的答案的话就是存在一个kkk,使得c−k在之前出现过，c+k还没出现，或者反过来c-k在之前出现过，c+k还没出现，或者反过来c−k在之前出现过，c+k还没出现，或者反过来我们设bib_ibi表示iii这个数是否出现过？那么如果ccc这个数没有答案呢？就
2021-09-24 20:16:03
109
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人