Archive

Archive for October, 2009

NOIP2009初赛问题求解题解

October 17, 2009 Leave a comment

痛定思痛……

第一题,求拓扑排序的个数,先把图转成类似树的形式,自底至上计算:

6:1种

4、7、6:2种,分别为476和746

3、4、7、6:2种

2、3、4、7、6:2种

1、2、3、4、5、6、7:1肯定是排在最前面的,5可以排在1后面任何一个位置,共有6个空,所以这时的方法数是2*6=12种

1、2、3、4、5、6、7、8、9:8和9本身是有序的,插到1~7时,有2种情况:8和9在一起,则共有C(8,1)=8种,8和9隔开,则共有C(8,2)=28种,根据加法原理和乘法原理,最终答案为12*(8+28)=432种

第二题,先将10015转换为7进制得到(10015)10=(41125)7,但可以先付41130,再找回2张,这样总共需要35张

第一题写了336,第二题写了33的,悲剧路过

NOIP出题人,我和你隔的不过是一朵菊花而已

Categories: Old Blog Posts

NOIP2009初赛记

October 17, 2009 Leave a comment

悲喜交加,不过悲大于喜吧……

看了一份非官方答案,自己大概有70多分,不过离80分的目标远了些

问题求解2道题,很猥琐地错掉了。第一题是隔板法,少算一种情况;第二题转7进制转错。这2个错导致我被扣10分……

说来也挺亏的,这一个多月我花了最大功夫的就是数学了,最后爆0,郁闷。

而且更郁闷的是,自己辅导的3个零基础的,包括喇叭帝,希望渺茫。

That’s all for now.

Categories: Old Blog Posts

激动

October 8, 2009 Leave a comment

代码第一次有缩进了,激动啊……

<pre>真是一个强大的标签

看来还是我孤陋寡闻

Categories: Old Blog Posts

USACO 3.1.4 Shaping Regions

October 8, 2009 Leave a comment

首先我要对这道题的数据使用一次嘲弄……裸的O(nab)的算法居然能过10个点

这道题正确做法大致有两种

1、线段树 但这里若用二维线段树,空间上很容易爆掉,所以我们可以把其中一维离散化,再用一维线段树处理另一维(时间换空间……)

2、矩形切割,这是我从网上了解到的一种比较强大的方法

e79fa9e5bda2e58887e589b2

大致思想由这张图已经可以了解的比较清楚了,实现的时候有很多技巧(^-^),这道题的方法到了后面第五章的时候还会用到(Window Area)。

代码:

/* ID: dementr1 PROG: rect1 LANG: C++ */ #include <fstream> using namespace std; ofstream fout ("rect1.out"); ifstream fin ("rect1.in"); int a, b, n; int llx[1001], lly[1001], urx[1001], ury[1001], color[1001]; int cut(int lx, int ly, int rx, int ry, int b) { if (lx==rx||ly==ry) return 0; if (b>n) return (rx-lx)*(ry-ly); if (lx>=urx[b]||ly>=ury[b]||rx<=llx[b]||ry<=lly[b]) return cut(lx,ly,rx,ry,b+1); int x[4], y[4]; x[0]=lx; y[0]=ly; x[3]=rx; y[3]=ry; x[1]=max(lx,llx[b]); y[1]=max(ly,lly[b]); x[2]=min(rx,urx[b]); y[2]=min(ry,ury[b]); int res=0; for (int i=0; i<3; i++) for (int j=0; j<3; j++) if (i!=1||j!=1) res+=cut(x[i], y[j], x[i+1], y[j+1], b+1); return res; } int main() { fin >> a >> b >> n; llx[0]=0; lly[0]=0; urx[0]=a; ury[0]=b; color[0]=1; for (int i=1; i<=n; ++i) fin >> llx[i] >> lly[i] >> urx[i] >> ury[i] >> color[i]; int count[2501]; memset(count, 0, sizeof(count)); for (int id=n; id>=0; id--) count[color[id]]+=cut(llx[id],lly[id],urx[id],ury[id],id+1); for (int i=1; i<=2500; i++) if (count[i]>0) fout << i << " " << count[i] << endl; return 0; }
Categories: Old Blog Posts

无名神作-克新本纪

October 4, 2009 Leave a comment

