显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 
 
 
 

BJOI2014Day4考试

2014-6-1 16:59:55 阅读3317 评论5 12014/06 June1

试题
https://onedrive.live.com/redir?resid=354ED8646264D3C4!303&authkey=!AKJFBXypoKtt_lg&ithint=file%2c.pdf

成绩(初步成绩,可能有变动,以最终公示的成绩为准)

姓名 编号 总分
idea merger

作者  | 2014-6-1 16:59:55 | 阅读(3317) |评论(5) | 阅读全文>>

BJOI2013Day4考试

2013-6-10 22:55:44 阅读3812 评论15 102013/06 June10

这次我不是做题的了。。。是出题的了。
题目下载(如果挂了及时和我说)
http://dl.vmall.com/c07mammrrg
数据
http://dl.vmall.com/c0a5qyysz0


不过出题也各种窘迫。
比如,我已经不能忍受LibreOffice3的崩溃速度了。
于是,我决定使用html书写题目文件。
http://dl.vmall.com/c0ojc891mb
有兴趣的同学可以玩一玩
还比如,我发现Arbiter单机版是一个让人毛骨悚然的测评软件。。。但愿NOI的时候它能强大一点。

作者  | 2013-6-10 22:55:44 | 阅读(3812) |评论(15) | 阅读全文>>

在北京冬令营的讲课

2013-2-5 22:35:47 阅读3604 评论33 52013/02 Feb5

时间过的好快啊,一转眼,立春了。

地点还是十一学校,但人已经换了一茬。

如果你是来找讲义、标程(有些错误)、题目的,给个链接:
https://skydrive.live.com/redir?resid=354ED8646264D3C4!102
有一个020405.zip
如果你是来找findcheat那题的测试结果的,那么同上。
或者我可以这么告诉你:
标程:满分
其他人:编译错误(大多数),超时(一些)、段错误(几个)、错误答案(很少)
如果把比较不正常的输入剔除,那么所有的程序都超时了。

如果你是听了课的,那么我希望你能够继续了解:

作者  | 2013-2-5 22:35:47 | 阅读(3604) |评论(33) | 阅读全文>>

说说NOIP2012的题

2012-11-19 22:10:59 阅读3391 评论10 192012/11 Nov19


再次围观OI比赛了。


今年NOIP的题值得赞美。我对它的概括为:很实惠,有新意有难度

第一天
第一题 vigenere。简单密码的解密。
北京一共192人,其中满分143人。
不用说了。

第二题game
这是一个很“实惠”的题目。
它是寻找一个排列P,最小化:
max(product(A[P[i]] for i in range(a))/B[P[a]] for a in range(0,n))
这种题对于受过良好数学/信息学系统训练的同学来说,是非常简单的。
但对于其他竞赛选手来说,就比较难了。
我们只要考虑将序列中的相邻两个人交换会发生什么即可:
  S   a      c

作者  | 2012-11-19 22:10:59 | 阅读(3391) |评论(10) | 阅读全文>>

NOI2012团体对抗赛程序

2012-8-3 17:19:09 阅读2553 评论17 32012/08 Aug3

应各种同学们的要求,在经过短暂讨论之后,我们决定将北京队的团体对抗赛以及相关工具进行开源。
我们使用GPL3.0许可证:http://www.gnu.org/copyleft/gpl.html
许可证的总结为:你可以自由的复制、修改、分发本软件并有权利获得源代码,唯一的限制的是对本软件及派生作品必须使用本许可协议进行授权。我们对本软件不做任何形式的担保。

作者  | 2012-8-3 17:19:09 | 阅读(2553) |评论(17) | 阅读全文>>

NOI2012记行

2012-8-1 22:09:08 阅读6038 评论30 12012/08 Aug1

作者  | 2012-8-1 22:09:08 | 阅读(6038) |评论(30) | 阅读全文>>

在北京的集训(7-24)

2012-7-24 14:29:32 阅读1754 评论0 242012/07 July24

今天还是陈高远的课。为了回应“昨天题太难”的抱怨,今天的题稍微和谐了一点。不过,依然是不是很好做。

