新队员

  昨天看到一大坨人涌进实验室,心里居然莫名地高兴起来,实验室也第一次处于有人没凳子坐的囧境。尽管这群人将来是金是铁都跟我没多大关系,我也没多么伟大去指引他们走向光明。

  一直以来都很愿意帮助大一大二的进入实验室,一个是因为这是自己作为老队员所能做出的贡献,更重要的是,我认为所有人都应该有机会来感受这比赛的魅力,而不应该卡在人为因素上而接触不了。

  这才是ACM。

Posted in 未分类 | 2 Comments

bug?

居然能访问了  8O

Posted in 未分类 | Leave a comment

合肥Regional小结

  话说,在出发去合肥的时候SYL做了个邪有暗香盈袖恶的梦,梦见我们队在合肥一行中夺得金牌倒数第一。要知道XDU至今还没拿过Regional的金牌,所以我们也没往这方面多想,还担心会不会因此掉不少RP而延续去年一队的悲剧拿到铜牌第一,狂骂了他一顿,因为梦往往是和现实相反的。。。

  10.8号早上离校。为了攒RP我特地加了Lost神牛的QQ(看到了他邪有暗香盈袖恶的头像)、在老校区打印时丢了U盘(这个不是特意的-_-)、忘了带身份证(幸好在合肥没有需要证件的地方)等。

  接下来是漫长的汽车、漫长的火车、漫长的汽车——可惜没有MM,只是四个男人的故事……让我们跳过这一段

  合肥不是一个发达的城市,经济貌似比西安差点,但感觉比西安整洁多了~不过也没什么地方好逛的,去李鸿章故居外面转了下,由于对李鸿章没有什么爱好最终还是没有进去看看。据去年一些合肥参赛队员说,合肥就是平淡、乏味看来不假。

  热身赛相当轻松,第一题是求线段经过的格子数,随便YY了下公式就上去写了,由于以为是文件输入输出贡献了一个WA,去掉文件输入输出返回Yes。第二题是一个简单的状态集合dp,想清楚后很快写完,马上返回一个Yes,延续了我状态集合dp 1Y的高RP。第三题是一个树同构,只不过多了一条非树边,想了下想出了一种枚举环上点Hash的方法,但一想到代码可能会比较长就不想上去写了- -。这时看了下周围的气球,出两个题的队伍还不是很多,突然觉得这个Regional也许不像传说中那样大牛众多,YY了下明天的比赛。然后就是无聊的调戏Judge时间,没事print下代码,提交各种诡异代码,发现弄不出来PE,而且同一个代码有时返回WA有时返回RE。

  晚上看了下芒果台的娱乐节目——就是那么娱乐,另外还上群水了下,顺便想了下今天A题的公式,感觉有点容斥的味道。明天的比赛是8:30,很诡异的时间,搞不懂为什么这么早。由于害怕会在床上失眠我也没那么早睡,一直到12点多有了睡意才睡,然后一觉到天亮~

  11号早上被酒店的电话闹铃服务给吵醒 :x ,随便收拾下吃下早餐就走人——这里不得不说下酒店的早餐是那么难吃……进场后主办方居然让我们熟悉下机器,有点意外,于是我上去打了下vim的配置,打开NetBeans,居然忘了新建一个Java项目(主要是这机器新建一个Java项目居然需要一两分钟= =)。

  比赛开始了,老规矩读题。这时我发现B题居然是判断一个数是否是梅森素数,看了下范围决定用Java水过,于是新建Java项目,经过一两分钟的等待我开始敲,不一会就敲完了,这时犹豫了一下要不要打表,而且这时看没人过B题有点害怕,再看了遍题目,还是决定交了上去。

  在等待返回结果的时候和队友讨论了已经很多人过的D题,居然是昨天热身题A题的三维情况,经过昨晚的思考我很快用容斥想出个公式,上去敲。这时B题返回Yes增加了我不少信心,不一会也把D题写完,测试了一些数据没问题,也交了,这次很快返回Yes。7分钟B题1Y,15分钟D题1Y,这让我有一种做梦的感觉- -

  接下来是E题,一看是个自动机,我上去敲了自动机的模板,不一会也敲完了,但这时我发现有点问题,再次分析下了,觉得那复杂度用字典树暴力就可以过,改了下,期间问了下Judge有没有内存限制。在35分钟的时候坐在我们前面的SCAU_Arctic就已经把E题过了,仰慕下~我想我还是有点紧张,这题居然写了40分钟,期间debug了不久,在60分钟的时候提交,返回Yes,又是一个沾满RP的1Y!这时wudired说他那一刻想到了哈尔滨- -

  G题是个博弈,wudired的强项,就让他上去敲了。wm给我讲了下J题的题意,这时悲剧出现了,我理解错了题意,然后想了很久一点思路都没有,转而看F题。F题是个字符串,但总感觉它不是用字符串的知识来解决的,我想了下线性扫描的方法,也没什么收获。

  wudired写完G题,但发现样例不对,下来跟wm讨论,我上去打了个SA的模板,觉得F题可能用得着。后来wudired明确了算法,但dp部分有点问题,跟我讨论了下,我发现是个简单的背包,但范围无法接受,这时他也发现范围有误,新复杂度刚刚好,我跟他讲思路让他继续敲,折腾了很久要提交时我改正了一些溢出问题,提交并返回Yes~在223分钟又是一个1Y~但这时候形势不是很乐观,因为这题用了太多时间而剩下的时间已经不多。我看了下board,发现A题出的人比较多,于是决定写A。

  A题是个麻烦题,算法很显然,O(n^2)的枚举,但不好写。这时我做了个不是很明智的决定,让wudired来写,wm看着,我出数据。现在想想应该是我这个主敲来写这种麻烦题,然后wudired看着,wm出数据。这题一直到比赛结束都没写完,也许,XDU_maybe就这样和WF擦肩而过了。

  封榜是12名,封榜后貌似其它队出的气球也不多。银牌应该是没问题了,但金牌……这时还听到一个消息,说J题Rejudge了,有一些队Rejudge后过了J题,觉得跟金牌是无缘了,是银倒无所谓,但不要是银牌第一……

  好不容易熬到了晚上颁奖,无意间坐在了一个记者的前面,无意间发现她有一份排名表,发现是——

  第9名,金牌!

  得知金牌后的情形我就不说了,大家发挥想象力YY下吧。坐我们前面的SCAU_Arctic拿到银牌,有点郁闷,据说是A题一个函数返回错。FZU_AcOrz在封榜前绝杀,拿到了银牌,其实我觉得如果不是他们发挥不好今晚拿金牌的就不是我们而是他们了。CUGB_newHope也是银牌,祝贺下他们~另外Bless下CCNU,期待下一场的爆发~

  现在想起来,我们队有很多缺陷在这场Regional暴露无遗,比如没法连续出题、思维不够深、状态不稳键等,以我们队的实力是完全有可能出5个题的。但我们队也是幸运的,能够拿到XDU的第一枚Regional金牌,感谢大家对我们的支持~

  Bless XDU_maybe @Shanghai~

