HDU4565题意： 给出a，b，n，m，求S_n=\lceil(a+\sqrt b)^n\rceil\%m。其中0

题意： 给出一个序列，从左往右每次选择一个长度为m的区间，对于每个区间，找出它的最大值max和从左往右扫描该区间时最大值的变化次数cnt。 思路： max用单调队列维护是常规操作。但是cnt要怎么在O(n)的复杂度内统计呢？ 倒着单调队列就可以了。 比如样例3 2 2 1 5 7 6 8 2 9，先把(9,9)放入队尾，因为2比9小，继续吧(2,8)放入队尾，(8,7)比(2,8)更优，这时候应该

题意： 有n个反面朝上的硬币，每次可以选a个硬币扔，要扔m次，目的是尽可能得让正面朝上的硬币多。问硬币正面朝上的期望为多少。 思路： 题目又看错了…主要是样例手算不出来…就以为本来的理解是对的… 事实上它是有贪心在里面的，因为尽可能要让正面朝上的硬币多，所以每次尽可能扔反面朝上的硬币，如果反面朝上的硬币不足a个的话，把反面朝上的硬币全选了以外正面朝上的硬币也选几个。 这里就可以dp了。 dp[i]

题意： 有一个长度为m的窗口，一个长度为n的序列，现在将这个窗口在序列上滑动，问每次滑动这个窗口内数的乘积模p的总和为多少。 思路： 可以将序列分成长度为m的若干块，每次滑动窗口的乘积可以用前一块的后缀积与后一块的前缀积拼起来得到。所以预处理出每个数在自己的块内的前缀积和后缀积即可。 挺巧妙的。 代码： typedef long long ll; ll a[1000010]; ll pre[100

题意： 给出一片森林，问能找到多少个三元组(x,y,z)满足f[y]>f[x]和f[z]>f[x]，并且x是y的祖先，y是z的祖先。 思路： 对于每个点作为y，答案为y的祖先中f比它小的乘以y的子树中f比它小的。y的子树中f比它小的，之前上一篇博文中用dfs序解决了这个问题，但是这里考虑到这里比较的不是编号而是f，所以像那个做法比较麻烦，所以可以考虑另一种做法，对于一个点，进入它的时候

题意： 有一棵n个结点的树，结点编号分别为1～n，询问对于每个结点，它的子结点中有多少结点的编号比它小。 思路： 这里用到了dfs序。 dfs序的介绍见这里：https://www.bilibili.com/video/av4482146?from=search&seid=7981889138645681255。 dfs序有一个可以利用的性质是每一棵子树在序列里都是连续的，所以可以对每个结

题意： 有n个城市，每个城市有一个被抢劫的风险值，现在有q次询问，问u到v在不经过风险值大于w的条件下的最短路长度。其中1≤n≤200，1≤q≤2×10^4，1≤w≤10^5。 思路： 不经过某些城市就相当于不用某些城市松弛，这可以想到floyd，最外层是松弛的城市，所以容易想到要将城市的风险值进行从小到大排序，即从小到大进行松弛，再把每次松弛的结果保存下来，相当于三维dp表示经过前i个城市进行松

题意： 有0~n-1这几个城市是连通的，每个城市之间连接着一些道路，问有几种删除边（有可能不删除）的方案，使得这些城市还是连通的，剩下的边最少（即生成树，剩下n-1条边），对于每个城市，它们到0的最短路不变。 思路： 因为只能有n-1条边，所以对于每个点每次加边的时候只能加一条。 首先算出每个点到0的最短路，然后对于每个点找一个父节点，如果0到父节点的最短路+该点到父节点的距离=0到该点的最短路，

题意： 给出一个长度为n且元素不超过k的序列，问删除m个数之后不同的序列有几种，模1e9+7。其中1 ≤ n ≤ 10^5，1 ≤ m ≤ min \{ n - 1, 10\}，1 ≤ k ≤ 10。 思路： dp[i][j]：前i个数字删除j个数字的方案数。 有转移dp[i][j]=dp[i-1][j](不删除该数字)+dp[i-1][j-1](删除该数字)。 考虑到序列里面可能有重复数字，比如

题意： 给出一些树组成的森林，让你添加几条边让它们连成一棵树，并且使树的直径最小。 思路： 要使直径最小，可以想到以前一道题目，可以连成菊花形，所以把直径最大的放在最中间，然后其他的连在它的外面，这样子的话，连成一棵树以后，最大直径肯定只跟两棵树有关，当然一棵树的时候就是树的直径，两棵树的时候是两个树的直径+1，,三棵树及以上的时候，最大直径肯定是最长的树的直径+第二长的树的直径+1或者第二长的树