AHOI2007 题解

Posted on 2012-05-04 18:00 Mato_No1 阅读(642) 评论(0)  编辑 收藏 引用 所属分类: AHOI
【注:本沙茶完成AHOI2007的题目用了3年多……因为6道题中,有2题是2009年AC的,1题是2010年AC的,剩下3题是2012年AC的……】

box:
要求x2=kn+1(k为整数),即(x+1)(x-1)=kn。因为(x+1)和(x-1)所可能具有的共同的质因数只有2,因此可以分为两种情况:(1)x是奇数,且n是4的倍数,此时可以将(x+1)和(x-1)都除以2,n除以4之后,转化为(x+1)/2或(x-1)/2是n/4的倍数,然后直接求解;(2)其它情况:此时必然是(x+1)或(x-1)是n的倍数,可以直接求解。注意需要特判一下x=0的情况;

door:
求逆矩阵的问题。方法:设置N*N的矩阵A和B,A初始为待求逆的矩阵,B为单位矩阵,然后,不断地对A和B同时实施相同的初等行变换,直到将A变成单位矩阵为止,此时B就是A的逆矩阵,若无论如何也不能将A变成单位矩阵,则A无逆矩阵。
初等行变换有3种:(1)两行互换;(2)将一行整体乘以一个非0常数;(3)将一行加到另一行上。
具体操作:类似于高斯消元。第一步,i从0到n-1,在A的第i到(n-1)行中找到一个第i列不为0的(若找不到则A无逆矩阵),并将其与第i行互换(变换1),然后,对第i行后面所有第i列不为0的,将其整行乘以一个非0常数(变换2),使得其第i列的值刚好是-A[i][i],并将第i行加到这一行上(变换3)使得其第i列变为0,这样一直下去,可以把A的下三角全部变为0;第二步,i从n-1到0,对于第i行第(i+1)列及其以后的每个数,若有不为0的,将其乘上一个常数(变换2)使得这个数变为-1,再用后面的已经处理好的单位矩阵对应行加到第i行上(变换3),将这个数变为0,这样一直到最后一列为止,最后,要把第i行乘上一个常数(变换2)使得A[i][i]=1,这样第i行就处理好了,这样一直下去,直到所有的行都处理好为止。

light:
首先对这个字符串A[0..n-1]进行自身exKMP,求出nx数组,nx[i]表示A[i..n-1]与A[0..n-1]的LCP长度。
然后,点灯器的长度为p可行的充要条件是:(1)nx[n-p]==p;(2)对于整个nx数组,取出其所有大于等于p的元素,则相邻两个元素的距离(下标之差)都不超过p。
对于第(2)个条件,只要用一个线段树维护最大距离就可以了,枚举p的时候正、逆序均可,推荐逆序,这样实际上等于不断插入元素,比删除元素要方便。

rock:
超级大水题。只要把矩阵中所有的0变成-1,再求最大子矩阵就行了。

redcross:
求01矩阵中最大的某种性质的子矩阵类的题目。最暴力的做法显然是13个数组(原始数组+上下左右延伸0的长度+上下左右延伸1的长度+左上左下右上右下延伸的0正方形的边长),如果把上下左右延伸0和1的长度进行合并可以减少到9个数组,但这样对于这种如此卡常数的题目还是会TLE的。其实,可以换一种思考方式,最后只用6个数组(包括原始数组)就解决了问题……至于这个是肿么搞的,现在不能说,以后的某一天再说……
另外这里的最优解排序……发现有惊人的地方么囧……

maze:
由于可以随便走,N<=10,因此可以枚举前5步的走法和后面5步的走法(其实全是一样的,枚举一次就行了,只是存储方式不同),把能得到的所有权值和分最后到达位置(前5步)和开始位置(后5步)存在数组里,然后就是二分查找了囧……至于N<10的情况就少几步枚举了囧。其实还是比较难写的,本沙茶2009年写这题的时候写了整整一晚上,当然这或许与本沙茶当时太太太太太……弱了有关(当然现在仍然弱)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理