第一题:跳跃
有N个定义在1~50!间整数上的周期函数,最小正周期不超过50.令F(x)等于他们的和。对每个n=0..N,问F(x)=n有多少个根。

第二题:古迹
有一个01矩阵,第a行第b列为1当且仅当:
abs(a-b)==1 or a+b==n+1 or set([a,b]) in [set([1,N/2]),set([N/2+1,N])]
一次“操作”可以选定一对u,v,
交换矩阵的第u、v行,同时交换矩阵的第u、v列

作者  | 2012-7-24 14:29:32 | 阅读(1754) |评论(0) | 阅读全文>>

在北京的集训(7-23)

2012-7-23 20:29:28 阅读1468 评论0 232012/07 July23

今天是陈高远讲课啦!

第一题:SRM533 D1 hard
pikachu
用"pi"、"ka"、"chu"作为字母给一些单词编码(即,给每个单词关联一个用"pi""ka""chu"拼成的串),使得任意的字母串至多有一种解读为单词序列的方法;给定每个单词的词频,问编码串的长度最少是多少,以及编码的方案数有多大。单词数N<=40。注意:"pi","ka",“chu"在串中的长度依次是2,2,3。
例如:有两个单词要编码,词频都是1,那么最优的编码长度是4,两个单词分别可以用"pi","ka"编码,有两种方案。

很想Huffman编码,对吧?不过,这其实是一个dp题。
来自SRM533
方法:从一个树根开始“生长”字典树,每片当前的叶子可以用于编码单词,也可以长出三片新的叶子。

作者  | 2012-7-23 20:29:28 | 阅读(1468) |评论(0) | 阅读全文>>

在北京的集训(7-22)

2012-7-22 15:43:15 阅读1103 评论0 222012/07 July22

今天还是 黄祎程 的课。
题很简单。

第一题:
从一个矩形的左下沿某个路径走到右上,使得距离某些特殊点的最近距离最远。
N<=5000

其实就是要找一个能够把左下和右上分开的特殊点之间的路径,使得最远的跨度最近。这个求一个最小生成树即可。


第二题:
写一个1~K的长度为N的数列,使得前K个数依次是1~K,最后K个数互不相同,并且相同的数之间的间隔不超过P-1个数。求有多少种方法。
N<=1e9,K<=10,P<=10

想没想到“生成树计数“?就是一个状态dp而已。

第三题:
维护一个序列A,对每个询问i,求j的数量,使得max(A[i..j])=max(A[i],A[j])
每次可以修改一个数。
N<=5e4

作者  | 2012-7-22 15:43:15 | 阅读(1103) |评论(0) | 阅读全文>>

在北京的集训(7-21)

2012-7-21 15:21:14 阅读1136 评论2 212012/07 July21

今天是黄祎程讲的课。

第一题:
给一片森林,每次连一条边把两个树连成一个树。动态问当前连通且最远的两个点的距离。
N<=1e5

我想都没想,写了一个动态树。。。还好一次调试通过,否则就哭了。
实际上,可以有超级简单的做法。
假设两个树,他们的直径分别是A-B,C-D,那么把他们合并起来,新的直径只可能是:
A-B,C-D,A-C,A-D,B-C,B-D,所以,写一个LCA查询距离即可。。。


第二题:
给一个树,问有多少种方法,把他分成若干个等大小的树块。
N<=1e6

作者  | 2012-7-21 15:21:14 | 阅读(1136) |评论(2) | 阅读全文>>

在北京的集训(7-20)

2012-7-20 20:31:48 阅读1324 评论5 202012/07 July20

今天依然何博硕讲课。
三个题,还比较可做。

第一个题:
给一个有向图G(节点数<=50),求一片森林,满足:
A如果是B在森林里的祖先,那么A在G中可以到达B;
如果B在G中可以到达A,那么B不能是森林里A的儿子;
如果A、B在G中可以相互到达,那么他们在森林里不能有相同的父亲。
你要输出森林里至少由多少个树组成。

