题意

给定一个正整数数列A，求一个平均数最大的、长度不小于L的子段。

solution

考虑check问题，正着枚举起点，我们需要知道每个起点所能枚举的最大值。当一个数大于当前二分的平均数时，它一定是对答案有贡献的，因此倒过来预处理每个起点能枚举到的最大值即可。时间复杂度 $O(nlogn)$。

题意

给你两个数 $a$ 和 $b$，$q$ 次询问 $[l,r]$ 内满足 (($x$ mod $a$) mod $b$) != (($x$ mod $b$) mod $a$) 的 $x$ 个数。（$q<=500,1<=a,b<=200,1<=l<=r<=1e18$）

solution

若 x % a % b != x % b % a，则(x + a $\times$ b ) % a % b != (x + $a \times b$ ) % b % a. 可以得到规律一定是以 a $\times$ b 为循环的，因此预处理前 a $\times$ b个即可。

题意

$n$ 件食材（每种食材的数量可以视为无限），小明连续工作 $T$ 时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第 $i$ 道菜肴有三个属性 $ai$，$bi$，$ci$，$ai$ 是该菜肴的美味值，$bi$ 是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：$ai-t*bi$，完成这道菜需要 $ci$ 的时间。求在这 $T$ 时间内能做出菜肴使得总美味值的最大值。

solution

首先需要贪心确定顺序，考虑只有两道菜，可以得到：$a_i−b_i∗c_i+(a_j−b_j∗(c_i+c_j))>=a_j−b_j∗c_j+(a_i−b_i∗(c_i+c_j))$，化简后得到：$b_i∗c_i>=b_j∗c_i$。排序后背包即可（需要降维）。

题意

三个人玩游戏，每个人最开始都有 $n$ 个数，开始轮流删数，直到最后每个人只剩下一个数。第一个人想让这三个数的和（$x+y+z$）加起来尽量大，第二个想尽量小，第三个想尽量接近0。每个人都以自己的想法为策略，问最后得到的三个数的和是多少（$n<=100$）。

solution

不要想复杂了，其实就是直接模拟。暴力枚举三个数，因为第三个人想尽量接近 0，因此枚举 $z$ 时维护最接近 0 的解 $m1$，因为第二个人想要最小值，因此取枚举所有 $z$ 得到的解（$m1$）的最小值$m2$，然后第一个人想要最大值，所以取枚举所有 $y$ （$m2$）的最大值 $m3$。

求最长回文串

解法一：中心扩散法

过于傻逼，就是枚举中心点向两边拓展长度直到不相等。（时间复杂度 $O(n^2)$，空间复杂度 $O(1)$）

Code

题意

给定一个长度为 $n$ 的数组，求长度为 $n-m$ 的不同子序列个数。（$1<=n<=1e5, m<=10$）

Solution

$dp[i][j]$ 表示长度为 $i$，删除 $j$ 个元素的子序列个数，不考虑重复的话，有 $dp[i][j] = dp[i-1][j] + dp[i-1][j-1]$（即已经删除了 $j$ 个和已经删除了 $j-1$ 个再删除这一个的情况）。

题意

给定一个由n个元素组成的序列 { a₁, a₂, a₃,…, a_n } ，她想知道其中有多少个子序列 { a_p1, a_p2, …, a_pm } $(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,…, < pm ≤ n)$，满足对于所有的 $i, j$ $(1 ≤ i < j ≤ m)$, a_pi^pj < a_pj^pi成立。

Solution1

py + dp直接冲。

题意

给定一个长度为 $n$ 的字符串，求不同的子序列个数。

Solution

很经典的一道计数dp。我们用 $dp[i]$ 表示以前 $i$ 个字符中的不同子序列个数：

题意

给定一个长度为 $n$ 的数组 A ，把所有长度 >= $k$ 的区间中的第 $k$ 大值插入 B 数组中，求 B 数组的第 $m$ 大数。

Solution

这种显然二分答案题我们主要关心 $check$ 问题。

题意

题意很简单，求长度为n的01串逆序对数量和。( n <= 1e18 )

solution

任意选两个位置 $i, j$ $(i < j)$，令 $a[i] = 1, a[j] = 0$，这样一定能产生逆序对，这样有 $C_n^2$ 种选法。剩下的位置随便放，有$2^{n-2}$种选法，总方案数即为答案。( 注意 1 需要特判 )