【火题合集】2.17考试

1.题目1

题目名字就叫这个。。

正解倒推O(mk)

然而我写的O(klogn)的splay 还少写了一句话萎了

不过加上之后比正解快得多

正解0.5s splay不到0.05s

 2.题目2

首先令dp[i][j] 表示km-1=i, km = j时b序列的最长长度

那么dp[i][j]=max(dp[k,i])+1, a[i]-a[k]<=a[j]-a[i];

直接转移肯定是O(n3)的

但是可以发现,若a[i]-a[k]<=a[j]-a[i],则a[i]-a[k+1]<=a[j]-a[i]

那么k之后的就不用再判断了

那么当我们确定了i之后,从前往后枚举j,随着j的增大a[j]-a[i]不断变大,只需将k不断向前推到最前的满足关系的地方k0并记录k0到i之间dp[k][i]的最大值即可。

那么枚举n次i,枚举n次j,对于每个i,k最多向前推n次,所以总复杂度为O(n2)

【听说这个叫单调队列

3.题目3

通过找规律发现n在斐波那契数列里时alice必输,否则必赢。。。

然后就是高精度了。。

另外还要压个位。。

极限压18位0.25s 23333

另外如果先排个序 那么斐波那契数列就不用重复求了 更快

 

说点什么

2 评论 在 "【火题合集】2.17考试"

提醒
排序:   最新 | 最旧 | 得票最多
游客

T4 comes from CTSC2009. ->_->

wpDiscuz