Posted in 未分类 | 12 Comments

Baby-step giant-step

不知道为什么这算法会有这么诡异的名字,比“舞蹈链”(Dancing link)还诡异。但话说回来,这算法确实是我数论学习上的Baby-step giant-step,另外发现自己似乎很久没写月志了,就写篇纪念下吧~(其实算是Wikipedia上这篇文章的简单翻译-_-b)

  众所周知,[tex]a^b \equiv c \pmod m[/tex]式中已知a、b、m求c很方便,用快速模取幕可以在[tex]O(\log_2 m)[/tex]的时间复杂度求出来。但如果已知a、c、m求b就不是那么容易求了,简单地枚举需要[tex]O(m)[/tex]的时间,但在竞赛中这时间复杂度基本不可能通过。而Baby-step giant-step算法利用[tex]b=in+j \,,n=\lceil \sqrt{m} \rceil \,,0 \leq i < m \,,0 \leq j < m[/tex]把[tex]a^b \equiv c \pmod m[/tex]转化为[tex]c(a^{-n})^i \equiv a^j \pmod m[/tex],利用Hash(或者二分查找)很强势地使时间复杂度降到了[tex]O(\sqrt m)[/tex],这种时间复杂度下对于[tex]m<2^{32}[/tex]的数据范围来说是绰绰有余的。下面就来介绍下这种神奇又简单的算法(如果m是个合数的话还有一种更快的算法叫Pohlig-Hellman algorithm,大致思路是把合数分解再用中国剩余定理合并起来,本文不作讨论):

  1. 令n=ceil([tex]\sqrt m[/tex])
  2. for j=0 to n-1
      计算出每一对(j,[tex]a^j[/tex])保存在Hash表里
  3. 计算出am满足[tex]a^{-n} \equiv am \pmod m[/tex]
  4. t=c
  5. for i=0 to n-1
      检查t是否在Hash表里,如果在就返回i*n+j,如果不在t=t*am

  算法的大致结构是这样,但有个小问题,就是第3步计算am:如果m是质数的话,自然是[tex]a^{-n} \equiv a^{m-n-1} \pmod m[/tex],但如果m不是质数就得用扩展的欧几里德来算,比较麻烦。这里可以改成b=in-j,于是原式可以转化为[tex]a^{in} \equiv ca^j \pmod m[/tex],这样在第3步就简单多了,直接快速模取幕就行。

  很抱歉写了个错误的方法。。。

