版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
解药,解题报告(共4篇)
Doubly-sortedGrid
GCJ09FinalProblemC
【简要描述】
给出一个N*M的方格纸,在方格内可以任意填写字母a到z,但是必须保证,任意一行从左到右字母的字典序必须保证不降,同时任意一列也必须保证字典序不降。
现在一些格子已经填上了一些字母,现在要求将剩余没有填写的空格子填满,同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。
Smalldataset
N,M≤4
Largedataset
N,M≤10
【分析与算法设计】
看到这个问题当然最简单的想法就是搜索了。
不过,注意到每一个格子可以填26种不同的字母,所以简单考虑就可以发现,对于即使单独1*M的方格纸,可能填写的数目也将达到O(26M)的规模——所以简单的搜索是绝不可行的。
但是,同时我们也可以注意到,其实我们在进行搜索的时候进行了很多的重复搜索,所以我们需要尝试确立一些搜索的状态来进行记忆化搜索,或者进行递推。
算法1:
注意到在Small中,虽然总的方案数很多,但是注意到行数和列数都不是很大,因此我们可以尝试进行状态压缩的动态规划。
沿用状态压缩动态规划的一般方法,我们记录扫描线上的状态进行转移。
如有图所示,其实我们需要记录的状态仅仅是紫色格子
中的字母填写情况,蓝色格子中的已经填写过的字母情况我们其实就不用知道了——通过紫色格子已经可以反映出蓝色
格子的字母状况了。
然后我们只要枚举橘红色格子填写什么字母然后进行状态的转移即可。
那么考虑紫色扫描线上的点只有O(M),相应的,状态数
即为O(26M),这在Small中,是完全可以接受的。
至于一些格子已经填写了一些字母,我们只需要在转移
到具体的格子然后再进行判断即可,算法并没有什么关键的转变。
时间复杂度:O(NM26M
)
空间复杂度:O(NM+26M)
期望得分:Small通过
观察到在Large中,虽然N和M仍然不大,仅仅10而已,但是,考虑到26个字母的可能填写方案,显然的,仍和关于字母具体信息的扫描线记录方式都是完全行不通的。我们知道,记录一个位置到底是什么字母,就需要花费26的记录代价,这是导致我们无法记录信息的关键问题。
那么,我们能不能分离这一问题,并不去记录某一个位置是什么字母,而去记录每一种字母到底占了哪些位置呢?
显然的!
算法2:
这里我们就需要利用到双调有序这一重要性质了。
如果在格子(x1,y1)内的字母比(x2,y2)内的字母字典序小,那么则必然有这样的限制条件:x1≤x2,y1≤y2。
所以,对于字母c1,以及恰好比其大一个字典序位置的字母c2,其分界线一定是一个从左下角到右上角的连续折线,并且任意一点只会向上,或者向右:
如右图所示,我们这里标出了字母a,b,c下方的分界
线,注意这里字母c所在的格子并不是连通的,所以,字母c的分界线是存在一部分与b的分界线是重合的。而其实字母d的分界线是完全和字母c重合的。
字母e的分界线就是整个方格的下拐折线。
并且任意字典序大于e的字母的分界线都是与字母e重合的。我们不妨称这样的一条从左下角到右上角的折线为一
条路径。
对于两条路径P1和P2,如果满足两条路径不严格相交,并且路径P1存在一部分严格的处在在P2的上方,则我们称P1=jtheninc(x,1shl(i-1));
fork:=x+1tox+(1shl(i-1))dod[i,j]:=d[i,j]+d[i-1,k]*p[j,k]/100;
d[i,j]:=d[i-1,j]*d[i,j];
end;
ans:=1;
fori:=2to1shlndo
ifd[n,i]>d[n,ans]thenans:=i;
end;
procedureprint;
begin
writeln(ans);
end;
begin
init;
main;
print;
end.
【方法二】分治
varn,p:longint;
a:array[0..1050,0..1050]ofextended;
f:array[0..15,0..1050]ofextended;
procedureinit;
vari,j:longint;
begin
readln(p);n:=1shlp;
fori:=1tondobegin
forj:=1tondobeginread(a[i,j]);a[i,j]:=a[i,j]/100;end;
readln;
end;
end;
proceduredfs(l,r,k:longint);
varzj,i,j:longint;
begin
ifk=0thenexit;
zj:=(l+r)div2;
dfs(l,zj,k-1);dfs(zj+1,r,k-1);
fori:=ltozjdo
forj:=zj+1tordobegin
f[k,i]:=f[k,i]+f[k-1,i]*f[k-1,j]*a[i,j];
f[k,j]:=f[k,j]+f[k-1,i]*f[k-1,j]*a[j,i];
end;
end;
procedurework;
vari,ans:longint;
begin
fillchar(f,sizeof(f),0);
fori:=1tondof[0,i]:=1;
dfs(1,n,p);
ans:=1;
fori:=2tondoiff[p,i]>f[p,ans]thenans:=i;
writeln(ans);
end;
begin
assign(input,'');reset(input);
assign(output,'');rewrite(output);
init;
work;
close(input);close(output);
end.
2.种树
【问题描述】
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号为1..n。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然,b
usingnamespacestd;
structddd{ints,e,v;}a[5005]={0},mid;
intn,m,ans=0;
boolv[30005]={0};
voidqsort(intl,intr)
{inti=l,j=r;
mid=a[(l+r)/2];
while(i||(a[j].e==&&a[j].s>n>>m;
for(i=1;i>a[i].s>>a[i].e>>a[i].v;
qsort(1,m);
for(i=1;i=a[i].s;j--){if(!v[j]){v[j]=1;t--;ans++;}
if(t==0)break;}
}
cout=2且k∈N*,x是正整数,g(x)=xxmod1000,x,k是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说,当k=3,x=2时,分别为(a1,a2,a3)=(2,1,1),(1,2,1),(1,1,2).
【文件输入】
输入文件有且只有一行,为用空格隔开的两个正整数,依次为k,x。
【文件输出】
输出文件有且只有一行,为方程的正整数解组数。
【样例输入】
32
【样例输出】
3
【数据范围】
对于40%的数据,ans
n-m+1tondo
Begin
forj:=1toans[0]doans[j]:=ans[j]*b[i];forj:=1toans[0]-1do
Begin
ifans[j]>=10then
begin
inc(ans[j+1],ans[j]div10);
ans[j]:=ans[j]mod10
End;
End;
whileans[ans[0]]>=10do
begin
inc(ans[0]);
ans[ans[0]]:=ans[ans[0]-1]div10;
ans[ans[0]-1]:=ans[ans[0]-1]mod10;end;
End
End;
ProcedureInit;
Begin
Readln(k,x);
End;
宁波工程学院
XX~XX学年第一学期
电信学院
3D游戏设计与制作大实验报告书
题目:班级:学号:姓名:指导教师:日期:
目录
1.系统分析.......................................................................................................................3
系统的功能.....................................................................................................32
系统设计思路.................................................................................................3.系统设计实现...........................................................................................................4
函数功能及其核心代码分析............................................................................4参考文献..........................................................................................................................8附录A系统使用说明.....................................................................................................8附录B源程序代码........................................................................................................8
1.系统分析
系统的功能
这是一款记忆翻牌小游戏,16张牌,单击出现的卡片。相同的自动会消掉。根据记忆将两张相同的牌翻出,消掉。考验的是你的瞬间记忆能力,根据记忆单击它翻过的牌。游戏简单好玩,相信你一定会喜欢的。
系统设计思路
此游戏一共有16张牌,8组两张相同的牌,点击一张牌,当前牌翻开,当点击第三张牌的时候,前两张牌相同的时候,前两张消失,不同的话,就翻回来。时间100秒。考验记忆力与敏捷度。
2.系统设计实现
函数功能及其核心代码分析
图1流程图
?
main()主函数
该函数是主函数。在主函数中,,调用start()开始游戏进行翻牌,游戏结束输出
所用的时间与结果。关闭游戏界面。
?
btnStart_click()点击翻牌并判
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 比亚迪购车定金合同模板
- 外籍员工合同模板
- 宅基地改造出售合同模板
- 工地用品配送合同模板
- 店面合同签署合同模板
- 货车电池租赁合同模板
- 朴邻租房合同模板
- 小区变压器检测合同模板
- 国有土地征收合同模板
- 挤塑板供货合同模板
- 4.1“涉险滩”与“啃硬骨头”
- RFJ05-2009-DQ人民防空工程电气大样图集
- 【课件】主动运输与胞吞、胞吐高一上学期生物人教版(2019)必修1
- 电子负载使用说明书
- 成人高等教育本科生学士学位英语水平考试大纲(非英语专业第二版)
- 银行入职申请审批表
- 精美句子仿写100例
- GB/T 35005-2018集成电路倒装焊试验方法
- GB/T 3414-1994煤机用热轧异型钢
- GB/T 24513.3-2012金属和合金的腐蚀室内大气低腐蚀性分类第3部分:影响室内大气腐蚀性的环境参数测定
- 2023年江苏省徐州市成考专升本英语自考真题(含答案)
评论
0/150
提交评论