about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1047
分析:
这道题就是一道单调队列的裸题。。。然而我的第一想法竟然是树套树= =
bzoj1047.cpp

 
about 3 years ago

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

C

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

D

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

E

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

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1046
分析:
注意一下,题目中的字典序是按照下标的字典序。
我们记表示从开始的最长上升子序列长度,这个很显然是的经典问题。
对于每一个询问,我们顺着扫一遍就行,时间
bzoj1046.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1045
分析:
我们设表示第个小朋友给第个小朋友的贡献。
那么有:




其中表示平均数。
我们可以先令,那么其他的也都可以求出一个值。
很显然如果增加,那么所有的都要增加
因此我们找出第小的,令,再重新计算一遍即可。至于怎么找中间的那个数,我只能说_大法好
bzoj1045.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1044
分析:
其实这道题也挺水的说。。。
对于第一问,我们先二分一个答案,贪心判断即可。
有了第一问后,我们的问题就是将木棍分成最多块且每块长度不超过第一问长度的方案数。
表示前个木棍被分成块的方案数,那么有:
,这个是可以做到的。
时间复杂度就是
bzoj1044.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1043
分析:
这个计算几何挺水的。。。就是要注意一下内切的情况。
bzoj1043.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1042
分析:
我还真没想到竟然是容斥。。。太6
不会容斥原理的先看看书吧,总之对于一组询问,我们的答案无限制选择个数有一个超过的有两个超过的有三个超过的有四个超过的
至于怎么算超过的,我们把上限减去必须选的然后就等价于无限制选择了。
bzoj1042.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3926
分析:
传说中的多串后缀自动机。。。今天膜了一发
由于叶子结点数很少,我们可以倒过来从每个叶子结点建一棵树,然后合并成一个大树(实际上可以直接合并)。
接着就是询问树上的子串个数,注意树上的子串都是从深度小的到深度大的。
这个怎么做呢,就是处理出序,按序从一个结点的父节点扩展即可。
然后要么就是统计集合,要么直接一遍也可以,要用哦。
bzoj3926.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1041
分析:
http://www.cnblogs.com/jianglangcaijin/p/3455025.html
bzoj1041.cpp

 
about 3 years ago

题目链接:http://cojs.tk/cogs/problem/problem.php?pid=1769
分析:
这是写的第一道感觉好高兴。
感觉就是启发式建树+剪枝,推荐看一看http://www.cnblogs.com/eyeszjwang/articles/2429382.html
cogs1769.cpp