about 3 years ago

论蒟蒻到底有多弱。。。本来紫名改机制后掉回蓝名,打个都掉了我真的是没救了。。。
忽略我们直接从开始讲起吧。

C

题目大意就是我们可以根据一个数列,构造出一个矩阵,使得。现在给你这个矩阵中的个所有元素,要你还原这个数列。
感觉我好啊,其实就是我们不断的取最大值就好了。
不妨设,那么给定矩阵中最大的那个数一定就是
去掉这个数以后,矩阵中其余所有数都是的,其中的最大值就是,我们用消去,然后问题就变成的规模了,以此类推。。
C.cpp

D

题目大意就是给定一个长度为的数列,将其循环次,求最长不下降子序列。
这道题我考场上想到做法了,但是没调出来= =。
我们考虑一个单位的数列满足数值上在范围内的最长不下降子序列长度为
怎么求出这个呢,我们可以先求出数列上以开头和结尾的最长不下降子序列,设其为,这个可以。那么的初始值就是,然后从内向外扩展即可。
求出了之后,我们可以记。由于最长不下降子序列的最大值最多上升次,我们可以保证每次值都上升的情况下,在的时间内出来(我偷了个懒写了个的),其余保持相同值的一个单位序列我们都可以用去计算。
D.cpp

E

题目大意你还是看原题吧。。。
这题在考试的时候根本没时间看。。。
我们知道如果一个要出现在长度为的子串中的话,要满足
因此我们记
我们先固定,设,对于满足的我们设为,那么我们找出每一段连续的,设长度为,计算这一段选出连续的方案数也就是
由于,因此我们搞出所有的,计算一下有哪些使得,然后再对每一个做一遍答案就好,这之中需要用到一点点求求和的知识来加速。具体看代码吧,看不懂也可以自己想一想很好推的。
时间复杂度是是指的约数个数。
E.cpp

← bzoj1046:[HAOI2007]上升序列 bzoj1047:[HAOI2007]理想的正方形 →
 
comments powered by Disqus