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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

BJOI2013Day4考试  

2013-06-10 22:55:44|  分类: OI |  标签: |举报 |字号 订阅

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


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

下面就把题目和算法贴出来吧

NOI2013北京队选拔赛
BJOI2013
竞赛时间:2013年6月2日上午8:00-13:00
题目名称 分数 压力 打回原型
目录 score load recover
可执行文件名 score load recover
输入文件名 score.in load.in recover*.in
输出文件名 score.out load.out recover*.out
测试点数目 10 10 10
每个测试点分值 20 20 20
是否有部分分 无 无 无
题目类型 传统 传统 提交答案
注意:
1. 最终测试时,所有编译命令均不打开任何优化开关
2. 每道题目的空间限制为:256M,代码长度限制为1M
3. 为了尽量接近NOI的实际情况,你的程序会在一个32位的NOILinux系统上
用Arbiter单机版进行测评。根据我的观察,Arbiter单机版是一个危险
的测评软件。根据竞赛规则,如果你的程序进行下列行为,虽然能通过
Arbiter的评测,但一旦被任何人指出,也会被算作0分:
直接的或间接的,但不包括无法避免的,进行下列之外的任何系统
调用:
access,brk,close,fstat,mmap,mprotect,munmap,open,read,wri
te,dup3,dup2,arch_prctl,execve,exit,exit_group,rt_sigactio
n,ioctl,getrlimit,readlink 这包括但不限于创建新的线程/进
程,运行外部命令,访问网络,向测评系统发信号,捕获程序收到
的信号,修改程序的资源限制。
直接的或间接的访问除输入、输出、运行所必须的文件以外的任何
文件,特别的,禁止访问其他选手的程序以及答案文件;
直接的或间接的,但不包括无法避免的,使用编译器内建、扩展函
数,包括特殊计算函数、SSE/AVX处理器扩展。

分数
【问题描述】
出题最困难的地方在于调控分数。题目必须要让选手之间的实力差异通过
分数体现出来。而参加考试的选手的能力水平分布严重影响了题目的得分分
布。适合一个省份的题目换到另一个省份里可能就瞬间变得没有意义。这里面
有一个十分微妙的关系。 为了更好的把握题目的难道,小强建立了一个模
型。 每个选手的实力都是一个0到100之间实数。小强可以掌控一个题目的“难
度”和“区分度”。一个选手的得分是:
实际分数=100/(1+exp(难度-区分度*实力))
其中,exp是指数函数。理想情况下,N个选手(N≥3)的理想分数应当形
成一个首项100,末项为0的等差数列(我们把实力最强的选手排在最前面)。
定义一个题目的分数偏差为:
对所有学生求和,(理想分数*ln(100/实际分数)+(100-理想分数)*ln(100/(100-实际分数)))
其中,ln是自然对数。 现在,你要计算:对于给定的N个选手的实力,分
数偏差的最小值是多少?
【输入文件】
输入文件为score.in。
第一行包含两个正整数N和P,表示选手的个数以及精度要求。
接下来的N行,每行包含一个0到100(闭区间)内的整数。
【输出文件】
输出文件为score.out。
输出一个实数,取P位有效数字,下取整。
【输入样例】
5 4
100
20
15
10
8
【输出样例】
195.2
【样例解释】
很显然,这个队伍里面有一个神牛和一群水人。出题的时候应当把精力放
在如何区分水人中谁更水,而不是牛人中谁更牛上。
最优的情况下,难度是4.662016,区分度是0.299386,此时实际得分是:
99.999999,79.013041,45.729992,15.867070,9.389952
下面这个图展示了理想得分、实际得分关于实力的函数。
作为对你的一个额外的提示,下面这个图是分数误差关于难度-区分度的
图像。可以看到,这里只有一个极值点。(图就略了)
【数据规模和约定】
一共有10个测试点,P的值依次是1到10。
对100%的数据,N≤20




