答案只有一個

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

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

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