【总结】北大2018冬令营题目&总结

6道题，6道与概率计数相关的题，6道都涉及998244353这个魔性数字的题

Day1

T1:

给出一颗n个节点的二叉树，每个叶节点有一个权值（权值均不相同），每个非叶节点有一个概率P，表示：该点的权值有P的概率为它所有子节点中的最小值，同时有（1-p）的概率为所有子节点的最大值。
现在将根节点所有可能的权值从小到大排序，设分别为 V1,V2,V3...Vm V 1 , V 2 , V 3 . . . V m
其一一对应的概率为 D1,D2,D3...Dm D 1 , D 2 , D 3 . . . D m
现在求：

分析：

40分算法： O(n2) O ( n 2 ) 暴力合并即可
特殊10分算法：因为树的形态随机，期望深度为log级，所以直接暴力枚举每个叶节点。
100分算法：把40分的用线段树启发式合并即可（有点卡常，很危险）。

T2:

有2*n张卡牌，其中n张为增益牌，卡的权值为 W1,W2,W3..Wn W 1 , W 2 , W 3 . . W n ，另外n张为战斗牌，卡的权值为 D1,D2,D3...Dn D 1 , D 2 , D 3 . . . D n ，保证所有 Wi,Di W i , D i 均为整数。从中随机抽取m张，使用其中的k张，使用规则为：每使用一张增益牌，所有战斗牌的权值乘上增益牌的权值，每使用一张战斗牌，即造成该牌的权值的伤害。
求所有情况下最大伤害之和mod 998244353。
数据范围：
多组输入数据
对于100%的数据， 1<Wi<109,Di<109 1 < W i < 10 9 , D i < 10 9
对于100%的数据， 2n≤3000 2 n ≤ 3000

分析：

Day1签到题，不难得到对于每种情况而言，先把能用的增益卡，按从大到小最多用k-1个，最后用尽量少的战斗卡，必然是最优策略。
按照这种策略，我们可以分开求抽到i张增益卡，m-i张战斗卡，将两者所有方案之和相乘，就得到我们需要的答案。
对于求用i张增益卡的所有情况的最大乘积之和，很容易计算，用一个背包加一个限制条件（不能超过k-1个）即可。
对于求用i张战斗卡的所有情况的最大和之和，相对要困难一些，不过对背包熟悉的同学也会觉得相当容易，我们只要按战斗卡的权值从小到大排序，假设当前求 dp[i] d p [ i ] ，枚举到的卡牌为 j j ，
若k-m+i<2，则dp[i]=D[j]∗C(j−1,i−1)dp[i]=D[j]∗C(j−1,i−1)
否则 dp[i]=D[j]∗C(j−1,i−1)+D[i−1] d p [ i ] = D [ j ] ∗ C ( j − 1 , i − 1 ) + D [ i − 1 ]
最后再 O(m) O ( m ) 枚举分别摸到i张增益卡，j张战斗卡的dp值，相乘之和就是答案

T3

本题代码量颇大，细节多，考场上无人得分（估计都觉得调第一题卡常更有趣）。
题目大意是一个类似于斗地主的游戏。
给出一些固定的手牌，假如你是地主，求在拥有这些牌的情况下，所有一定能打出春天（对方无论什么手牌，都无法出一张牌）的方案数(mod 998244353)，地主总牌数为20张。
具体出牌规则我记不太清，基本与斗地主想同，但有些出入。

分析：

这道题也没什么好说的，首先农民不可能有双王，也就意味着地主手上必有一王
然后分农民是否拥有炸弹这两种情况：
若农民有炸弹，那么地主必须先出一堆比他大的炸弹，最后一次性出完所有手牌。这种情况较少，很容易枚举出来
若农民无炸弹，也就意味着地主必须拥有从1到k的每张牌至少一张，再加上一王的约束，已经有14张牌确定了。最后6张暴力枚举，加一些剪枝，每种情况check一下即可。

Day2

T1：

我们知道求一个图的最大独立集问题是完全NP问题。尽管现在并没有严格的多项式复杂度的算法，但有很多近似多项式复杂度的算法。现在有一种算法是这样的：
随机得到一个从1到n的排列，从前向后处理，若当前位置的点可以加入我们目前的假设最大独立集，就加入它，否则忽略它，处理后一位。
求这样一种算法能得到最大独立集的概率 (mod 998244353)。
数据范围：
对于100%的数据，n≤20

分析：

Day2签到题
O(2n) O ( 2 n ) 复杂度记忆化搜索所有情况，每种情况表示：若为1，则该点选入当前假设最大独立集，若为0，则该点可能未访问，可能与当前的假设最大独立集矛盾。
每次枚举一个新加入的点，假设有m个可加入的点，其中能达到当前状态最大独立集（即局部最大独立集）的方案是加入点 a1,a2,...ak a 1 , a 2 , . . . a k ，其能达到局部最大独立集的概率分别为 d1,d2,...dk d 1 , d 2 , . . . d k ，当前状态能达到局部最大独立集的概率即为

T2：

猎人游戏，每个猎人有一个威胁值 Wi（Wi为正整数） W i （ W i 为 正 整 数 ） ，每个猎人死亡时，有 Wi∑j(存活)Wj W i ∑ j ( 存 活 ) W j 的概率打中i号猎人，随后i号猎人又会开枪，直到全部死亡。
现在由你来开第一枪，开枪的规则与猎人相同。
求1号猎人最后死亡的概率。
对于30%的数据， ∑Wi≤20 ∑ W i ≤ 20
对于50%的数据， ∑Wi≤5000 ∑ W i ≤ 5000
对于100%的数据, ∑Wi≤100000 ∑ W i ≤ 100000

分析：

这道题我目前仍不清楚正解。。。
据说要用到NTT什么的乱搞。。。。

T3:

在一棵树上，从x点出发，每次随机走一条相邻的边。有Q次询问，每次询问给出一个大小为k的点集，求能遍历完所有点集中的点的期望步数。
对于20%的数据，n≤5，Q≤5
对于另外10%的数据，保证k=1
对于100%数据，n≤18，Q≤5000

分析：

对于这道题，我终于能感谢感谢当时教练扔给我那一大堆概率题了，很容易发现，这道题应该是概率状压DP，但是不满足无后效性，怎么办呢。。。高斯消元（把转移方程当方程来解）。这和之前做过的一道概率题很像，因此我才能拿到10分。。30分的暴力写丑wa了。
正解有很多，但有一些也是用高斯消元做的。我印象很深刻，据说是CF之前有一次也有一个类似的题目，当时也是在树上做高消，但是要求复杂度只能有 O(n) O ( n ) ，因为是树，所以从后往前做就能在近似O(n)复杂度内通过（我还没来得及研究，这是大体思路）。

总结：

这次还好把大众分都拿到了，但有些关键的骗分没骗到，这也是遗憾。不过反正那些老师教练都没怎么看好我，也无所谓了。总之，这场比赛我个人认为不够全面，6道题全是计数类问题，对不擅长这类题目的同学很不友好（szp），不过也说明了一个趋势：北大正在努力地想出一些思维难度大的题目，而不是往年那些裸的数据结构题，但是可能由于准备不充分，或者他们认为计数类题目最能反映人的思维能力，这次的计数类题目制霸全场，但并不意味着计数类题目今后的考试仍然会如此热门。但是题目对思维的要求是明显在提升的。

最后

以上就是专一香水为你收集整理的【总结】北大2018冬令营题目&总结的全部内容，希望文章能够帮你解决【总结】北大2018冬令营题目&总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。