浅谈 由于窝太菜了，只好写这篇浅谈来聊以***。 那么我们从最简单的入门开始吧 【一】基础 一个最基础的入门题。 状态：表示到的长度 转移： 答案统计： 因为我们在更新时要找到最大的来更新答案使得答案最优。这样的复杂度是 但是我们可以在的时间内完成，此时可以用树状数组来维护。这里来讲一下用树状数组来维护。此时只要利用简单的区间求最值以及区间加就能完成。 AT2827 LIS例题 随便再来几道线性： 例题一：CF711C 这算是一道比较简单的题 表示表示前i颗树已经分成k组，第i颗树的颜色是j的情况花费的最小费用。 转移也很简单（就是思考这个状态可以由哪些状...

题解- 窝，调了个上午发现被***错误困扰，总算调出来了。 题目意思 题面很小清新：就是求 前置知识：树链剖分+差分 考虑离线。 我们首先可以把题目意思转换为：每次把询问区间里的点到根节点路径上的点权值（包括自己）加一，最后询问到根节点的权值和。我们可以画张图来理解这个转换。 这样就和好理解了。那我们如何来处理这个询问呢。于是我们很自然地会想到差分，即把拆成。那我们怎么实现这个差分呢？我们只需要在点上打上标记（即代码中的），只要即可。区间加等操作我们可以用树链剖分套个线段树来求解（这很套路的）。 时间复杂度：可以过得。 #include &l...

题解- CF722E 题目意思 题目就是让你从走到的道路中有个特殊点，没经过一个特殊点会使分数变为原来一半，问从到的期望得分（对取模） 我们首先把也看成特殊点，但是分数不用除二，然后为了保证每次是向下或向右先对排序即可，接下来就是啦。 这道题目如果把状态设为表示到点经过个特殊点的方案数的话，转移就很麻烦了。所以我们把状态改为表示表示到点至少经过个特殊点的方案数，这样就可以避免一些很麻烦的容斥。 然后我们再设表示从到点的方案数，那么这就变为一个清新的组合数问题，我们考虑一共走了次，最后选次向上，所以 对于的转移我们考虑从转移过来，这里很好的体现状态设计的正确性，我...

题解- P3523 DYN-Dynamite 题目意思 就是在一颗树中选个点使得这个点到关键点的距离最大值最小。 双倍经验 总算看懂题解来重新理解一遍，加深记忆。。 回归正题，因为题目要我们求最大值最小显然会想到二分。 首先我们设几个变量： 表示以为子树最近选择节点的距离 表示以为子树最远还没有选择的关键点距离 表示我们二分出来的答案 对于求还是比较基础的： 但是重点来了！ 要分种情况来讨论： 并且为关键点 如何理解呢？因为最近的点暂时无法满足条件 现在,因为以为子树的所有点都可以被覆盖，所以没有无法覆盖的点故...

题解- P2569 股票交易 题目意思 由于题面过长，不再描述。 戳这里 这道题目想清楚后还是不难的，是一道不错的单调队列练习题。 首先我们要明确状态： 表式到第天拥有个股票的最大收益。 这个状态还是挺显然的，不像某些题目卡状态。 对于转移，要分成多种情况来考虑： 我们就是没有任何积蓄的情况下买（相当于一个初始化），此时转移显然 我们当天选择不买也不买 这个应该比较好理解就是继承原来的最大收益。 已经有资金基础下买股票,此时如何转移呢？ 我们考虑上次买有多少股票，则转移很显然： **如何理解呢？就是上次购买时间...

题解- CF1296E2 题目意思 就是要给每个位置分配一种颜色，使得不同的颜色相邻的字符可以完成交换位置。求一种合理的方案。 思维题。 其实发现几个显然的性质就很容易啦。 对于一段相同或者递增的串只要使得他们相同即可，因为不需要进行交换，可以随意填色。但是值得注意的是，如果一个串长成此时就要保证的颜色要不同于因为要使得交换上来。所以对于这次要填的颜色只要暴力找出比它大的最大值即可，复杂度。 #include <bits/stdc++.h> using namespace std; const int N=2e5+5; int n,m,ans[N],ton...

