2008年过的轰轰烈烈而凄凄惨惨, 所以过去就过去吧.
收获很零碎, 所以找不到最大的; 遗憾能找到最大的, 超囧的noi2008, 唉..不多说它了. 让我们展望noi2009吧.
2008年的最后一天, 做了一件很有意义的事, 尽管事情没有像自己想像的那样发生, 但至少心愿达成…一半.
所以说, 无论怎么样的失败, 怎么样的成功, 过去了就过去了, 真正每天影响自己的, 还是那些很平常很平常的每天都在的人, 每天都在的事.
希望大家2009年, 不好的好起来, 好的继续好下去, 快乐, 幸福!
最后, 今天是我16岁的最后一天.
Saw系列 剧透警告, 小心进入. 剧透警告, 小心进入. 剧透警告, 小心进入.
Saw系列 剧透警告, 小心进入. 剧透警告, 小心进入. 剧透警告, 小心进入.
Saw系列 剧透警告, 小心进入. 剧透警告, 小心进入. 剧透警告, 小心进入.
题目 1: treat
最简单的一道题. 每个点都只有一个出度, 因此我们可以从任意点起, 把沿途每一个点的答案都算出来. 具体的说, 分成支路和环两种情况计算路径上点的答案, 支路上的点的答案为到环路的距离加上环的长度, 环路上的点的答案为环的长度. 每次从未被算出的点k开始访问路径, 一旦进入某个已经计算过的点, 则从这个点走起遇到的环肯定不包含k( 否则k应该早就被算出来了 ), 答案就是k到该点的距离加上该点到环的距离.
题目 2: sec
使用类似后缀树的结构就可以了. 不断插入01串, 并统计最多相同前缀. 以0110为例, 从根结点起, 进入0这个孩子, 结点中的count加1, 就得到了第一位匹配的单词个数, 再进入这个孩子的1这个孩子, 以此类推, 得到前两位匹配的单词个数. 想到就很好写了.
查看更多 »
一个月没有写日志了. 感觉好像也没有发生什么. 每天也就上课, 做oj, 整理2008年省队训练时的那些题. 很是单调的日子. 升级至wordpress 2.7, 后台变动很大, 看着很舒服!
今天是彤生日, 兼南京大屠杀纪念日, 但我发现我们班同学大多只记得今天是彤生日, 之后才勉强感觉今天好像是什么纪念日.. 生日快乐!
一天比一天冷, 但还是常常晚上走回家, 见证着乌鲁木齐的空气越来越来差, 报纸说今晚有流星雨, 问题是我连月亮都看不见了..
看书看的倒是比较勤快, 晚上不睡觉, 打开阅读灯看啊看, 看到灯都没关就睡着了. 平板阅读灯真的很省电, 至少这么浪费都没换过电池, 但完全没必要压书上, 放书旁边就已经很亮了.. 有几天看那本关于linux命令和编辑器的书, 有几天看什么是数学, 有几天看三毛的书, 还没有哪本书从头到尾看完.. 值得一提的是三毛的<哭泣的骆驼>, 的确是一本看了比较紧张比较难受的书. 发现看书看到睡着特容易做梦, 一做就是和老师吵架的, 连着几天吵, 基本所有老师都吵了一遍. 我可能现实中太压抑了, 然后梦里发泄一下..
接着就是标题中所写的 — 猫! 楼下院子里那只猫某天跑到我家里来了. 他不是一只野猫, 特别温顺, 估计是被院子里某个人家抛弃了. 我们家在21楼, 他是从楼梯间爬上来的, 好有毅力..
给他吃了一些肉和饼干什么的, “内阁”不让在家里养他, 于是就又把他放回楼梯间了. 之后就再没爬上来过. 或许主人良心发现, 又把他抱回去了吧!
题目 1: 混乱的奶牛
最简单的题目. 我采用记忆化搜索. search ( bit, k )中bit表示将剩余的奶牛用1表示压成的二进制串, k表示此次搜索从第k头奶牛开始. 则答案就是所有的i满足i与k会造成”混乱”, sum ( search( bit^(1<<(k-1)), i ) ).
题目 2: 安慰奶牛
不太容易发现的最小生成树问题. 如果将生成树中的某一结点作为休息点, 则设n(k)表示第k个结点的度数, 根需访问n(root)+1遍, 其他结点访问n(k)遍, 因为每从一条边进入该结点总需要”交流”一次, 而根需要多访问一次, 而每条边需要走两次( 从父亲下去一次, 从孩子回来一次 ). 所以总代价S = 2 * ( L_1 + L_2 + L_3 + … + L_n-1 ) + ( n(1)*c_1 + n(2)*c_2 + … + n(n)*c_n ) + c_root. 我们可以把每条边的权值修改为 2*L_i+c(s)+c(e), 这样上式就变为S= L_1′ + L_2′ + L_3′ + … + L_n-1′ + c_root. 因此最后的答案就是最小生成树的总权值加上最小的c_i值.
noip2008就这样转眼结束了. 我继续2008年rp游离于自己的控制之外的悲惨境地, 第一题忘记在素数判断时给0加特判, wa一个点, 没有拿到人人应拿330分, 以320分结束了有可能是我最后一次的noip. 第四题估计花费了出题者很多心思, 直接导致前三道很水, 而且到现在为止, 我还不知道第四题的正确算法是什么. ( sqybi的blog上倒是有一个, 但还没有仔细研究. ) 我先稍微补一下最近落下的作业, 然后仔细计划一下如何防止明年noi挂的和今年一样惨, 接着落实计划, over. 再发点感慨, 昨天是我帮着在arbiter下测选手程序. 我之前就发现arbiter超”强大”, 昨天更是深有体会: 一场比赛关了后再打开, 成绩就不见了, 按保存也没用; 编译指令它指定好了, 不可以修改, 我想拿低版本gcc测都没辙, 伟大的ccf指定的gcc版本是3.3.x, 我机子上只有4.3.2, 虽然后来在etch的源里找到了3.3的安装包.. 反正挺复古的; 这些都不是最愁的, arbiter测了多少次成绩, 就会产生多少个不同的排名, 无言…
有关noip评测的各种稀奇古怪的问题仍在oibh热烈讨论与争吵中.. 至于写不写题解看我心情吧, 前提还是我能把第四题想出来..
换了个新首页. 当然还是没啥特别的, 我没做出我脑中的构想, 但就这样吧. 我觉得能体现我的一些信息点就可以了, 有机会再补充. 怎么说也比挂一张照片的那个要丰富一些吧? ( 知道那张照片是哪里吗? 不在新疆住的同学大多只知道喀纳斯湖, 却没听过比它更美的赛里木湖的名字.. )
平板阅读灯到手, 躺床上看书从此就方便了. 在卓越买的”阅之星”的, 用了两次, 还不错, 比较满意. 第一次选择加急快递, 三天就送到我家了( 以前都是十天 ), 真不习惯..
最后小小的八卦一下, matrix67牛的mm文笔真是优美~
我是标题党, 啦啦啦~
其实也不完全是. 最近偶然找到这个有趣的网站 ( 只是域名有趣.. ) http://goodbye-microsoft.com . 大大的Debian的标志.
Debian~ 这周将系统换成了Debian, 原因是Ubuntu 8.10实在令人失望, 太慢了太慢了.. 一气之下换成Debian, 直接使用开源驱动, xorg.conf 一点修改都不做, 然后待机. 我的laptop第一次在linux环境中待机了, 太不容易了.. 我想是因为Ubuntu每次太”自主”的修改了xorg.conf 导致显卡驱动出现一些问题 ( 珍爱生命, 远离ATi ). 代价是compiz就没法启动了, 3D支持一直打不开, 我想只能装官方驱动了. 但又害怕又出现什么冲突搞的又没法待机了, 我对待机的需求比桌面效果重要的多, 所以还是先这样吧.
[update]后来装了官方的ATi驱动, 没什么冲突 
体会是, 用了Debian才知道Ubuntu原来为我们做了那么多, 同时在效率上做出了很大的牺牲. lsz大牛介绍Arch后, 本来想过换成Arch, 但配制太复杂了, wiki看的我头疼, 还是在很舒服的Debian下多学些东西吧~
期中考终于结束了, 考化学时写到最后卷子都读不懂, 自然科学真是神奇啊~ 一周时间恢复一下状态, 下周noip! 查看更多 »
感冒了, 头昏脑胀的, 啥都不想做了. 让我水一会儿.
这篇日志着躺在床上完成的. 躺着敲键盘感觉真爽, 很想买一个无线路由, 甩掉那个该死的网线. 但又没啥太大的用处, 不太想浪费钱..
以前拿上键盘就开始乱敲, 敲着敲着就能写满一屏幕, 尽管不知所云, 但不管写什么写完后都会觉得很舒服. 现在思绪单调的连两三句话都写不出来了, blog都变成”半月谈”了. 不是没有时间, 是根本不想写任何东西. 最初开始写blog时就是喜欢那种写完东西很舒服的感觉, 结果过了很久之后反而什么都写不出来了. together最初就是全篇的废话, 从头到尾 ( 其实现在也好不到哪去 ), 之后就觉得不能那么水, 然后写的东西稍微有了些逻辑, 记的东西也就丰富了一些. 但毕竟丰富的东西并不会总是出现, 或者当越来越累之后再丰富的生活中也不会有任何感触. 整个十月过的一天比一天累, 到现在已经只想睡觉了. 下过一场雪, 意味着冬天已经来了. 冬天果然是我最糟糕的季节. 漫长的冬天, 不知道什么时候才会结束啊. 查看更多 »
这标题看着很像tags.. 最近比较乱..
花两天时间学了一下python, 直接原因是spoj上KAMIL这道题 ( 用python可以写的更短 ), 根本原因是对脚本语言的好奇.. ( 有点文科男的味道.. ). 感觉用python做数据生成器什么的还是比c短的多, 挺舒服的.. 更深的应用就等用到的时候再研究了.
(如果你也想学python, 我推荐<简明 Python 教程>, 不长, 但很实用)
blog改变了几个细节的内容, 比如添加了ubuntu 8.10的倒计时模块( 期待啊, 10月30日就发布了~, 据说解决了一部分机器不能待机的问题, 不知道我这儿的问题有没有解决 ), recent comments部分添加了访客头像, 评论中添加了reply键, 还有若干跟theme有关的细节. 其实我想在dqfind.com中添加一些除了blog之外的内容, 但一方面太忙了, 另外一方面也确实没想好到底哪些内容比较有意思, 暂且就让它发挥blog的作用了.
最近在看<组合数学>. <什么是数学>完整的看完好像不太现实, 打算每周找感兴趣的几页读, 慢慢的将它读完. 暂且不太想看关于算法与数据结构方面的内容, 这几个月就多学点数学了. 每次一上语文课就忽然产生想读某某小说或某某书信集的冲动, 等真坐下来看书却又丝毫没了兴趣, 某某时期的文学青年应该就是在这种冲动中产生的吧~
十一在补课中结束了. 累计放假三天, 其中两天在写作业, 部分作业只好无视 ( 生物..生物..不做.. ). 玩掉一天, 吃饭, ktv. 认识了那个和我同名, 跑的比风还快的alft, btw, 他的声音很像更加沙哑的阿杜啊, 无论怎样柔软的歌从他嗓音里唱出来都跟摇滚一样了..
