http://blog.sina.com.cn/eggleung[订阅]
个人资料
公告
此乃巨菜哑熊之洞也。
我的USACO题解请点这里
我的空间请点这里
评论
读取中...
clustrmaps
Locations of visitors to this page
博文

这个题比赛的时候我们队没有出,原因是当时我和iSea同时否定掉了1000 * 2 ^ 14的算法,最后我写出了一个1000 * 2 ^ 7 * 7的算法,但是WA到了比赛结束。今天重新写了一下这个题,结果在HDU上一次AC了,非常郁闷……不过更郁闷的是跑得非常慢,貌似比1000 * 2 ^ 14的算法还慢,可能主要因为常数比较大吧……其实如果加一些东西的话,应该可以做到1000 * 2 ^ 7的。还是说一下我的做法吧。

维护两个数组cool_max[state]和cool_sub_max[state],前者保存从开始到当前时间并且当前按键状态为state的cool最大值,后者表示从开始到当前时间并且当前按键状态包含了state的cool_max的最大值(即cool_sub_max[state] = max(cool_max[k] | state包含于k))。那么顺序扫描时间,并在每个时间内枚举所有state,如果state合法(按键不冲突),由于如果当前state中某个按键处于strip note内,那上一个时间我必须也按下这个键(除非当前处于strip note的起始时间),否则当前按下这个键没有意义,因此当前的cool_max[state]就等于所有单个按键的cool加上上一个时间cool_sub_max[k | k是前述的必须按下的键的状态]。在当前时间算

Hibix@DHU 总结(2009-10-26 17:00)

嗯……这次上海除了拿到金牌外其它都非常悲剧……具体就不说了……总结下比赛情况吧……

 

练习赛就不多说了……B题是SB题我秒了。A题我写了一个错误的二分匹配的算法改呀改、WA呀WA,最后暴力过去了……C题iSea推出了一个惊人简单的结论然后AC了……总之做得非常慢,非常囧……

 

正赛的总结如下:

A题,64分钟,1Y。

A题出的非常晚,主要原因是bb拿到题一看A题的图以为计算几何就先没有仔细看,然后我和iSea一起讨论了B题,想到了变乘为加、矩阵乘法等等。结果iSea写了一会B题发现B题远没有想象中的那么简单,于是换我去写A题,也是全场比赛最简单的一道题,直接bfs预处理,然后就AC了。

B题,90分钟,1Y。

B题并不是一道简单题,而且细节比较多。我们队rp大爆发,我前一天晚上很诡异的突然想到了天王曾经说过的a ^ b % m的解决方法,把它抄在了标程的第

Hibix@NIT 总结(2009-10-18 22:03)

虽然颁奖典礼回来的路上我们还是有说有笑的,但是心中还是不免有一丝遗憾。4月份的时候我们就来到了这里参加了那个全国邀请赛,拿到的是金牌最后一名;今天来参加正式的区域赛,拿到的是银牌第一名。也许这就是RP守恒定律吧。下面写写总结吧。

 

来宁波的第一天就每人发了一个杯具……很囧……

 

第二天练习赛三道大水题让我们写的各种窘迫……

A题iSea写了很久才AC……

B题我用priority_queueTLE了2次然后iSea暴力过去的……

C题bb看一眼告诉我说线段树,我正准备写iSea说有一个队伍3分钟就过了这题,不可能那么麻烦。然后我一想就排序后扫描线过了。比赛结束以后xhw告诉我们题目里面说了那些区间都不相交的……终于理解为什么有人3分钟就过了这题了……

 

正赛的总结如下:

E题,5

悲剧啊……(2009-09-17 21:59)

各位教练:

由于突发事件,2009 Asia Regional Harbin无法如期举行。
我们正在等黄金雄教授的指示,再做最后决定。

给各校带来的不便,我们深表歉意。

2009 Asia Regional Harbin组委会

========================================华丽的分割线========================================

各位教练:

关于赛事无法如期举行的原因主要是甲型H1N1流感。
我们一直忙于赛事准备工作,对其他的无暇关心。网络赛前听说哈尔滨某些院校出现了确诊病例,我们跟校方做了简要沟通,可能当时的情况不是太严重,校方同意我们这个赛事继续进行。
今天下午计算机学院孟书记打电话说这个赛事恐怕要延期,我们马上去见周校长和张校长,获知事态已经很严重,根据教育部和省教育厅的有关精神,赛事必须延期。
黑龙江省的高校已经取消了十一长假,各校加强了防控,进入校门、教学楼、宿舍等,都要接受验证,出现确诊病例的学校已经封校。

大致情况就是这样,进一步了解可登陆:
http://news.hit.edu.cn/articles/2009/09-16/09154436.htm

