解药,解题报告共4篇

解药,解题报告(共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()点击翻牌并判