C-Alice and Bob 题目大意： m次询问，每次询问一个区间中有多少个连续的的子区间不同数的个数大于等于k（强制在线） 思路： 首先考虑朴素做法假设i作为左端点时向右扩展到f[i]这个区间有k个数字枚举区间[L,R]内 的所有的数字作为左端点对于[L,R]内的一个点t， f[t]<=R，那么t作为左端点的贡献是(R - f[t] + 1) f[t]>R，那么t作为左端点的贡献是 0 由于f数组是不递减的，我们可以在[L,R]中二分一个位置pos如果pos作为左端点的贡献是0，那么[pos,R]的所有贡献都是0对于有贡献的部分可以用公式这部分可以用前缀和公式O（1）求...

题目大意： 选两个节点u,v，使得两个节点的子树和权值最大，且fa[u]!=fa[v] 思路： 对于一个节点u假设有子节点v1,v2,v3..... 我们用mx[u] 记录u的子节点及其孙子节点中（反正就是u点下面的）任意一点为根的子树和最大值； 有没有大佬帮我用术语描述一下上面的句子 sum[u]为以u为根的子树和 N^2枚举两个点显然是不行的 缩小答案产生的范围 对于一个节点u 那么答案肯定产生于他两侧的所有节点中 我们mx记录的这个东西刚好记录了一个节点下面所有的节点 所以我们选出一个最大，一个次大就行了 CODE： int h...

题目描述n 个点，m条边， q个询问 ，每次输出 x,y的最短距离 思路首先看一个弱化版的给你n个点 ，n-1条边构成一颗树，q个询问，每次输出树上两点x,y的距离 这个题就是一个裸的LCA，lca的dfs完之后可以直接输出 int dis(int x, int y) { return depth[x] + depth[y] - 2 * depth[lca(x, y)]; }这个题 的 1≤ m≤ n+100 也就是说 多出来了100条边 就是 唯一的不同之处 我们先假设用其中的n-1条边构造一颗树，跑一边LCA ，求出q个询问中的 ans[i] = dis(x, y);然后...

题目描述：给一字符串，选出一段区间包含26个小写字母，求最短区间长度Slove：用尺取法，从l=r=1开始，如果【l,r】中不足26个小写字母 r++，否则 先记录答案，然后l++；代码 #include <map> #include <set> #include <cmath> #include <stack> #include <queue> #include <cstdio> #include <bitset> #include <vector> #include <iomanip&gt...

题目描述超市里有N件商品，每件商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品不能再卖。 求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。 输入格式输入包含多组测试用例。 每组测试用例，以输入整数N开始，接下来输入N对pi和di，分别代表第i件商品的利润和过期时间。 在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。 输出格式对于每组产品，输出一个该组的最大收益值。 每个结果占一行。 数据范围0≤N≤10000,1≤pi,di≤10000Slove：按照日期从小到达排序，维护一个堆heap，对于第i种物品如果今天卖他但是a[i].da...

Slove：要求价值的中位数，那首先要对价值进行排序，m为奇数的情况下然后我们枚举每个位置，如果该位置是中位数的最大，那么这个位置前面选m/2个的重量加上后面m/2个重量，使他们小于V就说明这个位置可以取得的，只需要维护一个大小为m/2 的堆就行，每次pop掉堆中最大的m为偶数的时候同理但是中间需要选择两个位置，数据范围为1e5，n^2肯定不行，所以用nlogn的算法，可以枚举第一个位置，二分第二个位置代码 #include <map> #include <set> #include <cmath> #include <stack> #inclu...

题目描述：有一个长度为n的序列，从中选择任意个数字将其分成两堆使两堆的和最大（且两堆的差值不超过m）先证明一下 取两次转化成一次的正确性 假设第一次取了 a ,b第二次取了 c ,da-b=mc-d=m-1那么如果我们把c放在a这端 明显是错误的我们把c放在b端( a+d )- (c+b)=-(m-1)+m=1 也就是说我们所有的操作都可以转化为一次实现这里我们考虑dp的状态表示 设dp[i][j]表示前i个数中 差值为j 的时候能够带走的武器的最大重量 对于每种武器，我们有三种选择 1.不选 dp[i][j]=max(dp[i][j],dp[i-1][j]...

一开始思路错了，想着把k当成1 求了一个最大子矩阵然后对最大子矩阵所在的一行用最大k段子序列，后来发现思路错了，因为这样所求的子矩阵的终点行一定都相同了正确的思路：因为m（列）是1<=m<=2，只有两种情况，对于m==1时候就是个竖着的最大k段子序列的和， dp[i][x][y] 在第一列的1-x行选择 在第二列的1-y行选择 共选择i个矩阵 1.假如选择第（x,1） 不选（y,2） max(dp[i-1][t][y]+a[x][1]-a[...

题目描述一棵树，每个节点有一个颜色，q个询问每次询问x，y求树上距离最长的两点其中一点color【i】=x;另外一点color【i】=y；思路1.对于求树上两点之间的距离可以用lca，倍增法求lca也不再介绍2.求max(color[i],color[j]]如果只看一种颜色x求最长的距离可以枚举是x颜色的每个点我们暂且叫颜色x的直径如果看两种颜色x,y 那么max是x直径的两端点中的其中一点和y直径中两端点中的其中一点 具体证明（https://blog.nowcoder.net/n/3b7f889807bf4bd4ad35f74b42e81c22） 由于color[i]比较大要可以先离散...

题目描述任务一：有n个人，每个人只能选一次，会消耗a[i]精力得到b[i]收益，现有的精力值为C,求可以到达的最大收益思路这么看就是一个简单的01背包问题（用一维的话注意从大到小枚举c（精力））任务二这n个人之间存在友谊关系，我们只能选择跟1有关系的人，思路用简单的并查集维护，在01任务1求解的时候判断 if(find(i)!=1) continue;代码 #include <map> #include <set> #include <cmath> #include <stack> #include <queue> #incl...

两种bfs解法解法一（315ms）：关于这种解，我最后放了个33%的代码，有没有大佬指正一下错误应该错在关于B的移动方式了。思路 让A在图上跑一次bfs记录A到达每个点的最短时间 让B在图上跑一次bfs记录B到图上每个点的最短时间 然后枚举每个点让他们在这里相遇，取最小值注意小B每次是跑两个点代码 #include <map> #include <set> #include <cmath> #include <stack> #include <queue> #include <cstdio> #include <bi...

题目描述： n种牌，每种a[i]个， m张万能牌 ，一次只可以代替一种牌 组成一套的条件：每种牌各一张 求最多组成的套数题解直接二分答案（最多能组成的套数）如果该种牌不够 那么差的牌=mid-a[i]差几张我们就用几张joker 代替因为我们要组成mid套牌每套牌最多有一个joker 所以 设添加t张joker所以 t<=m&&t<=mid 代码 #include <map> #include <set> #include <cmath> #include <stack> #include <queue&gt...

由于状压dp是在位运算的基础上进行的，所以先了解一下一些基础的位运算操作我们把每一行的状态用二进制储存起来 ll x=read(); a[i]=(a[i]<<1)+x;假如输入的是101那么a[i]的变化过程为a[i]=1a[i]=2a[i]=55的二进制刚好是101解决了储存问题，在解决图上冲突问腿有一个二进制数字x if(x&x<<1)可以判断是否有相邻的两者相同还有一种冲突是当前状态j和地图状态不符合假如地图状态（第i行）a[i]=1011j1=1100（不合法）j2=1000(合法) 那么j1&a[i]=1000j2&am...