Posted in 学习笔记 | Tagged , | 4 Comments

保佑保佑区域赛不要像昨天那样的发挥,保佑保佑区域赛前一天不要像前天那样RP爆发
不对,我是要当职业选手的,而不是这种状态选手,怎么可以被RP影响?
不YY了,不发泄了
虽然现在实力不行,但是
我会带两个J8队友走上光荣的、伟大的、一路草泥马狂注视的幸福之路的
PS:给我十天时间,让我把信号+数电+模电AK了

Posted in 生活 | 7 Comments

暂别

  我想我已经过了学习最迅速的阶段——确切说是早就过了,接下来应该就是不管怎么学都感觉不出自己有什么进步那种阶段,这阶段无疑是最痛苦和迷茫的。再加上上个月做比赛做到烦,我想我是时候离开下,做点其它的事。
  顺便,日子快到了,缅怀下我出生那年的志士们。

Posted in 生活 | 1 Comment

Contest@MAY 09

5.1 topcoder SRM439
  算是开始适应Topcoder的模式,这次终于不再掉Rating,颜色变绿,也开始学会cha别人~
5.2 nuaa
  南航的比赛真的很囧,很有马拉松的风范。刚好五一期间没事干,就全A了,还从来没拿过Rank 1呢…
5.3 zju 浙大月赛
  这次月赛居然出人意料地水,我们差一分钟就全A了!主要对那道概率题太没信心而且也对概率题没什么经验,刚开始一直在浪费时间找公式,后来用很暴力的方法去模拟,可惜改正最后一个bug后交上去已经out of contest time几十秒了,囧。这次跟sweat配合得还行,比较互补,两道较难的题都被他切了,膜拜下~
  Final Standing: Rank 15(不过说实话两个人组队参加月赛有点赖,而且貌似超级大牛也没几个参加…)
5.9 tic 腾讯什么tic大赛初赛
  题目都比较水,但我5个只A了3个,貌似我一到这种大赛都会状态掉很多,唉,心态还是不行。
5.12(祝福汶川人民) topcoder SRM440
  基本维持上一场的状态,但500分写慢又写残了,re-submit了一下,结果这题大概少别人100分。更脑残的是居然无视时间复杂度交了个暴力的1000分,一下子被人cha掉-_-…
5.16 tic 腾讯什么tic大赛复赛
  很意外还能进复赛,但还是延续了上一场的颓势,只A了一个题,没什么好说的,实力,及心态。
5.17 pku 北大09校赛
  感觉这场比赛偏重数学、思维而不重算法。很高兴handacher和sweat跟我组队了~两个简单题都水得很没水平,WA了几次。简单题完了就卡住了,我决定看一题当时只有5个人做出来的题(现在那题已经快沦落为水题了…),可能是补偿昨天低迷的RP吧,这题居然被我敲过了…但接下来handacher和sweat都被另一个题卡住了,我想我那时是有点得意不想再比下去了,而且他们也说算法应该对着我也没去插手他们那个题,自己找其他题看去。赛后才知道是算法错了,我想我仔细去看那个题也许会有点转机…唉,策略出错。
  Final Standing: Rank 35(如果把那个题也过了就能进前20了)
