竞赛讨论区 > 【题解】牛客网NOIP赛前集训营-普及组(第五场)
头像
Key酱不是喵
编辑于 2019-04-19 15:41
+ 关注

【题解】牛客网NOIP赛前集训营-普及组(第五场)

A体积数
因为要求 b ≥ 2,所以 a 一定小于等于 n0.5,所以可以枚举 a
注意两点: 运算过程可能会爆 int 要去重(开个数组就可以了)


B故事王
大模拟题
每一个评委的给分有 n! 种,因此局面总数只有 (n!)m
枚举所有的情况然后统计就可以了 next_permutation
注意会爆 int


C二叉树
两个点 u 和 v 在先序遍历中的顺序只和 lca 有关:
1. 如果 u 是 v 的祖先,那么 u 一定在 v 前面(反过来同理)
2. 如果最近公共祖先 f ≠u,v,那么哪个在左子树哪个就先
因此随机交换中,对于第一种情况,不改变 u 和 v 的顺序,第二种情况,各 有 50% 的概率改变/不改变
因此只要判祖先关系就可以了
判祖先关系可以用 DFS 序,即每一个子树在 dfs 序对应了一个区间,只要判 这些区间是否包含就可以了


D游戏
敌人肯定按照血量顺序死亡的,把所有敌人按照血量升序排序
则第 i 个敌人会受到 K+sum{j < i} a[j] 点伤害,这个敌人会死亡当且仅当这 个数值大于等于 h[i]
因此考虑 dp[i][j],表示当前考虑了前 i 个敌人,所有加入游戏的敌人的攻击 力的和为 j
则第 i+1 个敌人能加入游戏当且仅当 j+K >= h[i+1],直接转移即可
第二维只需要开到 max h[i],即 1e5 就可以了


std:

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