CTSC2014题目的各种乱搞方法 && 感想

Posted on 2014-04-30 23:25 Mato_No1 阅读(2965) 评论(7)  编辑 收藏 引用 所属分类: CTSC
@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); Day1 random:
首先基本方法是矩乘……xor可以转化为mod 2意义下的加法操作……
直接矩乘O(N3logK),需要优化……
由于mod 2,矩阵中所有的元素都是0或1,于是可以压位,设压w位,则时间复杂度变为O(N3logK/w)……
其实还可以继续优化。
在mod 2意义下,乘法相当于and,加法相当于xor……假设某次待乘的两个N*N矩阵分别为A和B……
先对A的每一行进行分段,每w位一段,然后这一段在进行矩乘的时候,实际上是对B的每个w*32的块,都将该块对应的若干行(这一段值为1的位置对应的那些行)取出并整体xor……
因此可以一开始就对B进行分块,每块大小为w*32,每块计算出对于每个w位二进制数对应行的xor和……
这样两个矩阵相乘的总时间就是O(N3/w/32)了囧……(A中一共N2/w段,每段在B中乘N/32块,每段和每块的相乘结果可以直接在预处理记录的xor和里面调,是O(1)的)
预处理时间显然是O(N2/w/32*2w),w=logN时两者平衡……
这样很明显可以卡过去N=1000,K=109的那些点(w取10),N=2000的或许也可以卡过去囧……

Day2 crypto:
N=50的,由于p大,直接随机53~58个方程,解方程组,有解的就认为是答案囧……
N=60的,基本思想是通过碰撞(两个方程xor)消去某些未知数,然后当未知数个数较小时暴力枚举验证……
@fanhq666 在讲题的时候,说进行两轮碰撞,第一轮消去第41~60个未知数,第二轮消去第21~40个,然后暴枚……
优化:这样在两轮之后其实是对4个方程合并后的结果,正确率严重降低,可以直接取3个方程碰撞消去40个(也可能>40个,减少枚举量)未知数,这样正确率就木有那么惨不忍睹了囧……

Day2 numbers:
基本方法:手打前若干个数字,后面的进行比对,选那个最像的(其实这样正确率并不能达到最高,可以取前10像的,看哪个数字最多,或者加入其它的一些估价……)
这样正确率可以达到约0.9……
为了进一步提高正确率,可以找出那些出错的数字,看都是将什么判成了什么……
结果是,4和9、7和9、3和5、某些1和8、某些1和2等易出错……
因此可以针对这些继续优化……比如对4和9设计更精细的估价函数,按每列拆分,可以确定上方的开口大小,然后取开口前若干小的为9,其它为4……

(未完待续)
———————————————————————————————————————————————————
一些感想:

我的OI生涯就这么结束了……
没能参加IOI,真的很遗憾……
但是像我这样的沙茶,除了提交答案和某些乱搞题外几乎木有任何优势,要是进了队,很明显是给中国丢脸啊囧……

CTSC的这几天,我和HN、ZJ的神犇进行了充分细致的交流……毕竟这是大学前最后一次和他们见面的机会了……
从这个交流当中感受到了很多东西……
首先当然是和他们讨论各种问题的过程中,他们告诉我的那些新思想和新方法……当然在他们的论文中也有体现……
真是太神了……我为什么就一直没想起来这些呢囧……
还有就是他们在一起讨论问题时的热烈的场景……原来那些新思想都是在这里出现的,只要一人想出来,大家都知道了囧……
想起我平时有多么孤独……这样的场景只能在比赛时经历……
众多神犇在一起,每人都可以从别人那里获得动力,以及获得各种有用的资料……
而我这样的沙茶,本来就很弱,被神犇们鄙视,又木有好的资料来源,自然也缺乏动力了……

这些因素加在一起的效果,就是我进步的速度明显比他们慢,明显跟不上时代……
回想起从2008年7月以来的这些日子……
前两年不用说了,学习的都是最基础的东西(这些东西在强省都是几个月解决的事,而我用了两年,已经明显落后)……
后面,虽然各位神犇给我提供了一些榜样作用,但是这种作用效果还是太差……
我仍然需要几乎完全靠自己的努力来解决那些巨可怕的问题……
当2011年LCT、各种分块开始烂大街的时候,我还在写线段树、splay tree的模板……
当2012年SAM出现的时候,我还在写一般的SA……
当2013年cdq-gyz分治等各种诡异的思想出现的时候,我还在写动态树的模板……
总是跟不上时代,以至于我相对于其他人变得越来越弱……
用比他们更多的时间,收益却远远小于他们……
每一次听到一道题是ZJ、HN等的资料题、模拟赛题等原题时,就有一种想哭的冲动……

我曾经不止一次地想过,假如我生在ZJ或HN,或者小时候转移到了那里……
这几年的生活会肿么样呢……现在会是什么样呢囧……
不用为了需要一篇论文或者一道题,在google、baidu、citeseerx等上面到处找,找了很久无果……
不用在看知识点或题解时,面对无论如何也搞不懂的部分,急得想撞墙,也木有用……
不用为了一道难题的解决折腾几天,可能几分钟讨论一下就完事了……
不会在比赛后讨论时,别人说到一种很熟悉的方法,自己却从未想到过也从未听说过……
不会每天都在痛苦中度过,却一直跟不上时代,越来越弱……
弱省之所以弱,也就是因为这些原因吧囧……
(听说AH已经连续6年无国家队了,各科国家队都木有……这不奇特,看看AH这环境,将来要有,只能说那个人太高能了囧……至少现在还木有这么神的人……)
当然,我不能改变自己所处的环境,只能在这种环境下选择尽可能优的行动……

我希望能有一个更加精彩的人类智慧时代……

cong 国家队:一出现就能使人吓傻的鼎爷、xyz大爷;压位帝+乱搞帝+人类智慧之神 sy菊苣;几何帝花神。
今年中国队应该可以延续辉煌了囧……
Orz @法法塔 @vfleaking @matthew99等神犇

Feedback

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-05-01 09:57 by erks
单兵作战不是蛮有意思么,相比之下国家队什么的根本不重要吧

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-05-02 10:48 by Mato_No1
@erks
确实有意思,可以保留独立思考的能力,避免让我的大脑变成别人思想的特定容器……
但是这样效率太低了囧……
这么多年过去了,我还是这么弱的沙茶,总是远远落后于ZJ、HN的神犇,就是因为他们的前沿成果,我总是要经过很长时间才能了解……光靠自己想是不能想出很多东西的囧……
另外就是在被某些难题虐以及进行某些研究的时候,木有人帮助会很慢的……比如这次我写论文就用了近一个月,@法法塔 两天搞定……

国家队在某种意义上可能不重要,但是想起我这么弱,以后也会落后于别人,真是无比的忧伤……

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-05-12 11:46 by matthew99
又被D了。。。。。。

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-05-12 22:46 by 486326
orz六年oi神犇,高一开始接触oi的不用考就可以滚粗了

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-05-13 21:05 by Hed
请问一下您论文的大体思想是什么?看了之后感觉有些懵。。。

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-06-06 20:54 by 武弘勋
求神犇的学习经验分享呢。如何才能在弱省高效学习oi呢……(起步本来就比强省晚了……现在自己又还有一年就要中考了……唉)
还有,现在有的时候有问题没法儿和同学讨论真的很难受。


P.S. (期盼什么时候能和神犇见上一面呢……)

# re: CTSC2014题目的各种乱搞方法 && 感想  回复  更多评论   

2014-07-08 15:29 by test
1.如果生在zj可能省队都进不了
2.您不愿意带当然几年都不会出国家队

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理