5.23 zju 浙江省第六届大学生程序设计竞赛
  本来想速秒A题的,但居然因为题意说得有点模糊(也可能是我考虑太多)贡献了一个WA(囧,开门绿啊),写J题时居然因为数组开小、输入出错连WA两次,很郁闷的开局~水题写完了开始写次水题,B题推公式推了很久很烦,直接写个二分居然1Y,以前这种有精度的题都会WA好几次今天居然RP爆发?C题是个最小生成树但我做的时候好像没几个人写,怕怕的,仔细想了一下用不到十分钟把它也1Y了~这时候排名居然已经相当靠前了,貌似是前三,不由得有点兴奋了——我是菜鸟,没见过大场面-_-b,这时候剩下几个题都有点麻烦,D题看起来就不想看下去,E是图论,handacher说他要做就给他了,G是计算几何,有点思路但怎么判断Observer被完全挡住视线有点麻烦,也很少写计算几何所以先不写它,因此只剩下H了。H刚开始一直在想DP,又想烦了,直接写个状态压缩BFS,居然也1Y了(今天真的是人品严重爆发了!)~接下来——好吧,我承认接下来一个半小时什么题都看不下去聊天去了,貌似兴奋过度。。。去看看handacher写E题,修改了几个问题,还幻想着如果AC了可以进入前三名,但一直没什么进展,就这么拖到比赛结束。现在想想这场比赛又有点遗憾,一是D题有好几个人过了,可见不是什么很难的题,我有一个半小时的时间完全可以试下的;一是或许我应该也写下E题,这种麻烦题我更有把握。唉,可能最近比赛太多写烦了……
  Final Standing: Rank 5(今天罚时控制得比较漂亮——至少比以前好多了,算是进步吧)
5.24 tju 川大校赛
  我只能说,组合数学真多……今天RP低迷现出了原形。开局10分钟1Y E题,但好像开局比较好到后面都会RP不行,今天果然这样了,J题贯穿了整场比赛,一共贡献了17次WA。。。A题比较水但我居然用了近半个小时来写它;K题也差不多但我理解错题意两次,重写了三次代码;C题刚想出DP方程(刚开始想歪了)就被wudired抢了并贡献一次TLE--居然不打表;G题用二分又写挂一次,调试代码似乎太久了,现场赛可不能这样;D题是最后半小时看的,想出方法后居然不知道怎么求[tex]C^m_n[/tex],到最后才恍然大悟要质因分解。。。
  Final Standing: Rank 6(罚时罚时。。。做的人不多,这样的排名不算什么)
5.27 topcoder SRM441
  250分轻松写完,拿了230+,500分貌似也不是很难,写了几行代码搞定,最后总分有600+。接下来看1000分,感觉是贪心但由于以前1000经常所cha所以不敢写了,直接放弃(虽然还有半个多小时的时间……)。回去看看500分的,发现一个比较囧的Bug,re-submit了下,一下子总分从600+掉到400分……这时感觉没什么Bug了就跟人聊天去(-_-b),结果在最后因为return时溢出在System Test挂掉了。想到自己cha别人的溢出cha得那么爽最后居然自己也阴沟里翻船了,囧。最后rating只涨了40,在这一局变蓝的梦想破灭了……
5.30 fzu 福大月赛
  对自己的1Y率还比较满意——虽然题目比较简单,不过B题WA两次很囧,仅仅只是因为没初始化,由于这题比较烦杂我光检查变量常量有没有写错了。很郁闷的是由于对剩下两题没什么想法了我就玩B题那个游戏去,结果比赛结束后才听wzc说剩下那两个题有一个可以很暴力地过,晕了。
  Final Standing: Rank 6
5.30~5.31 baidu 百度之星初赛
  题目真恶心,好吧,我放弃,游泳去~。
5.31 网易&topcoder 有道难题初赛
  水题赛,但需要细心点。这次写得很慢,测试了很多数据,虽然分数低点但比较稳定,毕竟初赛能过那么多人而且分高好像也没什么用。今天看了下,两个题都Passed,看来是进复赛了~

Posted in 生活 | Tagged | 7 Comments

