瑞典阿姆
瑞典阿姆
全部文章
分类
题解(8)
归档
标签
去牛客网
登录
/
注册
瑞典阿姆的博客
全部文章
(共8篇)
官方题解——最简单的一道题
D - 最简单的一道题 解法是线段树,定义 为区间 到 满足( ,且对于位置 ,位置 到位置 的这段区间的最小值是位置 的值)的 的数目,每个区间保存区间最小值和 。询问时设一个当前值 ,初始为询问的值,当前区间左边界小于所求位置时,继续递归,大于所求位置时,判断区间最小值是否小于...
2020-05-23
2
725
官方题解——校车
G - 校车 出题人的标程有问题,我验题居然没发现,是我验题不认真了,背锅。。。抛开题目出锅,这个题目还是蛮简单的,出题人给的做法是离散化+差分,我现场写了个更加暴力的。本来是打算作为签到题之一的没想到演了各位大佬了,谢罪。出题人标程: #include<bits/stdc++.h> u...
2020-05-23
1
694
官方题解——完美的战役
F - 完美的战役 首先我们计算每个分支的战力值,考虑每个人对分支战力的贡献,可以得到如下公式: 将每个人的贡献加起来我们可以得到分支的战力值为: ,其中 为该分支所有人的战力和。 我们记 其中 由组合数公式 得 累加得 代入 得 两边同时...
2020-05-23
1
576
官方题解——无敌阿姨
按照题意模拟即可,看不懂就是出题人语文没学好。 附队友代码: #include <bits/stdc++.h> #include <cstring> #define MAXN 103 using namespace std; int a[MAXN]; int main()...
2020-05-23
3
710
官方题解——异或生成树
C - 异或生成树 树型 表示以 为根的子树能否组成 ,如果为 可以组成,如果为 无法组成。由于是异或操作,所以 的范围是。转移方程为 ( 为 的子节点); 从根 开始 遍历每一个子节点,每遍历完一个子节点更新一下当前节点的 值。 队友的代码: #include <...
2020-05-23
0
698
官方题解——中位因数
H - 中位因数 由于一个数字的所有因数是分布在 的左右两侧,而我们要求的是因数的中位数,也就是要求小于 而且能够整除的最大数字。首先我们用筛法算出 之内所有数字的因数个数,以及每个数字的最小质因子,如果一个数字的因数比较多,直接从 向下枚举找到第一个就是;如果一个数字的因数比较少,我们可...
2020-05-23
4
685
官方题解——烦人的依赖
B - 烦人的依赖 软件的依赖关系可以看作一个有向图,而软件安装顺序就是求有向图的一个拓扑排序。注意题目中要求按照字典序排序,因此拓扑排序中要用优先队列。对于字符串的处理,可以先映射成整数,再做拓扑排序。有的同学反映超时,可以试试看unordered_map,比map要少个log。 #includ...
2020-05-23
5
861
官方题解——拯救咕咕咕之史莱姆
A - 拯救咕咕咕之史莱姆 签到题,直接手动模拟即可,当然你喜欢用代码模拟也可以。 天数 大洞 小洞 消耗的HP 1 1 0 3 2 1 1 6 3 1 2 9 4 1 3 12 5 2 4 18 6 3 6 27 所以血量小于等于 都能进入城堡。 这个题...
2020-05-23
1
585