感受被题解惊呆了，真没想到可以转化为DFS序，然后在链上思考这个问题！学到了 思路首先我们要明确染色策略，按照DFS序染***r>当我们染色到u点时，假如我们已经使用了k种颜色。按照DFS序染色的规则，我们可以发现，u点的子树并没有被染色，相反u的的父亲，父亲的父亲,...，都一定被染色了，至于它的兄弟也可能被染色。所以，我们考虑给u染色时，如果u染的颜色来自那k种，那么染的颜色一定与父亲相同，否则，肯定可以从u的非子树部分找到一个点，其颜色与u相同，这样的话，根据树的性质，u必须经过父亲才能到达那个点，这样就会产生冲突。如果染非k的颜色话，可以随便染，一定不会冲突。因此，DP转移式子...

感受整数分块真香！ 思路一般询问区间[L, R]的问题要么直接处理，要么分成[1, R]-[1, L - 1]处理。直接考虑第二种处理方法，怎么求[1,x]的答案呢？ 比如我们想求解约数的最高位的那个数码为4的情形 4 [40, 49] [400, 499]...有什么用呢？如果一个约数为q,那么区间[1, n]中存在约数为q的有【n/q】（下取整）是不是想到了，这不是就是傻×分块吗？ 复杂度分析枚举数码O(9) 枚举数码对应的区间 对于每一个区间，进行整数分块求解总复杂度最坏为O（9 * 10 * sqrt(n)）= O（1e6） #include <bits/std...

感受题目出得很好，但是我觉得题解讲得不是太好，也有可能是我太菜了。弄懂这题，我看的是cf官方题解E题https://codeforces.ml/blog/entry/72212思路我自己也YY一下，其实这是一道考虑边权对答案的贡献题。我们考虑某一个树边，树边W上有两个端点，记为u和v那么考虑任意一种配对方式，如果树边W被多余1对的最短路经过，假设经过W的最短路有 那我们可以贪心减少费用，把这路径进行转化（假设a1与a3在u的左侧，a2与a4在v的右侧） 在保证路径的前提下，只删除了u-v可能讲得比较突兀，我上一下CF官方题解的图 然后，我们只需要考虑每条边对答案是否有贡献即可，后面比...

感受：真水题，满足感爆棚 直接上代码了，其实树形DP就是在树上进行DP #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const ll inf = 1e18; struct edge{ int v, nex; ll w; }e[maxn << 1]; int head[maxn]; int n, m, s, cnt; int deg[maxn]; ll dp[maxn];///dp[i]表示从i点出发不能到达其任...

感受深深感觉到我很弱，树上倍增居然可以这样用！ 如果想到倍增，应该就可以想到这个DP以及转移式。但是存在一个问题：如何初始化dp[i][0]呢？ 求解完DP后，如何求答案呢？对于每一个询问q, u, v, c;我们可以再u的后面加一个点r，然后从r开始往上跳 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; struct edge{ int v, nex; }e[maxn << 1]; struct nod...

思路模板题：一般这种题就是先枚举一个区间的左端点，然后用数据结构维护另外一个区间左端点选择。 如下图如果枚举一个区间的左端点选择i点，那么另外一个区间左端点的选择情况只有5种情况。如果枚举一个区间的左端点选择（i - 1）点（图中未画出），那么另外一个区间左端点的选择情况只有6（5+1（i + k - 1）为左端点）种情况。发现没，这样就可以不断维护左端点选择为[i + k, n + k - 1]的最大值。 其实这道题也可以暴力用线段树搞，只不过代码量大一点常数大一点，哈哈。 卧槽，刚刚发现连优先队列都不需要用，毕竟维护后缀最大值，直接O（n）就可以了所以总复杂度就是O（T * n） ...

吐槽：我TM人都傻了，为什么这两种写法在牛客机子评测时会补题呢？是数据的锅吗？（1）（2）这两种写法有什么区别呢？难道是我对break函数有误解？ 思路回文子串的构造，一般都是某一个回文子串两边同时加上一个相同的字符。所以我们就可以想到用dp[i][j][x][y]表示串a中i-j与串b中x-y能不能构成回文子串？ 如果串a中i-j与串b中x-y能构成回文子串? 它可能由哪些状态更新过来的呢？串a中(i + 1) - (j - 1)与串b中x-y转移串a中(i + 1) - (j)与串b中x-（y-1）转移串a中i - (j - 1)与串b中(x + 1)-y转移串a中i - j与串b中(...

思路： 算是比较有意思的贪心^-^其实乍看就是简单01背包问题，由于我太弱没想到怎么优化复杂度。于是，换了贪心思路。 考虑一个简单问题，如果现在给定最多取K人，那么怎样最优取呢？显然找出n个人中s[]大于等于K的人，记为S。那我们只需要在S集合中找前K大的v值，并对其求和 敲黑板：最暴力的方法就是,然而这道题给的人数规模为n，也是表明K最多有n种，这样暴力跑下来复杂度还是 如何优化复杂度呢？我们把n个人的s进行从高到低排序，若，记取值集合为S1，取值集合为S2，S2肯定包含S1中部分元素，这就表明在求解S2时有些元素根本不需要枚举，直接从S1中获得了，这就是优化的出发点。 用SUM记为...

思路：所有询问按照k从小到大排序，为什么要这样呢？显然，如果小与等于k1的答案处理出来了，那么怎么处理k2（k2>=k1）的答案呢？如果在数组中所有小于等于k1的位置被高亮了，那么在数组中所有小于等于k2的高亮位置一定包含k1的高亮位置，这样从小到大跑过去，最多高亮n个点。那么答案是什么呢？ 怎么维护高亮点数呢？直接用树状数组动态维护。复杂度O（nlogn） #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; struct Query{ int l, r, k; in...

其实数据开到1e3还是可以轻松通过的haha😁 思路 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; const ll mod = 1e9 + 7; struct edge{ int v, nex; }e[maxn&n...

  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const ll mod = 998244353; struct edge{ int v, w, nex; }e[maxn * 2]; int c...

思路：设主串为S，判断模式串是不是S的子序列？贪心考虑，从左到右扫一遍S，如果当前字符在S中出现，那么我就找到S中最先出现的位置A1，然后我们下次找的位置要大于A1，以此类推。 复杂度分析二分查找 + 枚举 = O（ ） #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; vector<int> pos[30]; char s[maxn], tmp[maxn]; int n, m; bool solve(){ int ind =...

解题思路：维护两个双端队列，其中一个队列维护严格单调递增序列，另一个维护严格单调递减序列。 以最大值求解为例 以下的双端队列为手写 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; int ma[maxn], mi[maxn], a[maxn]; int n, k; int stk1[maxn], stk2[maxn]; ///stk1维护单调严格递减 stk2维护单调严格递增 int f[3], e[3]; void solve()...

A：牛牛的DRB迷宫I思路：设dp[i][j]为起点在(i,j)时的方案数那么dp转移式就显然可以得到： if(s[i][j] == 'R'){ dp[i][j] = dp[i][j + 1]; } if(s[i][j] == 'D'){ dp[i][j] = dp[i + 1][j]; } if(s[i][j] == 'B'){ dp[i][j] = dp[i][j + 1] + dp[i + 1][j]; }考虑到此dp转移式是由后面状态更新，所以用递归写比较简单 #include <bits/stdc++.h> using namespace std...