gougou1019
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
1019[[BR]]Legendary Pokemon
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1230
[[BR]]6 2006-07-15 !08:16:14 !00:07.51 844K C++ glimpse[[BR]]
惭愧下，程序运行的很慢。可能跟我递归的时候传了很大的参数并且一点剪枝都没做有关。[[BR]] 不过总算是AC了，算是我见过算法最弱coding最强的博弈吧。[[BR]] 这道题的描述有很强的中学生气质，就是背景比较#•#￥，说荒诞太重了，但是就给人怪怪的感觉。[[BR]]题目是几十天前做的，有些 细节记不清了，回忆一下：[[BR]] 我们假设捕捉的人是M，Wild Pokemon是P。他们最多一共出手10次，M在奇数次出手，而P在偶数次出手。[[BR]]函数：next 三个参数： 第k轮，M的当前状态M，P的当前状态P[[BR]]1．如果k == 11，说明他们各自出了5次手，P将在这轮逃跑，所以找到的概率为0，直接返回0[[BR]]2． 如果 k为奇数，轮到M出手：[[BR]]3．先检查M的血量是否大于0（注意是大于）如果不是，说明M挂了，返回0[[BR]]4．枚举所有的攻击手法：通过一 个函数计算出第i种进攻打中P后，P的状态P’,在这种攻击以后，捉到P的概略p=next(k+1,M, P’)*accuray[i]+next(k+1,M,P)*(1–accuray[i]),将i种p中最大的那个记录为best[[BR]]5．尝试补血操 作，记补血后的M为M’。补血操作有两点要注意，一点是现有血瓶个数必须大于等于1，喝完之后，M’的血瓶数量要比M减1，M’的血量比M大200，但是 不能超过Master的最大血量上限。经过补血后抓到P的概率为p=next(k+1,M’,P),取best=max(best,p)[[BR]]6.枚举 各种球捕捉P。一共有6种球，假设M有第i种球，用函数计算cp，即Master用第i种球扑捉当前P的概率。记用过第i种球的Master为M’，M’ 和M的唯一区别就是第i种球少一个。p=cp+(1-cp)*next(k+1,M’,P)。best=max(best,p)[[BR]]7．Master 的操作都完成了，返回best，即在k轮M，P的状态下，Master能逮到Pokemon的最大概率。[[BR]]8．当k为偶数，Pokemon的操 作,best初始化1[[BR]]9．先检查P的血是否大于0（注意等于0，P也算挂了），都挂了，当然抓不到[[BR]]10．检查逃跑概略是否为1，如果是， 肯定就抓不到了，没有算下去的必要[[BR]]11．检查P是否在催眠状态，如果在催眠状态，记下一轮P的状态为P’，P’和P的区别在于：P’催眠剩余轮数 减一,如果P’的催眠剩余轮数为0，则下一轮P’不处于催眠状态。函数直接在这里就返回了next（k+1,M,P’）*(1-run[k/2])，其中 run是在第k/2轮逃跑的概略。[[BR]]12．然后大家一定要注意，如果P的血量少于等于150，并且P有血瓶，要先给P回血，而不是先扣除它中毒的附 加伤害。记P回血后的状态P’，P’的血为P加200，P’的血瓶比P少一个，p=next(k+1,M,P’),best=min(best,p)[[BR]]13． 如果k不需要回血，或者是没有血瓶了，记录P的新状态P’，看P中没中毒，如果中了，P’就扣掉毒性的附加伤害（可能有很多种毒性伤害哦，注意是哪种）， 这时候再判一下P’是否挂了，如果挂了返回0，P’中毒的状态要更新一下[[BR]]14．记Master被击中的状态M’，M’等于M的血量扣300。记 Pokemon混乱攻击到自己为P’2，P’2为P’的血量扣300[[BR]]15．看看P否出于混乱状态，如果处于混乱状态，P’和P’2的混乱状态都要 更新。p=(next(k+1,M’,P’)*0.3+next(k+1,M,P’)*0.7)*(1-confusion[被混乱的种类])+ (next(k+1,M,P’2)*0.3+next(k+1,M,P’)*0.7)*(confusion[被混乱的种类])，注意，怪物攻击自己也是 有准确率的，best=min(best,p)[[BR]]16.如果P不处于混乱状 态，p=next(k+1,M’,P)*0.3+next(k+1,M,P)*0.7,[[BR]]best=min(p,best)[[BR]]17.next 函数返回best*(1-run[k/2]),即怪物被捉到的最小概率[[BR]][[BR]] 剩下的大约就是M，P的状态设计了，我是写了两个struct。[[BR]] 有几个要注意的是：[[BR]] 1。混乱（催眠是混乱攻击的一种）和毒素攻击本身是不能叠加的，但是可以既中混乱又中毒素攻击。[[BR]] 2．混乱和毒素攻击是持续三个怪物行动周期的，以毒素攻击为例，在周期1攻击，怪物扣掉附加血量后，在第2,4,6三个周期，怪物都要再次扣掉附加的血 量。第7周期开始时解除（不能在第8回合解除，因为第7周期会有逮捕操作）。[[BR]][[BR]] 大致就是这样，罗罗嗦嗦说了这么多，想必大部分人也不会看吧，只是希望给wa的同学帮助。不过如果实在不能ac，说不定是我哪记错 了，98mail：kown,88mail： pieerepeng,我把ac的代码发给你。[[BR]][[BR]] 最后，说一下对这类题我的看法吧：这类题对于提高算法的能力没啥帮助。但它就像一个坎，如果不能迈过，总是会留下阴影。Coding的能力取决于做过最 复杂题目的难度。
----
这里的12．然后大家一定要注意，如果P的血量少于等于150，并且P有血瓶，要先给P回血，而不是先扣除它中毒的附加伤害。
可能不太准确，事实上放过来做也能AC
题目再这些方面确实说明得不太好
{{{
555 我是大土人……
终于AC…… define果然是不好的
顺便这题关于先补血/毒/死的顺序有很大歧义，不过似乎怎么理解都能AC
比如这个case
0 0 800
10 20 30 100 100
1
4
1 1 0 2 0
4
2 21 87
2 0 57
2 33 93
2 2 71
0 0 0
0.2572 <- xgy
0.2584 <- gougou
0.2581 <- watashi
三种不同的输出，但是我们都AC了
}}}1019
Legendary Pokemon
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1230
6 2006-07-15 !08:16:14 !00:07.51 844K C++ glimpse
惭愧下，程序运行的很慢。可能跟我递归的时候传了很大的参数并且一点剪枝都没做有关。
不过总算是AC了，算是我见过算法最弱coding最强的博弈吧。
这道题的描述有很强的中学生气质，就是背景比较#•#￥，说荒诞太重了，但是就给人怪怪的感觉。
题目是几十天前做的，有些 细节记不清了，回忆一下：
我们假设捕捉的人是M，Wild Pokemon是P。他们最多一共出手10次，M在奇数次出手，而P在偶数次出手。
函数：next 三个参数： 第k轮，M的当前状态M，P的当前状态P
1．如果k == 11，说明他们各自出了5次手，P将在这轮逃跑，所以找到的概率为0，直接返回0
2． 如果 k为奇数，轮到M出手：
3．先检查M的血量是否大于0（注意是大于）如果不是，说明M挂了，返回0
4．枚举所有的攻击手法：通过一 个函数计算出第i种进攻打中P后，P的状态P’,在这种攻击以后，捉到P的概略p=next(k+1,M, P’)*accuray[i]+next(k+1,M,P)*(1–accuray[i]),将i种p中最大的那个记录为best
5．尝试补血操 作，记补血后的M为M’。补血操作有两点要注意，一点是现有血瓶个数必须大于等于1，喝完之后，M’的血瓶数量要比M减1，M’的血量比M大200，但是 不能超过Master的最大血量上限。经过补血后抓到P的概率为p=next(k+1,M’,P),取best=max(best,p)
6.枚举 各种球捕捉P。一共有6种球，假设M有第i种球，用函数计算cp，即Master用第i种球扑捉当前P的概率。记用过第i种球的Master为M’，M’ 和M的唯一区别就是第i种球少一个。p=cp+(1-cp)*next(k+1,M’,P)。best=max(best,p)
7．Master 的操作都完成了，返回best，即在k轮M，P的状态下，Master能逮到Pokemon的最大概率。
8．当k为偶数，Pokemon的操 作,best初始化1
9．先检查P的血是否大于0（注意等于0，P也算挂了），都挂了，当然抓不到
10．检查逃跑概略是否为1，如果是， 肯定就抓不到了，没有算下去的必要
11．检查P是否在催眠状态，如果在催眠状态，记下一轮P的状态为P’，P’和P的区别在于：P’催眠剩余轮数 减一,如果P’的催眠剩余轮数为0，则下一轮P’不处于催眠状态。函数直接在这里就返回了next（k+1,M,P’）*(1-run[k/2])，其中 run是在第k/2轮逃跑的概略。
12．然后大家一定要注意，如果P的血量少于等于150，并且P有血瓶，要先给P回血，而不是先扣除它中毒的附 加伤害。记P回血后的状态P’，P’的血为P加200，P’的血瓶比P少一个，p=next(k+1,M,P’),best=min(best,p)
13． 如果k不需要回血，或者是没有血瓶了，记录P的新状态P’，看P中没中毒，如果中了，P’就扣掉毒性的附加伤害（可能有很多种毒性伤害哦，注意是哪种）， 这时候再判一下P’是否挂了，如果挂了返回0，P’中毒的状态要更新一下
14．记Master被击中的状态M’，M’等于M的血量扣300。记 Pokemon混乱攻击到自己为P’2，P’2为P’的血量扣300
15．看看P否出于混乱状态，如果处于混乱状态，P’和P’2的混乱状态都要 更新。p=(next(k+1,M’,P’)*0.3+next(k+1,M,P’)*0.7)*(1-confusion[被混乱的种类])+ (next(k+1,M,P’2)*0.3+next(k+1,M,P’)*0.7)*(confusion[被混乱的种类])，注意，怪物攻击自己也是 有准确率的，best=min(best,p)
16.如果P不处于混乱状 态，p=next(k+1,M’,P)*0.3+next(k+1,M,P)*0.7,
best=min(p,best)
17.next 函数返回best*(1-run[k/2]),即怪物被捉到的最小概率
剩下的大约就是M，P的状态设计了，我是写了两个struct。
有几个要注意的是：
1。混乱（催眠是混乱攻击的一种）和毒素攻击本身是不能叠加的，但是可以既中混乱又中毒素攻击。
2．混乱和毒素攻击是持续三个怪物行动周期的，以毒素攻击为例，在周期1攻击，怪物扣掉附加血量后，在第2,4,6三个周期，怪物都要再次扣掉附加的血 量。第7周期开始时解除（不能在第8回合解除，因为第7周期会有逮捕操作）。
大致就是这样，罗罗嗦嗦说了这么多，想必大部分人也不会看吧，只是希望给wa的同学帮助。不过如果实在不能ac，说不定是我哪记错 了，98mail：kown,88mail： pieerepeng,我把ac的代码发给你。
最后，说一下对这类题我的看法吧：这类题对于提高算法的能力没啥帮助。但它就像一个坎，如果不能迈过，总是会留下阴影。Coding的能力取决于做过最 复杂题目的难度。
这里的12．然后大家一定要注意，如果P的血量少于等于150，并且P有血瓶，要先给P回血，而不是先扣除它中毒的附加伤害。
可能不太准确，事实上放过来做也能AC
题目再这些方面确实说明得不太好
555 我是大土人……
终于AC…… define果然是不好的
顺便这题关于先补血/毒/死的顺序有很大歧义，不过似乎怎么理解都能AC
比如这个case
0 0 800
10 20 30 100 100
1
4
1 1 0 2 0
4
2 21 87
2 0 57
2 33 93
2 2 71
0 0 0
0.2572 <- xgy
0.2584 <- gougou
0.2581 <- watashi
三种不同的输出，但是我们都AC了