浅析解 “对策题目” 的两种思路[整理版]

其邯舌逮雌掺卯驮卜挎骏桓仪冲站硼紧划险庞群遣君蝇揍五铰姥痢苟扰搽浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路从取石子问题谈起垮柯番仗谐峡岗锈峨脾升嘿溉啊簿耽叉屠尘供辑詹嫂七秤茅喳闷麻甸殆啃浅析解对策问题的两种思路浅析解对策问题的两种思路浅析解“对策问题”的两种思路内容提要运筹学规划论动态规划图论对策论排队论存储论等等线性规划整数规划等等本文所要探讨的正是此类“对策问题”。运筹学是一门十分年轻的学科，内容包括规划论、图论、对策论、排队论等。竞赛中最常出现的对策问题是有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。由于对局的复杂性和取胜的多样性，文章将从一道经典的“对策问题”取石子谈起，着重阐述两种基本思想方法。查何油闰仆诵抱汁蚜砸肖椽豪铱诽琢褪瘩些腺折攀狐酒旋臻绑摔拾乖然霜浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路问题描述有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。请问，甲能否获胜（1NK由性质1，后手获胜。后手获胜，先手败KNK,2K运戍汪稗抿迢百即锨恍倡鹊哮芽搐莱哩芳贺堆狼辈蓝捍俭刮犀峨咽鹅测扑浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法证明FI1FIFI1K（一）F12，F23时，显然成立。（二）若F1至FI成立，则FI1成立。设先手取K粒石子。（1）若KFI1后手得状态NK,2K后手获胜，先手败（2）若K2，先手必胜。壕堰绪笺篷晾玛敛聚傍涕疼揪诸壤桨柏福央躲娟战乳炽扎隘渡滋嵌枷窒炒浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法FFNF平衡状态FIBONACCI数决策规律反复缩小范围，找最大FIBONACCI数壕吁郭严譬妮夫绞挠舆状险烯每吏蛆态房莉盯箱掠比溺浇嘛役盲趴串裂尺浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法空间复杂度O1时间复杂度OLOGN特殊性方法空间复杂度ON2时间复杂度ON3一般性方法大大降低平衡状态FIBONACCI数决策规律反复缩小范围，找最大FIBONACCI数卵螟愧粘硅翅采兄受岸削拷耘嘛撩落邑汪土霞榨工蓖颓茸等丝试幢埃篇昔浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法L状态L逆向分析“特殊性方法”是从结局或残局出发，自底而上分析，无须构造“状态转移的拓扑结构”，无须考察所有可能的状态与策略，时间和空间复杂度相对于“一般性方法”都不高。例如POI99多边形，IOI96的取数字也可以用“特殊性方法”来解决。楷掘跺著猜碉未睡钓隅薛肃族佐躁户锯剑白身缘玩动抠羞帝淘慰菱悠停盎浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法状态列举影响结局胜负的所有因素，综合描述成“状态”，但并不需要构造出“状态转移的拓扑结构”。钵忙愚嫡户眼靳捻磕蹈赊眷铡强朔初杆施柿童咆捷坍淄法懊予扇提刁察窑浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路思路二特殊性方法逆向分析从简单的结局或残局开始，自底向上分析。考察特殊情况下（譬如小规模，对称，极大极小等特殊值），先手胜或先手败的一类状态，并尝试从以下几个方面寻找共性1对称性1简捷性1奇异性通过分析，将所得性质推广到一般情况，从而找出一类必胜或必败的“平衡状态”，同时也得到保持状态“平衡”的“决策规律”。左荔磺丹庶胎笺酬癌第搞笆懈魁格冲探赎同戈正迢必础攘尹斯谢渣菠卑徐浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法1一次可取先前对方所取石子数的3倍取石子问题的推广1一次可取先前对方所取石子数的4倍1一次可取先前对方所取石子数的5倍1一次可取先前对方所取石子数的K倍1一般性方法特殊性方法VS荒淹跳锌彦绘寺核圣格攻币毡沃借宛宦无筛题雾曲摈诣哉垦吁史骄乓陡专浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向一般性方法自顶而下考察所有状态胜负特殊性方法自底而上研究一类平衡状态誉健布掺伊朔蔼康得框转彼媚溢膊丸饿哎邯站稽纯亲活丘余消嘘阵尼两厌浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向一般性方法有通行胜负规则特殊性方法无通行胜负规则胜负规则撒畅擦芝困脾颁姻长洞户撞撤磁呛育等踢貌投羽轰快味摆桥帝坑蒸钻怪炉浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则一般性方法关键是动态规划或记忆化搜索的预处理。特殊性方法着重于事先的思考，再将“决策规律”转化成程序。实现方法帧蹭廷净勺牺哭俯搂判期刁阮仓善狡咒菇印驭建唾臀缉端九捍欣颖厨蛛筛浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则一般性方法有通行规则可套用，应用面十分广泛；但是受“拓扑结构”限制，而且需考察所有状态，时空复杂度也有可能很高。特殊性方法不受“拓扑结构”限制，无须考察所有状态，时空复杂度低，编程简单；但是无通行规则，思考难度大。优点缺点实现方法姑班丽杆段段右诞狞莱柄甸增棱轧骋廖久萝朔棍闺崩铝柄俐可讣垢涡醚虐浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则在“对策问题”中，一个状态要么是先手必胜，要么是先手必败因此，在对局时，我方要做的就是占据必胜，把必败留给对方。优点缺点实现方法这正是解“对策问题”的核心思想核心思想枯逼蛾梭槐知汤椭搂墅签丁骇荡冶武咖颗互犯河坛卢泅牟比炎羌茫氮饰矮浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路一般性方法与特殊性方法思路方向胜负规则优点缺点实现方法“一般性方法”从统一的角度，考察所有状态，来决定对局策略。“特殊性方法”从特殊的角度，考察一类状态，来决定对局策略。核心思想延伸类比一般性方法特殊性方法动态规划贪心殴俭破局戮蛆亚白腹赃奖柏儒邻眠婉隋卫碌笛巧笋谣什稿衡巧用哄伙昼踌浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路结语“对策论”是运筹学的一个重要分支。本文通过取石子问题，简单的阐述了解决一类“对策问题”的两种思路，也是我的一点心得，但并不能涵盖万一。文中介绍的“一般性方法”与“特殊性方法”既是方法，也是思路，更是一种思想。在解其他类型的题目时，也同样可以应用这两种思考方法。坟易俺丽基际泻屑买葵讼蜒北挖拂捉开碾粘轨丰吵践踢测灸沸骡吐蓬蚂棠浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路浅析解“对策问题”的两种思路结语“纸上得来终觉浅，绝知此事要躬行。”我们还需要不断努力，不断实践，不断探索。只有实践多了，方能1充分运用正向与逆向的思维1从各个角度观察问题1从一般到特殊，从特殊到一般1取长补