解藥,解題報(bào)告共4篇

解藥,解題報(bào)告(共4篇)

Doubly-sortedGrid

GCJ09FinalProblemC

【簡要描述】

給出一個(gè)N*M的方格紙，在方格內(nèi)可以任意填寫字母a到z，但是必須保證，任意一行從左到右字母的字典序必須保證不降，同時(shí)任意一列也必須保證字典序不降。

現(xiàn)在一些格子已經(jīng)填上了一些字母，現(xiàn)在要求將剩余沒有填寫的空格子填滿，同時(shí)要使得整個(gè)方格紙上滿足雙調(diào)不降的要求。問總的方案數(shù)取模10007的值。

Smalldataset

N,M≤4

Largedataset

N,M≤10

【分析與算法設(shè)計(jì)】

看到這個(gè)問題當(dāng)然最簡單的想法就是搜索了。

不過，注意到每一個(gè)格子可以填26種不同的字母，所以簡單考慮就可以發(fā)現(xiàn)，對于即使單獨(dú)1*M的方格紙，可能填寫的數(shù)目也將達(dá)到O(26M)的規(guī)?！院唵蔚乃阉魇墙^不可行的。

但是，同時(shí)我們也可以注意到，其實(shí)我們在進(jìn)行搜索的時(shí)候進(jìn)行了很多的重復(fù)搜索，所以我們需要嘗試確立一些搜索的狀態(tài)來進(jìn)行記憶化搜索，或者進(jìn)行遞推。

算法1：

注意到在Small中，雖然總的方案數(shù)很多，但是注意到行數(shù)和列數(shù)都不是很大，因此我們可以嘗試進(jìn)行狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃。

沿用狀態(tài)壓縮動(dòng)態(tài)規(guī)劃的一般方法，我們記錄掃描線上的狀態(tài)進(jìn)行轉(zhuǎn)移。

如有圖所示，其實(shí)我們需要記錄的狀態(tài)僅僅是紫色格子

中的字母填寫情況，藍(lán)色格子中的已經(jīng)填寫過的字母情況我們其實(shí)就不用知道了——通過紫色格子已經(jīng)可以反映出藍(lán)色

格子的字母狀況了。

然后我們只要枚舉橘紅色格子填寫什么字母然后進(jìn)行狀態(tài)的轉(zhuǎn)移即可。

那么考慮紫色掃描線上的點(diǎn)只有O(M)，相應(yīng)的，狀態(tài)數(shù)

即為O(26M)，這在Small中，是完全可以接受的。

至于一些格子已經(jīng)填寫了一些字母，我們只需要在轉(zhuǎn)移

到具體的格子然后再進(jìn)行判斷即可，算法并沒有什么關(guān)鍵的轉(zhuǎn)變。

時(shí)間復(fù)雜度：O(NM26M

)

空間復(fù)雜度：O(NM+26M)

期望得分：Small通過

觀察到在Large中，雖然N和M仍然不大，僅僅10而已，但是，考慮到26個(gè)字母的可能填寫方案，顯然的，仍和關(guān)于字母具體信息的掃描線記錄方式都是完全行不通的。我們知道，記錄一個(gè)位置到底是什么字母，就需要花費(fèi)26的記錄代價(jià)，這是導(dǎo)致我們無法記錄信息的關(guān)鍵問題。

那么，我們能不能分離這一問題，并不去記錄某一個(gè)位置是什么字母，而去記錄每一種字母到底占了哪些位置呢？

顯然的！

算法2：

這里我們就需要利用到雙調(diào)有序這一重要性質(zhì)了。

如果在格子(x1,y1)內(nèi)的字母比(x2,y2)內(nèi)的字母字典序小，那么則必然有這樣的限制條件：x1≤x2，y1≤y2。

所以，對于字母c1，以及恰好比其大一個(gè)字典序位置的字母c2，其分界線一定是一個(gè)從左下角到右上角的連續(xù)折線，并且任意一點(diǎn)只會(huì)向上，或者向右：

如右圖所示，我們這里標(biāo)出了字母a，b，c下方的分界

線，注意這里字母c所在的格子并不是連通的，所以，字母c的分界線是存在一部分與b的分界線是重合的。而其實(shí)字母d的分界線是完全和字母c重合的。

字母e的分界線就是整個(gè)方格的下拐折線。

并且任意字典序大于e的字母的分界線都是與字母e重合的。我們不妨稱這樣的一條從左下角到右上角的折線為一

條路徑。

對于兩條路徑P1和P2，如果滿足兩條路徑不嚴(yán)格相交，并且路徑P1存在一部分嚴(yán)格的處在在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.種樹

【問題描述】

一條街的一邊有幾座房子。因?yàn)榄h(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號(hào)為1..n。每個(gè)塊的大小為一個(gè)單位尺寸并最多可種一棵樹。每個(gè)居民想在門前種些樹并指定了三個(gè)號(hào)碼b，e，t。這三個(gè)數(shù)表示該居民想在b和e之間最少種t棵樹。當(dāng)然，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是正整數(shù)，g(x)=xxmod1000，x，k是給定的數(shù)。我們要求的是這個(gè)不定方程的正整數(shù)解組數(shù)。

舉例來說，當(dāng)k=3,x=2時(shí)，分別為(a1,a2,a3)=(2,1,1),(1,2,1),(1,1,2).

【文件輸入】

輸入文件有且只有一行，為用空格隔開的兩個(gè)正整數(shù)，依次為k，x。

【文件輸出】

輸出文件有且只有一行，為方程的正整數(shù)解組數(shù)。

【樣例輸入】

32

【樣例輸出】

3

【數(shù)據(jù)范圍】

對于40%的數(shù)據(jù)，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;

寧波工程學(xué)院

XX～XX學(xué)年第一學(xué)期

電信學(xué)院

3D游戲設(shè)計(jì)與制作大實(shí)驗(yàn)報(bào)告書

題目：班級：學(xué)號(hào)：姓名：指導(dǎo)教師：日期：

目錄

1.系統(tǒng)分析.......................................................................................................................3

系統(tǒng)的功能.....................................................................................................32

系統(tǒng)設(shè)計(jì)思路.................................................................................................3.系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)...........................................................................................................4

函數(shù)功能及其核心代碼分析............................................................................4參考文獻(xiàn)..........................................................................................................................8附錄A系統(tǒng)使用說明.....................................................................................................8附錄B源程序代碼........................................................................................................8

1.系統(tǒng)分析

系統(tǒng)的功能

這是一款記憶翻牌小游戲，16張牌，單擊出現(xiàn)的卡片。相同的自動(dòng)會(huì)消掉。根據(jù)記憶將兩張相同的牌翻出，消掉?？简?yàn)的是你的瞬間記憶能力，根據(jù)記憶單擊它翻過的牌。游戲簡單好玩，相信你一定會(huì)喜歡的。

系統(tǒng)設(shè)計(jì)思路

此游戲一共有16張牌，8組兩張相同的牌，點(diǎn)擊一張牌，當(dāng)前牌翻開，當(dāng)點(diǎn)擊第三張牌的時(shí)候，前兩張牌相同的時(shí)候，前兩張消失，不同的話，就翻回來。時(shí)間100秒?？简?yàn)記憶力與敏捷度。

2.系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)

函數(shù)功能及其核心代碼分析

圖1流程圖

?

main()主函數(shù)

該函數(shù)是主函數(shù)。在主函數(shù)中，，調(diào)用start()開始游戲進(jìn)行翻牌，游戲結(jié)束輸出

所用的時(shí)間與結(jié)果。關(guān)閉游戲界面。

?

btnStart_click()點(diǎn)擊翻牌并判