DAY01:
T1 : T75481.礼物
大致题意:小明有 m 元 , 一共有 n 件物品 , 有 v 和 w 两个属性 , 一共有 t 次 购买方案 ,
每次要买 q (奇数件)物品 , 要求购买q件物品中位数最大值。
SOLVE1: 暴力
对于每次购买进行dfs枚举,排列出所有的可能性并找到其中的最大中位数的值。应该能拿 50分
SOLVE2:二分答案(即正解)
因为中位数是具有单调性的 ,所以能够想到二分答案
对于每次购买去 二分可能的中位数(范围在 Vi 中的 最小值 ~ 最大值) 并检查可行性:
T2 : T75482.秘境
大致题意:题面看似很复杂,但看了样例后简单地就能发现他想要求的就是 1 ~ n 的所有数的开平方并向下取整的和。懂了这个之后,就很简单了,我们可以枚举 1~n 所有的数,并加和所有的sqrt()
SOLVE1:暴力
但是枚举1 ~ n 时间复杂度为O(n) 而题面的数据中最大n到达了10e18,暴力就会直接爆炸(只能拿3个点),那么我们就需要亿点点的数学优化了
SOLVE2:数学优化
我们不难发现,题目想要求的就是对于 i 在 1 ~ n 中 求和 :
∑i=1n⌊i⌋\sum_{i=1}^n \lfloor\sqrt{i}\rfloor i=1∑n ⌊i ⌋
这样我们大概会要求一个这样的数列的各项和 :
1,1,1,2,2,2,2,2,3,3,3.....,n\begin{matrix} 1,1,1,2,2,2,2,2,3,3,3....., \sqrt{n} \end{matrix} 1,1,1,2,2,2,2,2,3,3,3.....,n
那么我们就可以令 m=⌊n⌋m = \lfloor \sqrt{n} \rfloorm=⌊n ⌋ ,就可以将上式转换成两个不同的式子:
∑i=1n⌊i⌋=∑i=1m−1i2+∑i=m2ni\sum_{i=1}^n \lfloor\sqrt{i}\rfloor = \sum_{i=1}^{m-1} i^2 + \sum_{i=m^2}^n i i=1∑n ⌊i ⌋=i=1∑m−1 i2+i=m2∑n i
得到这两个式子之后题目就变得简单了,我们只需要化简一下这两个式子就好了。对于第二个式子,只需要使用非常简单的求和公式 :
∑i=m2ni=m(n−m2+1)2\sum_{i=m^2}^n i = \frac{m(n - m^2 + 1)}{2} i=m2∑n i=2m(n−m2+1)
但是对于第一个式子,我们就需要使用非常高级的平方和公式了:
∑i=1mi2=m(m+1)(2m+1)6\sum_{i=1}^m i^2 = \frac{m(m+1)(2m+1)}{6} i=1∑m i2=6m(m+1)(2m+1)
想要推导的话就更困难了,但是这里还是稍微论证一下吧
(n+1)3=n3+3n2+3n+1(n+1)3−n3=3n2+3n+1=3(n2+n)+133−23=3×2×2+3×2+123−13=3×1×1+3×1+1(n+1)^3 = n^3 + 3n^2 + 3n + 1\\ (n+1)^3 - n^3 = 3n^2 + 3n + 1\\ =3(n^2 + n) + 1\\ 3^3 - 2^3 = 3 \times2\times2 + 3 \times2+1\\ 2^3-1^3 = 3\times1\times1+3\times1+1\\
(n+1)3=n3+3n2+3n+1(n+1)3−n3=3n2+3n+1=3(n2+n)+133−23=3×2×2+3×2+123−13=3×1×1+3×1+1
*对于所有的(i+1)3−i3(i+1)^3 - i^3(i+1)3−i3*进行合并可以得到:
(n+1)3−13=3(12+22+...+n2)+3(1+2+..+n)+n(n+1)^3 - 1^3 = 3(1^2+2^2+... +n^2) + 3(1+2+..+n) + n (n+1)3−13=3(12+22+...+n2)+3(1+2+..+n)+n
移项一下可以得到:
12+22+32+...+n3=((n+1)3−1−3×n(n+1)2−n)÷3=2n3+6n2+6n−3n2−3n−2n6=2n3+3n2+n6=n(n+1)(2n+1)61^2 + 2^2+3^2+...+n^3 = ((n+1)^3-1 - 3\times\frac{n(n+1)}{2}-n)\div3 \\ = \frac{2n^3+6n^2+6n-3n^2-3n-2n}{6}\\ =\frac{2n^3+3n^2+n}{6}\\ =\frac{n(n+1)(2n+1)}{6} 12+22+32+...+n3=((n+1)3−1−3×2n(n+1)
−n)÷3=62n3+6n2+6n−3n2−3n−2n =62n3+3n2+n =6n(n+1)(2n+1)
最终可以得到:
∑i=1n⌊i⌋=m(n−m2+1)2+n(n+1)(2n+1)6\sum_{i=1}^n \lfloor\sqrt{i}\rfloor = \frac{m(n - m^2 + 1)}{2} + \frac{n(n+1)(2n+1)}{6} i=1∑n ⌊i ⌋=2m(n−m2+1) +6n(n+1)(2n+1)
这样我们就可以O(1)算出答案了
T3 : T75480.二分图匹配
*大致题意:有两个字符串S1,S2(只含有A~Z),我们要将他们进行匹配,规则是:对于每个i,j 和 S1i和,S2jS1_i和,S2_jS1i 和,S2j ,S1i=S2jS1_i =S2_jS1i =S2j 且 i1<i2i_1< i_2i1 <i2 ,j1<j2j_1<j_2j1 <j2 即匹配的每个字符需要相同且每次匹配之后,只能在后面选择字符进行匹配了。
正解思路:
我们可以考虑用动态规划的方法,用二维dpi,jdp_{i,j}dpi,j ,计算在S1字符串的i位置时,匹配成功j次最早的位置。但我们还要考虑S2的字符与S1匹配否则复杂度是O(nm)会超时,因此我们可以预处理出:t[i]数组,表示字符i在S2中第一次出现的位置和数组nxti,jnxt_{i,j}nxti,j 表示在S2中从第i个字符开始,字符j第一次出现的位置*
T4 : 三角游戏
大致题意:给你一个正n边形,每个点都有相应权值,要求在这个n边形中选择 3x3x3x个点构成 xxx个三角形,对于每个三角形(i,j,k)的得分是a[i] * a[j] * a[k],求能获得的最大分数,且所有三角形不能重叠
题目最难的地方在于如何不重叠三角形,但其实我们只需要将原题转化一下,把这个正n边形看成一个环,我们每次选定3个点,获得的分数并加上将余下的两个(或一个)剩余部分加和或者计算分割成三个区间的最大和。这样我们就得到了一个纯正的动态规划