题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1538
题目类型：
模拟
题意概括：
有1~n，n个海盗，m块金子，第n个海盗要提出一个分金方案，如果有一半以上的人同意，就立刻分金，反之就将这个人扔下水里，问所有情况都是最优解的情况下，要给第p个海盗分多少金？
解题思路：
如果只有一个人，所以肯定是给自己。
如果有两个人，那么自己将所有的钱都给自己，那么自己也同意分配，就可以得到一半以上的人的同意。
如果有三个人，第一个人知道如果不同意三号，那么自己绝对分不到钱，所以三号给多少，一号都会同意，有比没有强嘛，所以，三号只需要给一号一枚金币，剩下的全都收到囊中即可。
如果有四个人，如果第四个人死了，就像上种情况一样，所以只需要给二号一枚金币，就可以获得一半的支持。
........
以此类推，只要第n个海盗给自己编号奇偶性相同的海盗各一枚金币，即可。那么问题就来了...
如果得到的金子不够贿赂怎么办，也就是m*2<n的情况下，那就不是钱不钱的问题了，那就是小命要紧了，具体分析一下：
假如有500个海盗，但是只有100枚金币，怎么办？
对于201号来说，自己不能拿金币，并且把金币给除自己之外的其他奇数号海贼就能存活
对于202号来说，自己同样不能拿金币，并且吧金币给除了自己之外的其他偶数号海贼就能存活
对于203来说，至少需要102个人的支持，但是自己贿赂的拿金子获得的海盗加上自己，只能拿到101票，所以203必死，
对于204，如果自己死了，203必死，所以203一定会支持自己，所以自己吧金币分给之前的前200号偶数，一共可以得到100+1（203）+1（204），自己可以保证不死。
对于205号，204,203已经有了保全之策，所以他们是不会支持205的，所以205必死。
金币数量的不确定性:由上面的推理可知, 当n=2m+2时, 上一轮推理没有分到金币的人的金币数量首次具有不确定性, 并且在n>2m+2时, 这种不确定性一定会延续下去, 轮到因为n号决策者之前的一个人决策时, 那个人肯定分不到金币了, 所以在上一轮推理中没有分到金币的人的个数一定大于m。
综上所述就是该题的解题思路，非常感谢大神的解题思路，给我带来了太多的灵感，参考链接：
http://blog.csdn.net/acm_cxlove/article/details/7853916#comments
题目：
A Puzzle for Pirates
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 996 Accepted Submission(s): 384
All the pirates enjoy throwing one of their fellows overboard, but if given a choice they prefer cold, hard cash, the more the better. They dislike being thrown overboard themselves. All pirates are rational and know that the other pirates are also rational. Moreover, no two pirates are equally fierce, so there is a precise pecking order — and it is known to them all. The gold pieces are indivisible, and arrangements to share pieces are not permitted, because no pirate trusts his fellows to stick to such an arrangement. It's every man for himself. Another thing about pirates is that they are realistic. They believe 'a bird in the hand is worth two in the bush' which means they prefer something that is certain than take a risk to get more, where they might lose everything.
For convenience, number the pirates in order of meekness, so that the least fierce is number 1, the next least fierce number 2 and so on. The fiercest pirate thus gets the biggest number, and proposals proceed in the order from the biggest to the least.
The secret to analyzing all such games of strategy is to work backward from the end. The place to start is the point at which the game gets down to just two pirates, P1 and P2. Then add in pirate P3, P4, ... , one by one. The illustration shows the results when 3, 4 or 5 pirates try to divide 100 pieces of gold.
Your task is to predict how many gold pieces a given pirate will get.
#include<iostream> #include<cstdio> #include<ctime> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #define C 240 #define TIME 10 #define inf 1<<25 #define LL long long using namespace std; //保存2的幂 int fac[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; void slove(int n,int m,int p){ //金币够贿赂的情况 if(n<=2*m){ //不是决策者，而且奇偶性相同，都能被贿赂 if(n!=p&&(n%2==p%2)) printf("1\n"); //剩下的都是决策者拥有 else if(n==p) printf("%d\n",m-(n-1)/2); else //其余人分不到金币，他们的决策不影响全局 printf("0\n"); return ; } //这时候的不同在于决策者不能拿金币 else if(n==2*m+1){ if(p<2*m&&p&1) printf("1\n"); else printf("0\n"); return ; } int t=n-2*m,i; //这是刚好保命的情况，对于决策者来说，肯定没有金币 //对于其它人来说，要么肯定没有金币，要么可能没有金币，不确定性 for( i=0;i<14;i++){ if(t==fac[i]){ printf("0\n"); return; } } for( i=1;i<14;i++) if(t<fac[i]){ //决策者必死 if(p>2*m+fac[i-1]&&p<2*m+fac[i]) printf("Thrown\n"); else printf("0\n"); return ; } } int main(){ int t,n,m,p; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&p); slove(n,m,p); } return 0; }