[WOJ]1408 Ball(2009-09-09 02:28)
Oh, my god... 这恐怕是我目前为止ACM/ICPC生涯中最麻烦最复杂代码最长的一道题了……这是今年武大校赛的一道题目,是momo精心准备的一道“不可做题”……在momo强烈推荐之下我只好硬着头皮去做了……也终于硬着头皮AC了(当然也有参考当时4份长度都达10+kb的标程=.=)……题目请点这里
题意倒很简单,只是做起来就不那么容易了……大概的做法就是二分圆的半径,然后就可以把所有的障碍物扩展为圆角矩形,这个圆角矩形是可以拆成四个圆和两个矩形的,现在的问题就变成判断起点和终点这两个点能否连通了。然后可以发现只需要走点与圆的切线还有圆与圆的切线就可以了(当然这些切线得合法)。所以求出所有的切线,用这些切点离散化所有的圆,再构出图判断起点和终点是否存在路径就可以了(我用的并查集)。
下面就是恐怖的代码了(其实计算几何代码真的挺优美的):
这个暑假的总结(2009-08-31 21:49)
今天是8月的最后一天了,也马上就要开学了,就扯两句吧……
这个暑假只回家了一周,从7月12号开始就待在武汉了。回家的那一周感觉很美好,只是给我印象最深的却是感觉爸妈更加老了……回武汉后基本上每天的生活就是吃饭睡觉泡机房做比赛了……天气很炎热,机房空调质量也不是非常好,每天又要训练,感觉还是挺累的……
好像又不知道说什么了……那还是说ACM/ICPC吧……
8月1号到现在,基本上是每天一场组队赛。总体来说,问题还是非常多,暂且总结如下吧:
  • 简单题还是不够稳。我和iSea都会经常犯一些SB错误……
  • 卡题现象非常严重,卡题导致经常没有时间把自己能做的题都做出来。而且由于期间xbb生病只有我和iSea做比赛,经常会出现我和iSea各卡一道题目卡死的情况……这个需要调整,建议以后出现这种情况我和iSea要交换题目。
  • 知识面还是很不足。计算几何现在还算有点起色
[推荐]时空幻境(Braid)(2009-07-18 20:35)

嗯,非常非常好的一个游戏,不管是从游戏的构思,设计,画面,音乐(虽然这个不是原创)还是故事的编排上看,我觉得都堪称是一部神作!强烈推荐!

顺便说一句,游戏中书上那些不知所云的文字我是不怎么理解的……看了网上很多的观点,至少说明游戏中每一个元素都是有着深层的含义的,游戏到底是要表达什么呢?自己玩玩去体会体会吧!

 

通关

 

嗯,早就听别人说VC下Debug和Release方式编译出来的可执行文件差别很大,但是一直都不知道有多大。于是前段时间就测了下两者的时间开销上的差异,真是不测不知道,一测吓一跳……

主要进行了以下代码的测试(仅仅测试了一些简单的东西,大家有兴趣可以自己试试):

//执行10亿次空循环
#include <cstdio>
#include <ctime>

using namespace std;

int main() {
    clock_t t = clock();
    for (int i = 0; i < 1000000000; ++i);
    printf('Time cost: %d\n', clock() - t);
    return 0;
}

(2009-06-06 14:21)

嗯,抢到的两张票。不过今年貌似没有时间去北京了……白抢了……

去湖南的一些总结(2009-06-02 17:30)

嗯,周六早上出发去的湖南。由于晚上没有睡好,火车上大家又一起玩闭眼(貌似某次闭眼我险些睡着),所以到了长沙以后非常困……

下午练习赛,其它队伍都想睡觉,所以没去,只有我们去了。练习赛题目一共4道,都很水,我们随便提交了提交,WA几次,反正也很快就全切了,主要目的是熟悉环境。让我们不能理解的是……居然不用PC^2,用OJ来评测……而且居然是Windows XP系统+Devcpp环境……当然还有给高中生用的Free Pascal,还有Java的Eclipse。练习赛期间还有个人问我们怎么读到数据结尾……我们直接faint……切了4道题后我们一人拿了个气球就走了(我本来拿了两个,结果rp了一下有个气球在我走出去以后就不见了=.=)。然后我们开始盘算……一般来讲练习赛不能做太好……否则正赛必挂……

晚上百度之星第一场,题目很BT,都是代码量巨大巨大的题……我们很多人写了A题并且互相对拍了数据。xbb一直在奋战B题……只听他“我变量申明完了,已经xx行了”,“我初始化写完了,已经xx行了”,就这样,xbb奋战了好长时间的B,终于把B这个及其恶心的题目纯朴素写出来了……Orz下……

好友
读取中...
访客
读取中...
Links
寒冰的Blog

好友刘哥!

泽德的Blog

好友伟人!

泪无邪的Blog

好友乙醚!

zgcjyjy的Blog

好友国超

逆铭的Blog

总说自己是巨菜的巨牛!

清风未明的Blog

天真可爱的巨牛!

Terro的Blog

巨牛,撑起甘肃OI一片天!

格格的Blog

好友格格!

王嘉的Blog

兰州五中乐团的前辈,长笛相当牛!

兰州市第五中学

初中学校的网站!

兰州第一中学

高中学校的网站!

音乐播放器