pku3469 Dual Core CPU

很久没贴代码了~

写这个题主要是为了练习ISAP(可能更多人叫SAP),ISAP实现起来不算太复杂,只是写的时候大意了把GAP优化写残废了,TLE很久,这也说明GAP是ISAP不可缺的优化~
Continue reading

Posted in 解题报告 | Tagged , | 2 Comments

USACO 09MAR月赛

  第二次参加USACO的月赛,但这次题目做起来远没上次做铜组踏实——题目也太水了吧,还是我算法错了:sandcas貌似是贪心,心里其实没底,但暂时想不出贪心反例;fristeam是DP,怕在边界出现问题;lookup二分,但用二叉树来实现写得不是很好,有超时的可能。想弄数据来测试又懒得弄,现在半夜又没人能讨论,被TopCoder打击了好几次,现在写题都没什么信心……算了,不就是一次USACO月赛,WA了就WA了,还是睡觉去,留点精力给其它事~

Posted in 生活 | Tagged , | Leave a comment

Debian 5.0 Lenny安装配置笔记

  由于机子上的Ubuntu 8.04已经被我折磨得不成样了,而且也实在看不惯Ubuntu那默认的土黄色,想换个新套件试试,刚好Debian也发布了最新的稳定版,看起来还不错。于是,我开始了我漫长的Debian之旅~

  Debian是一个基于deb包以稳定著称的Linux套件,据说就连testing(测试版)甚至是unstable(测试版的测试版)都要比一些正式版套件要稳定,不过为了稳定其stable(正式版)所包含的软件一般都比较旧。而我现在也没什么兴趣去试用各种最新的软件,我只需要一个比较稳定的环境来让我写代码和处理一些日常事务,Debian这种特性算是挺适合我的。不过Debian的安装配置显然没有Ubuntu那么方便,我安装Ubuntu时安完可用、立等可取,而Debian就让我实在头大,不然我也不会写这篇日志--主要是为了以后安装时有个参考,其次也是为了发泄心中的郁闷 :evil: ……

  • 下载安装映像

  好了,进入正题。首先是下载ISO。官网上说获得Debian有四种方法,一是下载一个叫netinst.iso的小型映象文件来安装,这映象文件只包含一个基本的系统和很少的软件包,安装时会联网下载更多软件包来安装(其实也可以不联网,不过安装完后只是一个很基本的系统,没有X Window什么的);第二是下载很多很多的的CD/DVD映象文件,大概要20G吧,如果网络下载速度比较抽风比较中国特色就别全下了,下第一个就行;第三是买Debian光盘,如果有的话那确实不错;第四是买预装Debian的电脑-_-b,这我就不想说啥了,很多官网向来都是很抽风的。我下的是netinst,只是觉得为了那一百多M的东西去刻一张CD-R很奢侈。

  • 安装时无法使用无线网络

  由于用netinst安装,安装时候需要联网,我用的又是无线网络,这时候麻烦来了:安装的时候能识别出我的Intel 3945无线网卡,但缺少一个non-free的firmware,要我放在U盘之类的东西并连接电脑。 我于是照办,而且无线网卡似乎也成功驱动了--笔记本上的无线网卡指示灯亮了,但就是死活搜不到AP,手动输入AP的SSID和IP地址什么的好像也不行,莫非是个Bug,还是我哪步出现问题了,反复尝试无果,只得乖乖去买根网线来用有线网络安装。

  • 源的选择

  安装过程没什么大的疑问,源选的是美国的源,速度也不是慢到不可接受,后来用apt-spy试了下,台湾源貌似也挺快的,下回就用它了。不知道什么时候才能有稳定的国内源,怀念用cn99的日子。。。

  • 中文字体

  安装后重启,看到GNOME界面我郁闷了,居然是用楷体来做系统的默认字体,我只能说Debian在中文化这方面严重抽风了。我的解决方法先装个文泉驿正黑字体(感觉差Vista下的微软雅黑很多,可能是X下字体的渲染问题吧),root权限下apt-get install ttf-wqy-zenhei,再修改/etc/fonts/local.conf(刚装好的系统一般是不会有这个的,自己创建)如下:

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>

