答案只有一個(gè)

1、答案只有一個(gè)淺談問(wèn)答式交互問(wèn)題交互式問(wèn)題的分類(lèi)分類(lèi)依據(jù)：庫(kù)函數(shù)和選手程序的關(guān)系博弈式交互問(wèn)答式交互博弈式交互問(wèn)答式交互問(wèn)答式交互的邏輯模型最后的答案發(fā)現(xiàn)之旅我們的目標(biāo)把題目做對(duì)，拿到分?jǐn)?shù)。不管用什么方法，在題目允許的情況下完成此題把題目做好。用較好的方法把交互式題目做得簡(jiǎn)潔、漂亮。用合適的方法，找出那唯一可能的解。探討這一類(lèi)問(wèn)題的解決策略。觸類(lèi)旁通，爭(zhēng)取為其它問(wèn)題提供靈感。我們的工具解決問(wèn)題的兩種思路思路一：“篩”法一言以蔽之：減少答案的不確定性 ！提問(wèn)的選擇范圍：可能降低問(wèn)題不確定性的所有問(wèn)題。如何選擇提出的問(wèn)題：隨機(jī)選擇；平均信息量最大的;選最壞情況下篩去最多的；古老的分類(lèi)學(xué)界：動(dòng)物界門(mén)：

2、節(jié)肢動(dòng)物門(mén)綱：昆蟲(chóng)綱目：雙翅目科：蠅科 屬：蠅屬 種：家蠅結(jié)論：這是一只蒼蠅！思路二：構(gòu)造法構(gòu)造一種提問(wèn)題的序列，或者一種生成該序列的算法，按照這樣的序列提問(wèn)，找出唯一的符合題目意思的答案。這是一種“一開(kāi)始就有計(jì)劃的提問(wèn)方式”。兩種方法的比較篩法問(wèn)題規(guī)模：不能太大當(dāng)前可能為答案的各個(gè)元素之間的邏輯關(guān)系不明顯思維難度：小實(shí)現(xiàn)難度：大往往不能準(zhǔn)確估計(jì)最壞情況下提問(wèn)次數(shù)構(gòu)造法問(wèn)題規(guī)模：任意當(dāng)前可能為答案的各個(gè)元素之間有明顯的邏輯關(guān)系思維難度：往往不小實(shí)現(xiàn)難度：往往不大往往可以準(zhǔn)確估計(jì)最壞情況下提問(wèn)次數(shù)實(shí)戰(zhàn)：進(jìn)入問(wèn)題之旅要素題目的模型交互的方法評(píng)分的標(biāo)準(zhǔn)地下城市和太空站之謎模型相似交互方式相似推論：解

3、題策略相似？事實(shí)上：解題策略不相似！評(píng)分方式不相似！地下城市：M太空站：32768地下城市和太空站之謎的啟示不同的評(píng)分標(biāo)準(zhǔn)，將決定不同的解題策略的使用！以不同的標(biāo)準(zhǔn)來(lái)評(píng)判不同的算法，優(yōu)劣自然不同！多數(shù)派一個(gè)學(xué)校有奇數(shù)個(gè)學(xué)生，分成兩個(gè)不相交的團(tuán)體：多數(shù)派和少數(shù)派請(qǐng)你確定一個(gè)一定屬于多數(shù)派的學(xué)生。交互規(guī)則：給出學(xué)生編號(hào)，得到兩個(gè)學(xué)生是不是同一個(gè)團(tuán)體的信息。評(píng)分：在m次提問(wèn)后得到正確答案，一共有n個(gè)人。你的得分是min(n-m,0)的線性函數(shù)。警告：測(cè)試庫(kù)迫使你進(jìn)入最壞的情況，并且一旦你給出的學(xué)生可能屬于少數(shù)派，我們就生成一個(gè)這樣的例子作為本輪的測(cè)試數(shù)據(jù)。多數(shù)派問(wèn)題的解法一N=11少多解法一的分析得分：1優(yōu)點(diǎn)：簡(jiǎn)單，并且找出了每一個(gè)學(xué)生屬于哪個(gè)團(tuán)體。缺點(diǎn)：過(guò)于簡(jiǎn)單，沒(méi)有優(yōu)化。雖然找出了每一個(gè)學(xué)生屬于哪個(gè)團(tuán)體，但是題目并沒(méi)有要求我們這樣做。靈機(jī)一動(dòng)：不找出每個(gè)學(xué)生屬于哪個(gè)集合，僅確定一個(gè)屬于多數(shù)派的學(xué)生！多數(shù)派問(wèn)題解法二多數(shù)派問(wèn)題解法二不同組相同組調(diào)皮的小孩ABB=星星隊(duì)A=星星隊(duì)星星隊(duì)月亮隊(duì)否否月亮隊(duì)月亮隊(duì)是是星星隊(duì)星星隊(duì)是是星星隊(duì)裁判否是月亮隊(duì)裁判是否小結(jié)燦爛星河IOI2000 中等硬度IOI2002 Rods冬令營(yíng) 2002 太空站之謎冬令營(yíng) 2001 猜單詞游戲NOI 2002 調(diào)皮的小孩CEOI2001 多數(shù)派CEOI2001 Cha