省选、noi正式比赛oj数据相关1bjoi2013day4题目

1、BJOI2013竞赛时间：上午8:00-13:00注意:最终测试时，所有编译命令均不打开任何优化开关每道题目的空间限制为：256M，代码长度限制为1M为了尽量接近NOI的实际情况，你的程序会在一个32位的NOILinux系统上1.2.3.用Arbiter单机版进评。根据观察，Arbiter单机版是一个的。根据竞赛规则，如果你的程序进行下列行为，虽然能通过Arbiter的评测，但一旦被任何人，也会被算作0分：直接的或间接的，但不包括无法避免的，进行下列之外的任何系统调用：acs，brk,close,fs,mmap,mprotect,munmap,open,read,write,dup3,dup2

2、,arch_prctl,execve,exit,exit_group,rt_sigactio n,ioctl,getrlimit,readlink 这包括但不限于创建新的线程/进程，运行外部命令，网络，向系统发信号，捕获程序收到的信号，修改程序的资源限制。直接的或间接的文件，特别的，除输入、输出、运行所必须的文件以外的任何其他选手的程序以及文件；直接的或间接的，但不包括无法避免的，使用编译器内建、扩展函数，包括特殊计算函数、SSE/AVX处理器扩展。第 1 页 共 7 页题目名称分数压力打回原型目录scoreloadrecover可执行文件名scoreloadrecover输入文件名score

3、.inload.inrecover*.in输出文件名score.outload.outrecover*.out测试点数目101010每个测试点分值202020是否有部分分无无无题目类型传统传统提交分数分数【问题描述】出题最的地方在于调控分数。题目必须要让选手之间的实力差异通过分数体现出来。而参加的选手的能力水平分布严重影响了题目的得分分布。适合一个省份的题目换到另一个省份里可能就瞬间变得没有意义。这里面有一个十分微妙的关系。 为了更好的把握题目的难道，建立了一个模型。 每个选手的实力都是一个0到100之间实数。度”和“区分度”。一个选手的得分是：可以掌控一个题目的“难其中，exp是指数函数。理

4、想情况下，N个选手（N3)的理想分数应当形成一个首项100，末项为0的等差数列（定义一个题目的分数偏差为：把实力最强的选手排在最前面）。其中，ln是自然对数。 现在，你要计算：对于给定的N个选手的实力，分数偏差的最小值是多少？【输入文件】输入文件为score.in。第一行包含两个正整数N和P，表示选手的个数以及精度要求。接下来的N行，每行包含一个0到100（闭区间）内的整数。【输出文件】输出文件为score.out。输出一个实数，取P位有效数字，下取整。【输入样例】5 41002015108【输出样例】195.2【样例解释】第 2 页 共 7 页分数很显然，这个队伍里面有一个神牛和一群水人。出

5、题的时候应当把精力放在如何区分水人中谁更水，而不是牛人中谁更牛上。最优的情况下，难度是4.662016，区分度是0.299386，此时实际得分是：99.999999，79.013041，45.729992，15.867070，9.389952下面这个图展示了理想得分、实际得分关于实力的函数。作为对你的一个额外的提示，下面这个图是分数误差关于难度-区分度的图像。可以看到，这里只有一个极值点。【数据规模和约定】一共有10个测试点，P的值依次是1到10。对100%的数据，N20第 3 页 共 7 页压力压力【问题描述】如今，路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的路由器典型的要处理

6、100Gbit/s的网络流量。他们每天都之下。巨大的压力建立了一个模型。这世界上有N个网络设备，他们之间有M个双向的是连通的。在一段时间里，有Q个数据包要从一个网络设备发。送到另一个网络设备。一个网络设备承受的压力有多大呢？很显然，这取决于Q个数据包各自走的路径。不过，某些数据包无论走什么路径都不可避免的要通过某些网络设备。你要计算：对每个网络设备，必须通过（包括起点、终点）他的数据包有多少个？【输入文件】输入文件为load.in。第一行包含3个由空格隔开的正整数N，M，Q。接下来M行，每行两个整数u，v，表示第u个网络设备（从1开始）和第v个网络设备之间有一个。u不会等于v。两个网络设备之间

7、可能有多个。接下来Q行，每行两个整数p，q，表示第p个网络设备向第q个网络设备发送了一个数据包。p不会等于q。【输出文件】输出文件为load.out输出N行，每行1个整数，表示必须通过某个网络设备的数据包的数量。【输入样例】4 4 21 2【输出样例】第 4 页 共 7 页压力112【样例解释】设备1、2、3之间两两有，4只和1有。4想向2和3各发送一个数据包。显然，这两个数据包必须要经过它的起点、终点和1。【数据规模和约定】对于40%的数据，N，M，Q2000对于60%的数据，N，M，Q40000对于100%的数据，N100000，M，Q200000第 5 页 共 7 页打回原型打回原型【问

8、题描述】不可否认的是，网络的发展产生了疯狂增长的内容。这些内容可能是每个网民随手记下的志，或者的经济数字。内容的格式不渐渐出现。，质量参差不起。于是，很多以前不曾存在有一个问题很有意思。某些文档在经过了若干次的格式转换(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。其中，*代表110输入文件中有很多的小写字母。【输出文件】输出文件为recover*.out输出一个整数，表示最小的修改次数。【输入样例】第 6 页 共 7 页打回原型baetalipop