压力
【问题描述】
如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的
核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力
之下。
小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的
链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发
送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走
的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设
备。
你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有
多少个?
【输入文件】
输入文件为load.in。
第一行包含3个由空格隔开的正整数N,M,Q。
接下来M行,每行两个整数u,v,表示第u个网络设备(从1开始编号)和
第v个网络设备之间有一个链接。u不会等于v。两个网络设备之间可能有多个
链接。
接下来Q行,每行两个整数p,q,表示第p个网络设备向第q个网络设备发
送了一个数据包。p不会等于q。
【输出文件】
输出文件为load.out
输出N行,每行1个整数,表示必须通过某个网络设备的数据包的数量。
【输入样例】
4 4 2
1 2
1 3
2 3
1 4
4 2
4 3
【输出样例】
2
1
1
2
【样例解释】
设备1、2、3之间两两有链接,4只和1有链接。4想向2和3各发送一个数据
包。显然,这两个数据包必须要经过它的起点、终点和1。
【数据规模和约定】
对于40%的数据,N,M,Q≤2000
对于60%的数据,N,M,Q≤40000
对于100%的数据,N≤100000,M,Q≤200000

打回原型
【问题描述】
不可否认的是,网络的发展产生了疯狂增长的内容。这些内容可能是每个
网民随手记下的日志,或者政府公示的经济数字。内容的格式不统一,质量参
差不起。于是,很多以前不曾存在的问题渐渐出现。
有一个问题很有意思。某些文档在经过了若干次的格式转换(odt,输出成
pdf,打印到纸上,拍摄为图片,光学字符识别)之后损失了大量的信息,甚
至,只剩下了一堆小写字母:
quic
kbro
vvnf
oxju
mpso
vert
hela
zydo
g
这个貌似加密过的文字其实只是:
Quick brown fox jumps over the lazy dog.
去掉所有空格、大小写、标点,然后把w换成了vv(两个v),然后每4个
字符1行排版得到的而已。
定义一个合法的英文文本为由空格隔开的若干英文单词。所谓英文单词,
就是随试题下发的englishwords.txt中的行。
给定一堆英文字母。你要做最少次数的修改使得它变成一个合法的英文文
本。
每次修改可以:插入一个字符(包括空格),或者删除一个字符,或者替
换一个字符(但不能替换成空格),或者交换相邻的两个字符。
【输入文件】
输入文件为recover*.in。其中,*代表1~10
输入文件中有很多的小写字母。
【输出文件】
输出文件为recover*.out
输出一个整数,表示最小的修改次数。
【输入样例】
baetalipoproteinemiatuberculariaceae
【输出样例】
2
【样例解释】
交换开头两个字符,然后插入一个空格,得到
abetalipoproteinemia tuberculariaceae
相信我,这是两个英文单词。
【数据规模和约定】
你会得到这题的所有输入文件。


这次比赛的分数嘛,先恭喜徐禹生、张子禾获得了这次的最高分360(满分600)。
另外恭喜赵晟宇(人大附中初二!)、孟涛在总的排名中排到了前两个。
人大附中初二真是一个神奇的地方。。。

题目我觉得还是难度比较适中的,没有搞的特别变态。。。不过,似乎后面的题除了骗分以外也没有人写别的算法了。

第一题,一个赤裸裸的凸优化问题。什么是凸优化?
然后你可以用各种方法去解了。
这次,大家最喜欢的方法似乎是三分搜索套三分搜索。

第二题,一个赤裸裸的图论问题。
标准算法:先求双联通分量的分解,把图变成一个树。
之后就是统计每个点被多少个树上的路径覆盖了多少次。这个是可以用经典的LCA+treeDP实现的。
总体的复杂度应该是线性。

第三题,一个赤裸裸的动态规划。
把它当作一个提交答案你就输了。
计算:原串前i个字符变成了一些单词+一个单词片段j,并且第i个字符是或不是要和第i+1个字符交换的情况下的最小操作步骤。
其中j用一个字典树来组织。
然后,就是暴力跑这个dp,2个小时肯定就出来了。

可惜了,虽然看到了人大附中初二的同学发威,不过北京依然没有能够干脆利落秒杀题目的同学。。。加油吧,北京今年NOI的金牌我是没法去拿了。。。


  评论这张
 
阅读(3951)| 评论(15)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

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