来一发B题的组合数学的解法首先考虑比较朴素的做法，枚举区间l,r枚举这个区间的值，然后用隔板法计数，复杂度O(n^3)我们用公式表示（来自官方题解）我们发现第一个式子和j没关系，第二个式子和i没关系操作一个这个公式变成那么我们只需要预处理出 计为num[i][k]那么最后答案的计算可以变成这里如何处理num数组的时候可以使用前缀和的方式， num[i][k] = pre[n][k] - pre[i-1][k] Code: ll fun[maxn],inv[maxn]; ll C(ll n,ll m) { if(n<m) return 0; if(m==0) retur...

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...