克新本纪
深中灵秀地也。其奇人千状,不能胜数。克新者,领风云之际,翔九天之云,睥睨群雄,当为深中奇人之龙凤。
时值乙丑年四月,第三学段终了,四单一之算筹先生与吾等分别。有好事者探得继任者乃姓刘,名“克星”。吾前辈闻之,笑而不语。良久,曰:“呜呼, 汝等遇千古名师,教学帝刘讳克新,真乃幸甚至哉!”又正色道:“克新放羊出身,而凌厉狠辣,未有及者。吾辈学子闻有其课,皆悉数逃窜。留者,于段考场上尽 皆摧残至死,死状甚为可怖。克新贻害甚巨,不可留,必除之而后快。”
吾等闻之,如遭霹雳,众皆默然。深中龙潭虎穴之地,外儒内法,柔中有刚。太史公曰:此校未除旧法教师放任之流弊,又添江氏改革之阵痛,混沌不堪,辞教师非如炒鱿鱼之易也。吾等静候,俟其首课。
及至首课,不见克新,但见先师。见先师,皆百感交集,涕泗横流,心中怖惧难道出万之一也。先师默然。
又至次课,座中者终得为克新。容貌甚伟(猥)。慈眉善目,大耳宽颌,颇具佛像。吾等皆佑其早登极乐,莫再祸害人间。待吾入座毕,金口遂开,曰:“ 我前日托病未至,实欲考验汝等定力也。今日观之,尚欠火候。无碍,无碍。汝等盼得名师矣!汝之兽学可得突飞猛进矣!”闻此言,吾皆内焦外嫩,无语之至。未 几其又现雷人之举。克新播幻灯,幕上见一诗。克新堆笑曰:“吾赋诗一首,为汝吟之。”乃朗声诵到:“相识即是缘。缘是×××,缘是×××,……缘分啊,我 骄傲!
“你们有缘遇到我,像我这么好的老师你们打着灯笼都找不到啊!我能让你们在玩中学,在学中玩(太史公曰:此至理也)。只要你们智力正常,照我的 路线走,学兽学其实很简单。”待至末尾,诗已成文。其境界之高,令人自叹弗如;其脸皮之厚,令人自叹弗如;其口才之好,唾沫星子之多,令人自叹弗如。惟其 剽悍之学法,藏头不见尾,庐山不露相,令人心怀惴惴。
继而克新曰:“吾之学法,主在自主学习,即‘带着问题学、答、讲、练、评;理论联系实际,使抽象问题具体化、形象化’。概而括之,莫有如‘高效 放羊’一词精妙者。汝得吾法,不需教,可触类旁通。若遇难题,神挡杀神,佛挡杀佛。”吾皆膜拜。又曰:“学兽学,乃至一切道理,皆须知此四词——元素、结 构、层次、关系。天地万物,莫不归乎于其中。吾法又可略为三词:类比、联想、构造。元素、结构、层次、关系,类比、联想、构造,共念五遍!”吾等如入语文 课之境。再曰:“欲知何理,必览其书。古人云:书读三遍,其义自见。书中自有颜如玉,书中自有黄金屋。书籍是人类进步的台阶……今我曰:书未有读三遍者, 欲工兽学,天理不容!!读十遍!!!”众无言以对,尽皆拜服。一同学怒,眦视克星。克新见状,伸掌抚其头。同学暴怒,欲起身,众劝而作罢。克新曰:“吾抚 汝头,爱汝尔,莫见怪。”其又曰:“古人谓‘严师出高徒’,则师不严无以出高徒也。吾素善体罚。今法虽不容,为汝等谋,当为之。今后如有不从或于堂上玩手 机者,以巴掌伺候。”群怨沸腾,然克新视若无睹。
憩毕,复归座上。克新曰:“此当下不为例。吾上课,必一气呵成,不能有断。”常人如闻此言,必觉不可思议,然克新言论之荒诞稀奇,闻所未闻。吾 等怒无可怒,太息哂之。忍气咽声,待其开课。然克新端坐椅中,安之若素,曰:“汝等自习第一章,做完书上所有习题。”语毕,直盯屏幕,目不转睛。吾等相视 摇头而嘻。
其后数课,我等至而门不开,候久不见。克新来迟,必有托辞,如车多路塞云云。及上课,又目盯屏幕,或察书上作业。学生有疑,问之,曰:“书可读 三遍否?”学生退。再问,则曰:“自行思量”。仍不解,再问,则曰:“汝无慧根,诚难教也。”偶开金口,替吾解惑。道:“兽学公式都很好记。塞抠抠塞,抠 抠塞塞。”或曰:“积化和差与和差化积都没有用”太史公曰:克新固言过些有用知识,但其平日放纵过甚,致课堂懒散成风,有心教,无人听,是以事倍功半,收 效甚微。
至学段中,克新一时传为佳话。一日克新因盯屏幕太久,劳累过甚,遂见周公。见其睡意深沉,有人信步至前,观克新屏上之物。此公回,笑曰:“克新果有帝相。学法固迥于常人,而又能于堂上炒股,面不改色,果当世雄杰也!”炒股帝刘讳克新遂为天下所知。
至学段末,有台湾学者傅某来深中讲解孔孟之道。讲演毕,诸观众可置疑。克新举手。吾等围观,笑而不语。克新曰:“吾得闻台湾清静之地,不生动乱。 大陆经十年浩劫,凋敝不堪,故台湾鱼学应胜于大路,何以现陈水扁此等人?”傅某区区书生,以哲学见长。而刘帝目光高远,深刻锐利,针砭时弊,非傅某所能 及。傅某只得偷换概念(吾疑其答非所问,此问固难答之)。克新帝相毕露,竟成学术帝。深中师者至尊,非其莫属。
至此,克新超凡入圣,成深中霸气之祖。吾辈入段考场,题虽易,然死伤者十之七八,皆拜刘帝所赐。吾辈诚惶诚恐,受恩感激,脸无愠色,于最后一课来见克新,然又见先师。克新可谓有始有终,虎头虎尾,真乃大英雄本色也!!
太史公曰:闻世之师者,必有其法。而克新得以无法胜有法,无招胜有招。以放羊之术,尽绝学生于考场;以放羊之闲,逞炒股之功,赚外快于堂上,可谓 运筹帷幄,断学子之后路,集个人之财富,诚堪大用。而其教学手法之全面,知识之系统,令人疾呼其可为政治先生。而以其口才之好,面皮之厚,能令学生断不知 数学为何物者,千古独此一人。前无古人,后无来者,其境界高以至此,即是非人;而集三帝一体,震古烁今,光耀万世,又非禽兽所能比肩。故其非人亦非兽,究 竟何物?无人知晓。

Categories: Old Blog Posts