这题很经典吧,一看就是网络流的题。如果你打算去NOI,那么建议你先思考一下建图的方法。
先计算强联通分支。
之后,核心思想是让父亲和儿子建立匹配的关系,可以:
每个强联通分支作为左边的点,向右匹配(当儿子)

作者  | 2012-7-20 20:31:48 | 阅读(1324) |评论(5) | 阅读全文>>

在北京的集训(7-19)

2012-7-19 15:32:30 阅读1840 评论10 192012/07 July19

今天是做绍兴一中的三个练习题

 

第一题:

给一个无向图,求两个点之间最短路的个数(如果两个点之间的距离超过2,就输出“太长”)

N,M都是1e5范围的数。

其实只用处理距离是2的情况即可。

很简单,用大-小分治即可。

大度数的点和大度数的点之间的结果暴力算,打一个表。

小度数的点和小度数的点之间暴力算。

大度数和小度数之间:枚举小度数点的邻居,在大度数点的邻居们中查找。

 

第二题:

一副牌,四个花色,点数从1~正无穷。从中选不超过K张,他们点数和是n,求选法的种数。

K<=10

n<=1e9

先写一种搞笑的dp:

作者  | 2012-7-19 15:32:30 | 阅读(1840) |评论(10) | 阅读全文>>

ZJOI2012《波浪》《灾难》题解

2012-5-27 16:21:20 阅读5491 评论19 272012/05 May27

我出题的特征很多人都已经发现了,那就是以“小强和阿米巴是好朋友”开头。

具体的题面可以去lydsy.com/JudgeOnline看看。
我说一下做法:

《灾难》
【题意简述】

给一个有向无环图,问每个节点删掉之后会导致多少个点不可达。

【算法描述】

有这样一个事实:
生物之间的灭绝的结构形成了一个树,树上的一个节点的灭绝会且仅会导致以它为根的子树的灭绝。我们管这个树叫“灭绝树”。
对于生产者,我们给它添加一个假想的食物:太阳。
这样,“灭绝树”就形成了一个以太阳为根的树。

作者  | 2012-5-27 16:21:20 | 阅读(5491) |评论(19) | 阅读全文>>

BJOI2012 Day3(30%)

2012-5-27 14:55:59 阅读1828 评论9 272012/05 May27

应大家要求,我先把北京集训的题目贴出来。至于数据,我正在慢慢联系,看出题人是否同意公布。
http://115.com/file/e7jf38x9#bjoi-all.zip

今天的题目很和谐。

题目是否让贴出来我正在联系。可以先概括一下题意。

第一题:tree
一个无向图,每个边有两种权值(都是正的),
求一个生成树,使得他的两种权值的和的乘积最小。
N<=300 M<=10000

第二题:chess
若干个饼干,每次可以把一个饼干啃一口(之后分成两块)。啃的第i口的得分为啃的长度乘以2^i。两人轮流啃。

作者  | 2012-5-27 14:55:59 | 阅读(1828) |评论(9) | 阅读全文>>

CTSC2012

2012-5-9 19:19:28 阅读4594 评论18 92012/05 May9

经过激烈的角逐,CTSC2012可算落幕了。
先恭喜6个进入面试的同学:
李超、顾昱洲、钟沛林、艾雨青、王钦石、沈添笑
最终入选的同学是谁呢?大家可以自己猜猜,之后到noi官网上去看答案。

我发一下各种东西:(体积比较大,我用115了)
题目:
http://115.com/file/anw0huco#CTSC-2012-DAY1.pdf
http://115.com/file/c28abdrq#CTSC-2012-DAY2.pdf
数据(我整理的数据不是最终版,每个题只有前几个点用于了正式测评,后面的点可能有问题)
http://115.com/file/be9c3474#evaldata.tar.7z

作者  | 2012-5-9 19:19:28 | 阅读(4594) |评论(18) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 

北京 朝阳区 天蝎座

 发消息  写留言

 
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 

发现好博客

 
 
列表加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017

注册 登录  
 加关注