2016 Multi-University Training Contest 7
HDU 5809 Ants
题意
- 给平面图上(N(N le 10^5))个点，任意两点均不相同。
- 如果从一个点出发，会走到距离最近的一个点，距离相同的情况下取(x)坐标最小的点，仍相同则取(y)坐标最小的点。
- 有(Q(Q le 10^5))次询问，每次选图上的两个点(包含在输入里)，问从两个点同时出发，最后能否相遇。
思路
- 如果最后能相遇的话，必然是(i)的最近点是(j)，(j)的最近点是(i)，这个用并查集维护即可。
- 最近点可以套(KD-TREE)模板求。
代码
HDU 5815 Golden Week
题意
- 给一棵(N(N le 1000))个点的树，每个点表示一个城市，其中节点1是首都。
- 有(M(M le 1000))个游客，每个游客从首都1出发到城市(C_i)，预算(B_i)。
- 现在要给每条边（路）设置花费，使得最后收益最大。
思路
代码
HDU 5816 Hearthstone
题意
- 炉石游戏，你的敌人剩(P(P le 1000))点血。
- 你的卡组一共有(N+M(N + M le 20))张卡，游戏开始前已打乱顺序，其中有(N)张A卡，可以再抽两张卡；(M)张B卡，可以对敌人造成(b_i)点伤害。
- 游戏开始时，你可以抽一张卡，求最后你能在本回合杀死敌人的概率。
思路
- 如果最后没有抽完卡组，则手上的牌必然都是B卡，也就是说可以先预处理出手上有(x)张B卡的方案数，然后再讨论有(x)张B卡能够斩杀敌人的情况。
- 用(f(i,j,k))表示一共抽了i张卡，手上有j张A卡，k张B卡的方案数，转移$$f(i+2,j-1,k+2)+=f(i,j,k)，k+2 le M f(i+2,j,k+1)+=f(i,j,k)*2， i-k+1 le N，k+1le M f(i+2,j+1,k)+=f(i,j,k)，i-k+2 le N$$
- 转移时注意边界条件，同时当抽了(N+M-1)时，要特判转移，因为这时候只能抽一张卡。
- (2^M)枚举B卡集合，求(g[x])表示用(x)张B卡能够斩杀敌人的方案数。
-
[P=sum_{i=1}^{N+M}{sum_{k=1}^{M}{f(i,0,k)g[k]k!(M-k)!inom{N+M-i}{M-k}}}$$当前$i=N+M$，需要特判，此时A卡可以不为0。 ]
-
[Ans = P / Q ]
代码
HDU 5819 Knights
题意
- 有(N(N le 1000))个骑士站在一条线上，每个骑士往(a_i(0-左，1-右))方向走，遇到边界0和N+1会改变方向。
- 当两个骑士相遇时，每个人有50%的概率打败对方。
- 求第(N_{th})骑士获胜的概率，即打败其他所有人。
思路
- 用(f[i][j])表示前i个骑士剩j个人往右走的方案数。
- 如果第一个骑士往左走，则马上会碰到边界往右走。所以初始时可以直接令(a[1]=1,a[n]=0)。
- 转移，若(a[i]=1)，则$$f[i][j]=f[i-1][j-1]$$若(a[i]=0)，那么第(i)个骑士会和前(i-1)中剩下的往右走的骑士战斗，结果要么这个骑士打败前面的所有骑士，最后走到边界变成往右走的骑士，要么被其中某个骑士打败，则$$f[i][j]=sum_{k=j}^{i-1}{f[i-1][k]} f[i][1] += sum_{k=1}^{i-1}{f[i-1][k]}$$注意这个求和是可以预处理的，所以时间复杂度为(O(n^2))
代码