话说暑假就快结束了，也不知道blogger什么时候解封啊。用XX门进来的。
今年跑去参加了一趟NOI,被虐的很惨，而且是我认识的人里最惨的一个。
SXY没高三了，所以明年要加油了....有些东西下次补齐
2009年4月22日星期三
准备AHOI
这段时间真的郁闷了。
我做SGU的题目，真的很搞笑。因为我看到的题目不是我想死也想不出来的，就是我一想就出来的，然后程序不是巨烦就是巨简单，都不想写。
然后做前几年的AHOI的题......简直是被虐啊......会写的还是会写，不会的还是不会......估计我去，能把所有简单题切掉就行了，我没有其他要求了.....最后拿个两三百分，也挺好.....
还有就是我这两天都是上火上到死啊....今天中午要睡午觉了，刚躺下就流鼻血了.....我发誓我没有在想什么邪恶的东西.....算算这都是这个星期第五回了吧。希望考试的时候不要弄出去年YK的事情，这哥们去年居然过马路的时候就流鼻血了.....
准备的时候才知道我还有很多东西不知道啊....比如差分约束系统....比如很多线段树的应用....比如一大堆动规题（什么1D/1D和四边形不等式).....再比如什么遗传算法啦，最小费用最大流啦，带上下界的最大流啦，比如最优二分图匹配啦，LCA和RMQ以及+-1RMQ啦，什么各种诡异的数据结构啦（话说我平衡树还不会写）什么状态压缩动规啦......一大堆要解决的头疼问题.....我决定明天把他们都看一遍，再写一遍....最后后天再看看一些记得不太熟的数论和图论算法，还有(Extended)KMP等等.....看来我和SXY的差别还是很大的。
所以，我就要努力了......后天就走了，我心里还没底啊.....
我做SGU的题目，真的很搞笑。因为我看到的题目不是我想死也想不出来的，就是我一想就出来的，然后程序不是巨烦就是巨简单，都不想写。
然后做前几年的AHOI的题......简直是被虐啊......会写的还是会写，不会的还是不会......估计我去，能把所有简单题切掉就行了，我没有其他要求了.....最后拿个两三百分，也挺好.....
还有就是我这两天都是上火上到死啊....今天中午要睡午觉了，刚躺下就流鼻血了.....我发誓我没有在想什么邪恶的东西.....算算这都是这个星期第五回了吧。希望考试的时候不要弄出去年YK的事情，这哥们去年居然过马路的时候就流鼻血了.....
准备的时候才知道我还有很多东西不知道啊....比如差分约束系统....比如很多线段树的应用....比如一大堆动规题（什么1D/1D和四边形不等式).....再比如什么遗传算法啦，最小费用最大流啦，带上下界的最大流啦，比如最优二分图匹配啦，LCA和RMQ以及+-1RMQ啦，什么各种诡异的数据结构啦（话说我平衡树还不会写）什么状态压缩动规啦......一大堆要解决的头疼问题.....我决定明天把他们都看一遍，再写一遍....最后后天再看看一些记得不太熟的数论和图论算法，还有(Extended)KMP等等.....看来我和SXY的差别还是很大的。
所以，我就要努力了......后天就走了，我心里还没底啊.....
2009年4月4日星期六
高斯消元和初等行列变换
正在痛苦地准备AHOI.....不过我能不能去还是个问题。
上次的市选，我是满分，SXY满分，其他的人或多或少都有一些错，可能是大家都没怎么认真去考，所以就有点差吧。好多人都出了低级的错误，这让我们都很惊讶。
好，下面转入正题。
今天去做了AHOI2007的day1,题目难度还是有的。我要真去做.....50分。
第一题和第二题都是数学题....第三题我没敢看，估计我三个小时还不一定写的出来。
第一题估计是一道扩展欧几里德算法的应用，应该不难吧......但是我不会扩展欧几里德啊......今天晚上把它切掉。
第二题是这篇文章讨论的重点了：
题意就是求矩阵的逆，数学家可以不看了。
我上网查了半天，终于弄明白矩阵的逆是要用传说中的初等行变换求得....于是我又去查了半天初等行变换.....就本题来说，我想到的第一个算法极其愚昧:根据矩阵乘法，可以写出N组N个一组的N元一次方程，最后用高斯消元一个一个解掉.....O(n^4)......上网查半天之后，得出这个结论：这道题可以在原矩阵的右边再写一个I矩阵，然后用初等行变换同时对这两个矩阵进行操作,最后把原矩阵变换为I矩阵的时候，右边的I矩阵也变换为了原矩阵的逆.......好诡异......
但是我当时居然傻X的不会如何把原矩阵变换为I矩阵.........
于是又上网查......
最后在一个很牛的网站上查到了这个东西，看完我就一拍桌子站起来：靠，这不就是高斯消元吗？
所不同的就是在高斯消元的时候，我们是把系数矩阵化为一个上三角矩阵，然后再进行回带。而求矩阵的逆则是在化为上三角矩阵之后，继续使用行变换把上三角矩阵的上三角也给划掉，最后留一条对角线。
其实如果带上常数项，也同样进行行列变换的话，最后化出来的对角线矩阵所对的常数矩阵也就是方程的解了。
看来我的那本线性代数没好好看啊.....说的也是，我的《工科线性代数》放在家里已经一年了，我连10页都没翻到。
话说回来，搞OI的还真是痛苦.....还要学线性代数，组合数学，基础离散数学（数论和图论）,还有一大坨的东西，生物化学物理都不能差，阅读理解能力要好，否则题目都读不懂......英语要很不错，否则各大OJ上的题目你都不要想读懂......痛苦啊......
上次的市选，我是满分，SXY满分，其他的人或多或少都有一些错，可能是大家都没怎么认真去考，所以就有点差吧。好多人都出了低级的错误，这让我们都很惊讶。
好，下面转入正题。
今天去做了AHOI2007的day1,题目难度还是有的。我要真去做.....50分。
第一题和第二题都是数学题....第三题我没敢看，估计我三个小时还不一定写的出来。
第一题估计是一道扩展欧几里德算法的应用，应该不难吧......但是我不会扩展欧几里德啊......今天晚上把它切掉。
第二题是这篇文章讨论的重点了：
题意就是求矩阵的逆，数学家可以不看了。
我上网查了半天，终于弄明白矩阵的逆是要用传说中的初等行变换求得....于是我又去查了半天初等行变换.....就本题来说，我想到的第一个算法极其愚昧:根据矩阵乘法，可以写出N组N个一组的N元一次方程，最后用高斯消元一个一个解掉.....O(n^4)......上网查半天之后，得出这个结论：这道题可以在原矩阵的右边再写一个I矩阵，然后用初等行变换同时对这两个矩阵进行操作,最后把原矩阵变换为I矩阵的时候，右边的I矩阵也变换为了原矩阵的逆.......好诡异......
但是我当时居然傻X的不会如何把原矩阵变换为I矩阵.........
于是又上网查......
最后在一个很牛的网站上查到了这个东西，看完我就一拍桌子站起来：靠，这不就是高斯消元吗？
所不同的就是在高斯消元的时候，我们是把系数矩阵化为一个上三角矩阵，然后再进行回带。而求矩阵的逆则是在化为上三角矩阵之后，继续使用行变换把上三角矩阵的上三角也给划掉，最后留一条对角线。
其实如果带上常数项，也同样进行行列变换的话，最后化出来的对角线矩阵所对的常数矩阵也就是方程的解了。
看来我的那本线性代数没好好看啊.....说的也是，我的《工科线性代数》放在家里已经一年了，我连10页都没翻到。
话说回来，搞OI的还真是痛苦.....还要学线性代数，组合数学，基础离散数学（数论和图论）,还有一大坨的东西，生物化学物理都不能差，阅读理解能力要好，否则题目都读不懂......英语要很不错，否则各大OJ上的题目你都不要想读懂......痛苦啊......
2009年3月29日星期日
市选总结
嗯嗯，这是我第一次写这种东西.....
总结一下，这次讯飞杯，好象是第一次在一中办，而且是第一次在一中新校区办.....
比赛激烈程度不高，开场前我就和ZYF讲，这次估计是一中队内赛了......
结果果然，变成了队内赛。我旁边两位小哥连PASCAL都用的不熟,其实第一题就是考会不会编程的.......简单Ad hoc，没难度啊。
还有比赛之前进场的时候出现了一点小插曲：WTJ和YK两个这一届最强的男人居然坐在一块.....（当然是隔一个人）imba!难保他们两个比赛时不窥屏。
好了，废话不多说，我们来分析一下题目；
首先是第一题，Ad hoc，难度为零，会编程的人都会，就不讲了。
题目二,O(n)的算法要懂一点脑筋，我写的O(n)，估计很多人写的都是n^2级别的。同志们想想，1000的平方就是1E6，十万级别,最后一题的n^2我的程序都不能瞬秒，扩大100倍的运行时间估计1秒很难拿下......
其实o(n)就是开一个队列，队中元素就是所要累加的数，只要我发现队列中元素和大于n就让队首出队，和小于n就让下一个元素入队，保证了几乎没有冗余的循环，平摊分析应该是O(n)，没仔细想过。
题目三是一道怪难的数学题.......估计也是这次比赛难度系数最高的一题了，其实题目意思很简单，就是给你n个数，问有几种不同的不等关系。想一想，如果把所有的数从小到大排列，等于的放到一起：
{a1=a2=……=ai} {ai+1=……=aj} …… {ak=ak+1=……=an}
把所有的相同数都归到一个集合里，这个集合就是一种划分，再把集合全排列，就是这样划分集合所对应的不等关系数目。
估计看到这里大部分人都明白了，就是所有集合划分方式乘上个集合数目的全排列数嘛。把n个数划分为k个集合.......第二类stirling数.......全排列......阶乘.........相乘........高精度乘法......
题目四,有点小难度的DP，其实也简单，因为乘积末尾的0是乘积的因数中有多少个10决定的，而最少有多少个10又是由最少有多少个2或者5决定的，所以.......简单了吧.
好了，目前就分析到这里，其他的就等官方成绩出来以后再写上吧。
总结一下，这次讯飞杯，好象是第一次在一中办，而且是第一次在一中新校区办.....
比赛激烈程度不高，开场前我就和ZYF讲，这次估计是一中队内赛了......
结果果然，变成了队内赛。我旁边两位小哥连PASCAL都用的不熟,其实第一题就是考会不会编程的.......简单Ad hoc，没难度啊。
还有比赛之前进场的时候出现了一点小插曲：WTJ和YK两个这一届最强的男人居然坐在一块.....（当然是隔一个人）imba!难保他们两个比赛时不窥屏。
好了，废话不多说，我们来分析一下题目；
首先是第一题，Ad hoc，难度为零，会编程的人都会，就不讲了。
题目二,O(n)的算法要懂一点脑筋，我写的O(n)，估计很多人写的都是n^2级别的。同志们想想，1000的平方就是1E6，十万级别,最后一题的n^2我的程序都不能瞬秒，扩大100倍的运行时间估计1秒很难拿下......
其实o(n)就是开一个队列，队中元素就是所要累加的数，只要我发现队列中元素和大于n就让队首出队，和小于n就让下一个元素入队，保证了几乎没有冗余的循环，平摊分析应该是O(n)，没仔细想过。
题目三是一道怪难的数学题.......估计也是这次比赛难度系数最高的一题了，其实题目意思很简单，就是给你n个数，问有几种不同的不等关系。想一想，如果把所有的数从小到大排列，等于的放到一起：
{a1=a2=……=ai} {ai+1=……=aj} …… {ak=ak+1=……=an}
把所有的相同数都归到一个集合里，这个集合就是一种划分，再把集合全排列，就是这样划分集合所对应的不等关系数目。
估计看到这里大部分人都明白了，就是所有集合划分方式乘上个集合数目的全排列数嘛。把n个数划分为k个集合.......第二类stirling数.......全排列......阶乘.........相乘........高精度乘法......
题目四,有点小难度的DP，其实也简单，因为乘积末尾的0是乘积的因数中有多少个10决定的，而最少有多少个10又是由最少有多少个2或者5决定的，所以.......简单了吧.
好了，目前就分析到这里，其他的就等官方成绩出来以后再写上吧。
订阅：
博文 (Atom)