<alias>
<family>serif</family>
<prefer>
<family>Liberation Serif</family>
<family>DejaVu Serif</family>
<family>WenQuanYi Zen Hei</family>
</prefer>
</alias>

<alias>
<family>sans-serif</family>
<prefer>
<family>Liberation Sans</family>
<family>DejaVu Sans</family>
<family>WenQuanYi Zen Hei</family>
</prefer>
</alias>

<alias>
<family>monospace</family>
<prefer>
<family>Liberation Mono</family>
<family>DejaVu Sans Mono</family>
<family>WenQuanYi Zen Hei</family>
</prefer>
</alias>

<match target="pattern">
<test name="family" >
<string>serif</string>
</test>
<edit name="family" mode="prepend" binding="strong">
<string>Liberation Serif</string>
</edit>
</match>

<match target="pattern">
<test name="family" >
<string>sans-serif</string>
</test>
<edit name="family" mode="prepend" binding="strong">
<string>Liberation Sans</string>
</edit>
</match>

<match target="pattern">
<test name="family" >
<string>monospace</string>
</test>
<edit name="family" mode="prepend" binding="strong">
<string>Liberation Mono</string>
</edit>
</match>

<match target="font">
<test qual="any" name="family">
<string>WenQuanYi Zen Hei</string>
<string>文泉驿正黑</string>
<string>文泉驛正黑</string>
</test>
<test compare="more_eq" name="pixelsize"><double>13.5</double></test>
<test compare="less" name="pixelsize"><double>14.5</double></test>
<edit name="pixelsize"><double>13</double></edit>
</match>

<match target="font">
<test qual="any" name="family">
<string>WenQuanYi Zen Hei</string>
<string>文泉驿正黑</string>
<string>文泉驛正黑</string>
</test>
<test compare="more_eq" name="pixelsize"><double>11.5</double></test>
<test compare="less" name="pixelsize"><double>14.5</double></test>
<edit name="antialias" mode="assign"><bool>false</bool></edit>
<edit name="embeddedbitmap" mode="assign"><bool>true</bool></edit>
<edit name="hinting" mode="assign"><bool>false</bool></edit>
</match>

</fontconfig>

  我把文泉驿正黑设为系统默认中文字体。由于个人不喜欢太小号的中文矢量字体,看起来很模糊,所以把中文小号字体改为点阵字体。

  • Intel 3945ABG无线网卡

  前面说到,安装的时候无线网络没法用只能用有线网络,现在安装完以后无线网卡还是没法用。这个解决起来比较简单,去这个网站下个firmware,解压后把里面那个iwlwifi-3945-1.ucode文件放在/usr/lib/hotplug/firmware/下,然后重新挂载iwl3945模块就行了:

modprobe -r iwl3945
modprobe iwl3945

  • 无线网卡指示灯

  相信很多笔记本都会有这玩意,用来指示无线网卡的状态。以前用Ubuntu 8.04的时候我笔记本的无线网卡指示灯一直都是暗的,驱动不起来,想去研究怎么把它弄亮但又懒得去弄,因为不亮就不亮,又不碍事。现在用Debian,它终于亮起来了,但问题是,它是一闪一闪地亮起来了,一有网络传输就闪,这么刺眼的东西还不如不要。后果费了一些时间,在老外的网站找到解决方法(国内的Debian社区远不如Ubuntu),在/etc/network/if-up.d/下新建个脚本文件no-blink(喜欢叫什么名就叫什么名,但最好别中文名),内容如下

#!/bin/sh
if [ "$IFACE" = "wlan0" ]; then
    for dir in /sys/class/leds/iwl-phy*X; do
        echo none > $dir/trigger
    done
fi

  注意,记得给脚本文件加可执行权限,即chmod -x no-blink,我刚开始就是因为忘了加浪费了很多时间。。。

挂载NTFS/FAT32分区

  修改/etc/fstab,依样画葫芦了:先用fdisk -l看看哪个是NTFS/FAT32分区,再为各个分区新建个文件夹,把它们的路径都写进fstab,type是ntfs或vfat,options为user,uid=1000,noauto(如果想开机挂载就别写noauto了),保存好就可以直接在位置->计算机里面双击挂载。

Posted in 学习笔记 | Tagged , | 2 Comments