C题 求一颗树删去某个点后 形成的森林的最长上升子序列 最短, 输出最短的值 思路 : 点分治 + 线段树合并 首先解决第一个问题 如何求一颗树的最长上升子序列 ? 首先 最容易想到的就是 树上dp 先将树变成一颗有根树 (根随意) 对于 一颗以点 为根的树 ， 所有经过 的 最长上升子序列（并不一定要选择, 只是构成的数组经过）, 要么 为端点 要么 为 中间的某个点, 如下图表示两种情况 那么只要以每个点为根 都求出上图所示的两种情况的LIS， 取 即使答案 方法有很多，这里说一下比较常见的， 线段树合并 对于 每一个点， 都开两颗权值线段树, 其中 lis[i] 表示 最后一个...

这题 无非两种操作 一种对于当前的时间 在这个时间 的时间之前的时间操作要舍去 当插入元素后 如果元素数量大于 要舍去优先级最低的 一 个 如果只有上述两种操作， 很明显一个队列模拟即可只需按时间依次插入，每新到一个时间， 先while 循环从队头删去第一种情况的然后插入当前元素， 判断数量是否大于 m 大于就再把队头元素减去即可答案就是再插入前判断当前队列中是否有要的元素 但是他会有另一种操作， 是 改变某个元素的优先级 那么一个简单的队列就做不了了因为队列本身无序（相对于要查找的来说）所以不能二分, 并且删去这个元素再放入的操作队列也做不了 但是容易发现，上述的操作只会改变队列中...

链接：https://ac.nowcoder.com/acm/contest/16832/H 来源：牛客网 请问一下， 官方题解是直接dfs的， 有不进行dfs 直接递推的方法吗？

D题 观察一下 对于 来说 其中 会发现 对于连续的 中会有一些数的对于连续的相同的 数来说，每多一个数对于 的余数相当与减去 即是一段数的和而这一段数每一个之间差值 为 本身不会超过 所以可以开一个 来记录前 项 每项之间差的前缀和可以边求数边处理 时间复杂度 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; const int mod = 998244353; ll f[maxn], sum[600][maxn]; int K;...

他说了数字的范围是 int 以内, 所以直接桶排序会爆内存（也不知道为什么能过, 出题人数据太水） 正确同排序方法 应该是先缩小范围, 然后在桶 先采用分块的方式 开个vector <int> [maxn] 来放 然后 On 的时间就可以把范围缩小其中的某个 块内 这个时候最大值和最小值相差不超过 1e5， 采用桶排序即可 #include <iostream> #include <algorithm> #include <cstring> #include <cm...

首先 用数学归纳法证明斐波那契数列前n项平方和 等于 f[n] * f[n+1];假设 第 n 项时满足 前n项平方和 等于 f[n] * f[n+1];那么 第 n+1 项时 应该是 f[n] * f[n+1] + f[n+1] * f[n+1]= f[n+1] * (f[n] + f [n+1] )= f[n+1] * f[n+2] = 假设的情况且 第 1 项 平方和 满足证毕定义 一个列向量 存放 (f[n+1] f[n] )T根据矩阵的乘法性质 可以看出1 11 0这个矩阵乘以 列向量 (f[n+1] f[n])T 就等于 (f[n+2] f[n+1])T所以 (f[n+1] ...