【艰苦时期 】题解 .在劫难逃 把所有情况枚举出来，取前大即可。 考虑，我们先对每种宝箱做背包。 表示到第个宝箱得到价值为的方案数，则有 于是只要转移即可，为每个宝箱最大值的和。 统计答案就很简单了。 难度： 劫富济贫 枚举全排列即可，计算最大收益即可。 综合算法 由于没有相同的，可以偷取每个金库的钱， 即可 考虑贪心，对于那种先以为第一关键字排序以 为关键字排序在统计肯定是错的。 于是我们要反悔：如果已经积累要偷金库的数量大于 却价值很高。我们要舍去价值小的来替换这个。如果小于直接加入计划即可。 这些都可以用小根堆来维护的。...

题解- CF246C Choosing Balls 题目意思 说人话就是你可以选若干个物品，若这次选择的物品与上次选的相同那么这个的贡献就是否则是。要使得利益最大化。 一开始我以为是什么贪心。后来想想认为还是一个。就是要利用其特殊的一个性质单调性 我们设表示到现在选择的最后一个元素的颜色为的最优解。 显然对于上次颜色相同的只要即可，对于颜色不同的即于是我们只要去求即可。此时我们就要去维护最大值以及次大值。而且因为单调性我们可以做到更新最大值与次大值。 #include <bits/stdc++.h> #define int long long usin...

题解-P6040 「ACOI2020」课后期末考试滑溜滑溜补习班 题目意思 题目较长，不便于描述 这道题目就是考察了一道基础的单调队列优化，以及化柿子的方法。 ，暴力 设表示到的最小花费精力，转移 即可 if(n<=1000) { memset(f,127/3,sizeof(f)); f[1]=a[1]; for ( int i=2;i<=n;i++ ) for ( int j=max(1ll,i-X);j<i;j++ ) f[i]=min(f[i],f[j]+K+(i-j-1)*D+a[...

题解-P6005 Time is Mooney G 题目意思 就是给你一个有向图，你在上面走，没经过一个点可以获得，最后你要减去(走过的边数) 考虑,我们设表示第天到达城市的最大收益。 转移很简单 对于的处理我们只需要反向建有向边即可，答案就是 但是这样的枚举范围无法确定，但是我们发现即可，因为 #include <bits/stdc++.h> using namespace std; const int N=1005; int n,m,C,cnt,head[N]; int M[N],f[N][N],ans; struct nood { int nex...

题解- P4134 连连看 题目大意 就是在区间中找出尽量多的数对,若两种情况下数对数相同使得若干对数对和尽量大。 这道题目难点在于如何转换到熟悉的模型——最小费用最大流。但是题目要我们求数对和尽量大，所以我们只要把边权取反相当于求最小费用，最后答案再去一遍反即可。因为这样我们就可以用简单的方法来解决这道题目了。 于是就很简单： 对于一个成立的数对从到连一条费用为的边流量为的边即可。 从超级源点向连边权为流量为的边，从连边权为流量为的边向超级汇点。 #include <bits/stdc++.h> using namespace std; const int ...

题解- CF650D Zip-line 题目意思 就是给你个序列以及多次操作，每次把换做求一遍（操作之间互不影响） 显然每次修改暴力做是不可行的复杂度至少为。于是我们要思考每次修改会对答案形成怎样的影响。 先对原序列每个点做一遍以他为结束的记为，以他作为起始的记为。易得原序列的就为。 每次对于修改一个值分几种情况来考虑 （思路借鉴 霜雪谦年 的题解），我们记修改过后的为，同理。 对于的情况如果那就更新答案 对于的情况相对复杂一点。我们要先判断此次修改的点是否为原序列的必经之点，判断的方法很简单如果，并且这样的情况有且只有一种。 剩余的就是不变的情况了。于是我们这道题目就做完了。求可以使...

rp++

并查集 #pragma GCC optimize(3) #include <bits/stdc++.h> #define For(i,a,b) for ( int i=(a);i<=(b);i++ ) #define Dow(i,a,b) for ( int i=(a);i>=(b);i-- ) #define FOR(i,t) for ( int i=head[t];i;i=e[i].nex ) #define db double #define mem(x,s) memset(x,s,sizeof(x)) #define cpy(x,s) memcpy(x,s,si...