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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

BJOIDay4(50%)题目、算法及成绩  

2011-06-12 16:03:29|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天的题是高逸涵出的,他没有写标程。题目只有一个传统题;其他两题都需要checker,但是他没有给我们发。

竞赛时间:2011年6月12日上午
题目名称 矩阵模板 数据库设计 缓存规划
目录 matrix database cache
可执行文件名 matrix database cache
输入文件名 matrix.in N/A cache.in
输出文件名 matrix.out N/A cache.out
每个测试点时限3s 3s 20s
测试点数目 10 10 5
每个测试点分值10 10 15~25
是否有部分分
题目类型 传统 库函数 传统

注意:最终测试时,所有编译命令均不打开任何优化开关
矩阵模板
问题描述
给定一个M行N列的01矩阵,以及Q个A行B列的01矩阵,你需要求出这Q个矩阵哪些在原矩阵中出现过。
所谓01矩阵,就是矩阵中所有元素不是0就是1。
输入文件
输入文件的第一行为M、N、A、B,参见题目描述。
接下来M行,每行N个字符,非0即1,描述原矩阵。
接下来一行为你要处理的询问数Q。
接下来Q个矩阵,一共Q*A行,每行B个字符,描述Q个01矩阵。
输出文件
你需要输出Q行,每行为0或者1,表示这个矩阵是否出现过,0表示没有出现过,1表示出现过。
输入样例
3 3 2 2
111
000
111
3
11
00
11
11
00
11
输出样例
1
0
1
评分方法
本题没有部分分,你的程序的输出只有和标准答案完全一致才能获得满分,否则不得分。
数据规模和约定
对于100%的实际测试数据,M、N ≤ 1000,Q = 10
对于40%的数据,A = 1。
对于80%的数据,A ≤ 10。
对于100%的数据,A ≤ 100。
数据库设计
问题描述
在这个问题中,你需要设计一个简单的底层数据库。
简单的说,你需要写一个程序支持以下三个函数:
Init、CountPoint、InsertPoint。
下面是实现细节:
Init
C语言函数原型:void Init()。
Pascal语言函数原型:procedure Init。
没有输入参数,没有返回值,仅在程序开始时被调用一次。
CountPoint
C语言函数原型:int CountPoint(int Leftside, int Rightside)
Pascal语言函数原型:function CountPoint(Leftside,Rightside:longint):longint
两个参数分别为查询的左右边界,你应该返回之前有多少个点在当前给定左右边界内,在边界上的点视为在边界内。
参数类型:int/int(C/C++),longint/longint(pascal)
返回值类型:int(C/C++),longint(pascal)
InsertPoint
C语言函数原型:void InsertPoint(int Position)
Pascal语言函数原型:procedure InsertPoint(Position:longint)
输入参数为插入的点的坐标。
参数类型:int(C/C++),longint(pascal)
没有返回值
输入文件
本题没有输入文件。
输出文件
本题没有输出文件。
数据规模和约定
对于100%的实际测试数据,每一测试点内总的函数调用次数不超过200000。
你的程序需要能够对于每一个查询函数返回正确的结果才能得到满分,否则不得分。
C/C++选手需要在提交的程序最前面插入如下语句:
#include “database.h”
所有提交程序不能有主函数(C/C++中的main函数,以及pascal中的主函数),若不遵守此规定造成的编译错误责任自负。
缓存规划
问题描述
在计算机科学中,如何科学的利用缓存是一个程序员需要了解的重要的知识。一般在计算机中会有若干级的缓存,越是高级的缓存访问速度越快,但是价格也就越贵,因而容量相应的也就越小。各个层次的缓存构成了整个计算机的存储结构。
在本题中,我们把缓存抽象成数学模型,你需要完整的描述如何合理利用缓存最快的完成指定的任务。
事实上本题中的缓存分为4个层次:
1. 寄存器,共有5个。
与寄存器相关的操作共有如下几个:
a) 读取寄存器,指令格式为L 0 x y,操作为将1级缓存中第y个空间的数读取到x号寄存器,这里0 ≤ x < 5,0 ≤ y < 100。
b) 写入一级缓存,指令格式为W 0 x y,操作为将1级缓存中第y个空间的数改写为x号寄存器内的数值,这里0 ≤ x < 5,0 ≤ y < 100。
c) 寄存器加法,指令格式为A x y,操作为将第x号寄存器的值改写为x和y号寄存器内数值的和。
d) 寄存器乘法,指令格式为M x y,操作为将第x号寄存器的值改写为x和y号寄存器内数值的乘积。
所有寄存器操作所耗费的时间为1。
2. 1级缓存,共有10个区,每个区内共有10个存储空间。
与1级缓存相关的操作共有如下几个:
a) 读取1级缓存,指令格式为L 1 x y,操作为将2级缓存中第 号空间开始的10个存储空间读取到1级缓存的第x个区内,这里0 ≤ x < 10,0 ≤ y < 100。
b) 写入2级缓存,指令格式为W 1 x y,操作为将2级缓存中第 号空间开始的10个存储空间改写为1级缓存的第x个区的内容,这里0 ≤ x < 10,0 ≤ y < 100。
所有1级缓存操作所耗费的时间为20。
3. 2级缓存,共有50个区,每个区内共有20个存储空间。
与2级缓存相关的操作共有如下几个:
a) 读取2级缓存,指令格式为L 2 x y,操作为将主存中第 号空间开始的20个存储空间读取到2级缓存的第x个区内,这里0 ≤ x < 50,0 ≤ y < 5000。
b) 写入主存,指令格式为W 2 x y,操作为将主存中第 号空间开始的20个存储空间改写为2级缓存的第x个区的内容,这里0 ≤ x < 50,0 ≤ y < 5000。
所有2级缓存操作所耗费的时间为100。
4. 主存,共有100000个存储空间。
输入文件
本题的输入文件仅包含一个正整数T(1≤ T ≤ 5),表示当前是第几组数据,数据内容见下一页。
输出文件
对于每组输入,你需要输出对应的缓存规划方案,每个输出文件的第一行包含一个整
数表示你的缓存规划方案的指令数,接下来若干行每行一条指令,格式如问题描述中所示。
评分标准
对于每组数据,我们设有一个基础时间,你所获得的分数由下式所确定:
min([totalscore*basetime/yourtime],totalscore)
其中totalscore是该测试点的总分值,basetime是该测试点的基础时间,yourtime是你在该
测试点的所有指令所用的时间之和。
数据规模和约定
本题共有5组数据,每组数据的内容以及分值如下:
1. 测试点1(分值15)
初始在内存的前2500个空间存放了50*50的矩阵,你需要将这个矩阵的转置存放
在其后的2500个空间内。basetime:100000
2. 测试点2(分值20)
初始在内存的前10000个空间存放了100*100的矩阵,你需要将这个矩阵的转置存
放在其后的10000个空间内。basetime:500000
3. 测试点3(分值20)
初始在内存的前5000个空间存放了两个50*50的矩阵,你需要将这两个矩阵的乘
积存放在其后的2500个空间内。basetime:2000000
4. 测试点4(分值20)
初始在内存的前10000个空间分别存放了50*100及100*50的矩阵,你需要将这两
个矩阵的乘积存放在其后的2500个空间内。basetime:8000000
5. 测试点5(分值25)
初始在内存的前20000个空间分别存放了两个100*100的矩阵,你需要将这两个矩
阵的乘积存放在其后的10000个空间内。basetime:40000000


分数概览:
张放:260 ==========================
范浩强:200 ====================
罗剑桥:200 ====================
黄纪元:200 ====================
(其他人最高150)

算法:
1.Hash(不要选错Hash(如何选错Hash请问何行舟))或KMP(如何用KMP请问张放)
2.平衡树、线段树(Trie)、(任何你能想到的数据结构)
3.这。。。你一定要注意到要输出行数!
我没有注意到输出行数,结果,导致
91分=========.
变成
0分
囧!
其他受害者:何行舟、黄纪元。。。。。。
只有张放看到了行数这个条件(膜拜)
这题的一般做法:
分治!
把一个大的矩阵的问题分成几个小的。
目的是把小的矩阵放进更快的缓存里。
高逸涵没有写标程。。。(或者说,只写了一个能得7分的标程)

三次考试的题目、数据及标程:
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/BJOI2011.zip
(不要给我发邮件了。。。邮箱都快爆了。。。)


  评论这张
 
阅读(1188)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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