题意：动态求中位数 思路：建一个大根堆和一个小根堆 用大根堆维护较小的部分 （中位数左端）用小根堆维护较大的部分（中位数右端）这样大根堆堆顶的就为中位数 插入数据时维护两堆堆顶的大小关系即可 #include <bits/stdc++.h> using namespace std; priority_queue <int> que1; priority_queue <int,vector<int>,greater<int>> que2; void init() { while(!que1.empty()) ...

思路：树的题目多半和dfs有点关系 滑稽.jpg首先对于叶子结点的话 是一定要染色的 这显而易见 关键点在于对于已经被覆盖了的点的操作根据贪心 可能会想 已经覆盖的点我不再去动它了 但这其实是错的 很容易就举出反例 若其中有一个点覆盖范围巨大 这思路就是错的了所以对于其他的结点 更新最大染色范围的操作就是必须的 如果该结点的子节点可以染色到它的话 他就不需要再染色 更新最大范围 如果染色不到它 它就需要被染色 同时选择子节点内范围最大的点染色 更新最大范围 #include <bits/stdc++.h> using namespace std; const int N =...

题意：给出n个结点的树 用k种不同的颜色染色 当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同个染色方案才是合法的 题意：既然是颗树 连通性是一定的 题目说的有点绕 但其实就是至多给k个联通块染色 求染色方案数 从一个叶子结点出发考虑用 来代表前i个结点染j种颜色的方案数 转移方程也很容易想到就是即染和前一个结点一样的颜色 和 染新的颜色除去前j-1种外 还有 k - （j - 1）种 最后把n个结点染色情况相加即可 #include <bits/stdc++.h> using namespace std; #define LL long...

题意：给出n个数字 和 k 问将一个数字（只要一个）向前移动至少k个单位 有变化的向后顺延 使得 最大 思路：先预处理个前缀和 和 原始数组的答案 越往前面越小 为了保证答案最大只需要移动k位就好 然后从第k+1位开始枚举变化情况 因为每次移动在当前位置i 到 i - k区间内的数都会往后顺延1位 则加上他们的区间和 而当前位置向前移动了k位 所以要减去k对答案的贡献 过程中维护最大值就是答案 #include <bits/stdc++.h> using namespace std; #define LL long long #define mes(x,a) memset...

题意：求区间l,r中的数x 及其 x的约数最高位出现的次数 思路：首先利用前缀和的思想将问题转化成求 [1,r] - [1,l-1]题目是说求x的约数首位出现次数 自然就想到枚举因子 假设当前有因子a 则另一个边界显然就是x/a将他们都假设成 L,R 所以问题变成了在L,R中 求最高位为出现的次数而求L,R中的出现次数 我们可以通过枚举最高位和位数 右区间 - 左区间 + 1 将答案统计即可过程量记得开LL 否则会炸int #include <bits/stdc++.h> using namespace std; #define int long long int ansl[...

题意：将n个点分成n/2个集合 问最小代价是多少 思路：通过画图可以发现，当某个结点的子树结点个数（包括它本身）个数为偶数的话，他是可以实现内部互联的，反之，如果点为奇数的话，它肯定要和外边的点相连，所该点到父亲结点的一定会有贡献 #include <bits/stdc++.h> using namespace std; #define LL long long const int N = 10010; struct node { int w; int to; int next;///相同起点的上一次加入的边的存储位置 (指向下一条边在edge数组中...

题意：在主串中寻找子序列 思路：字符串长度都来到了1e6 暴力肯定超时 我们可以先预处理一个next数组来表示主串当前第i个字符到任意26个字母下一个位置是在哪 然后模式串根据next数组匹配 复杂度为 "图片标题") #include <cstdio> #include <cstring> using namespace std; const int N = 1e6+5; const int M = 2e5+5; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; int nex...

题意：给出n个结点m条边的无向联通图 备注里说边的数量m恒等于n-1 那么就是一颗树 选出一个点s 使得所有度为1的结点都到不了s 度为1的点显然就是叶子结点 思路：既然是树形dp 那么就先思考下他们的子问题是什么 目标是使得所有叶子结点都到不了s 显然子问题要从子树开始入手 处理的方法也就两种 1是直接删除s和子树的联系 2是删除子树和叶子结点的联系 用dp[u]来代表叶子结点不能到根的最小代价 则转移方程为 "图片标题") #include <bits/stdc++.h> using namespace std; #define LL long lo...