偶尔刷刷题

分类

题解(32)

/ 注册

全部文章（共4篇）

牛客OI周赛11-普及组-C-Colorful

题目大意：n个点，m条边，每条边有颜色，生成一棵树，要求边的颜色数最少，输出最小值。边多、点少，稠密图，但不能直接去重边，因为颜色是很重要的。因为颜色数量不超过12，那就用二进制存储颜色，输出的结果也是1到12之间！用邻接矩阵存储边，暴力枚举每种颜色是否选，时间复杂度，接着搜索判断是否连通。因为...

生成树洪水填充时间复杂度爆搜邻接矩阵搜索 fill 稠密图 flood 二进制

2019-08-23

2 801

牛客OI周赛11-普及组-B-GameWithNumbers

题目大意：判断2到m有多少个数字是合法的。对于给定的n个数，是合法的；其他数字若是合法，那么必须存在2到n-1的约数，且这些约数都是合法的。暴力求解：从小到大枚举2到m，如果约数都合法，标记该数字合法；如果遇到一个不合法的约数，则不标记合法。需要从小到大确定是否合法，保证用到的约数都是更小的、...

模拟筛法约数筛选法数学枚举时间复杂度

2019-08-23

0 723

牛客NOIP暑期七天营-普及组4-D火龙果画

题目大意：输入n个直角三角形，被第i个三角形覆盖，美观度增加，请问所有被覆盖的点中，最大美观度是多少？暴力70分，但不开long long就只有20了。数据很水，开了long long，边加美味度边统计最大值都有70（23行放到16行之后）！暴力做法，不需要多想：对于每个三角形，包含在里面的点全...

差分标记差分模拟时间复杂度思维前缀和几何

2019-08-22

2 964

牛客NOIP暑期七天营-普及组3-C区间中最多的数

题目大意：给定n个数，q次询问，每次问区间[l, r]直接出现最多的数字是什么？并列的话输出较大数。从数据范围看，O(qn)超时，O(qa)不超时。空间限制128M，开一个100*200000的数组刚好不超时。预处理每种数字出现的前缀和，对于每个循环，分别O(1)求出每种数字的数量，记录最优值...

模拟时间复杂度空间复杂度前缀和

2019-08-21

0 817