2.3k 2 分钟

# 题目 # 题意 给定 t 个点,r 条道路,p 条航线,和一个起点,道路可互相到达,航线只能单向到达,且航线的权值可能为负数,问从起点到各个点的最小距离是多少?若不可到达输出 “NO PATH” # 思路 把所有道路相连的点组成联通块,给他们编上号,从起点所在的联通块往后跑一个拓扑排序,连通块内跑 dijstla,松弛时发现松驰的点和当前点不在一个连通块内,则把更新的点所在的联通块入度 - 1,大致思路是这样,但是还是有许多细节问题 为什么一开始要加入入度为 0 的点? 因为要保证拓扑序列的进行。假设 s 所在块编号为 a,a 连向块 c,块 b 连向块 c,且块 a 块 b...
4.6k 4 分钟

# 340. 通信线路 # 分层图做法 建 k+1 层图,相邻两层图之间权值为 0,代表免费升级,在一层图里面跑就去找最大值,最后的答案就是第 k+1 层的 dis [n] 也就是 dis [(k+1)*n],注意的是这样的做法只有在边数大于 k 时成立,当全部边都可以免费升级时,会出现问题,还没有跑到最后一层图就到达终点了,这时就会往回跑,导致边权增加,就会出错,所以需要把层与层之间的终点连接起来,使它们可以免费互相到达 #include <bits/stdc++.h>#define debug...
1.1k 1 分钟

# __int128 C++ 支持的最大数据类型就是 longlong,再大就会爆掉,所以出现了__int128 类型,默认 gcc 是不支持编译的,但是在各大 OJ 上是可以运行的,__int128 不支持 cin、cout,所以需要自己写读入打印函数,也就是传统的快读快写 #include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; void read(__int128 &x){ int y=1;x=0; char...
3.1k 3 分钟

# Early Orders # 题意 n 个数从中找出一个包含 1-k 的字典序最小子串,注意子串可以断开,但是相对顺序不能变 # 题解 求得是字典序最小的子串,用一个单调栈维护,从栈底到栈顶依次表示子串的从前到后,为什么用栈呢?考虑子串的先后性,必须先把后面的更新了才能更新前面的,如何维护栈呢?对于栈顶元素,从左往右遍历的过程中如果这个数字比栈顶数字小,而且右面还有栈顶数字,那就可以出栈,还有就是当栈内有一个元素了,这时就不能再往里面塞这个元素,搞一个标记数组标记栈中是否有这个元素 # CODE #include <bits/stdc++.h>#define ios...
1.5k 1 分钟

# B 比武招亲(上) # 题目大意 给定 n,m,每次从 1-n 中挑选出 m 个数,可以重复挑选,挑选出的数的贡献值等于排序后最大值减去最小值,挑选的序列不同当且仅当两个序列排序后不同,求所有可能的序列的总贡献值? # 解法 可以枚举贡献值,差值一共有 n-1 种,差值固定了,也就是在 m-2 个空位中随意放置 [min,max] 的数,这里有一个坑,也不是随便放的,因为要求排过序后序列不同,也就是放置要求是单调不减,于是可以把 + 1 看成一个隔板,就是在 m-2+1 个隔板中放置 d (差值) 个隔板,可是隔板可以连续放置,所以放置一个隔板后空位就会增多!所以答案不是 C...
1.2k 1 分钟

整数分块可以以 log (n) 的时间复杂度内求出∑i=1n⌊n/i⌋{\sum_{i=1}^n\lfloor n/i \rfloor}∑i=1n​⌊n/i⌋ # 小 G 的约数 # 解法 单纯求 F (n) O (n) 求出,现在求∑i=1nFi\sum_{i=1}^nF_i∑i=1n​Fi​,可以换种思路,从个体对整体的贡献下手,对于每一个约数求有这个约数的所有数数量,显然是 n/i 个,然后乘上 i,那么问题就转化为了∑i=1n⌊n/i⌋∗i{\sum_{i=1}^n\lfloor n/i \rfloor*i}∑i=1n​⌊n/i⌋∗i,很明显的整数分块模板,什么是整数分块,考虑...
2.4k 2 分钟

# bitset # 用途 这个东西相当于一个 bool 数组,int 是 32 位表示一个数,而这个 32 位表示 32 个数,每一位只能存 1 或者 0,这就使得可以开的空间是 int 的 32 倍,时间复杂度为(位数)N/W (计算机常数一般为 32),而访问其中某一位时间复杂度为 O (1),这个的用处多用于数组开不下 1e9 以上的空间,用 unordered_map 插入时复 O (logn) 级别,就可以用 bitset 优化时间为 O (1) # 定义与初始化 使用 bitset 类型需 #include<bitset> bitset...
3.1k 3 分钟

# P1197 [JSOI2008] 星球大战 # 题意 n 个星球,m 条边,k 此摧毁,每次都会摧毁一个星球,摧毁一次求一次联通块,没摧毁时也要输出一次 # 解法 求联通块有两种方法 利用 dfs 或者 bfs 从每一个点出发,把能到达的点都标记,每一个点都走一次,时间复杂度为 O (n), 使用并查集,单独 n 个点联通块就是 n 个,当两个点连接起来并且这两个点分别属于两个不同的联通块时,把他们合并成一个集合,联通块数量 - 1,时间复杂度差不多等于边的数量,>O...
1.3k 1 分钟

种类并查集可以解决多种关系的问题,比如两个人不是朋友的关系,其思想是多开几倍的空间,假如有 n 种关系,就开 n 倍的空间,然后用 + n 来表示两个不同集合的关系 # 食物链 P2024 链接:https://www.luogu.com.cn/problem/P2024 开 3 倍空间维护 3 个集合,分别表示 A、B、C,例如 1 和 2 是朋友,那就把 3 个集合中的 1 和 2 合并,1 吃 2,就把 A 集合中 1 和 B 集合中的 2 合并,B 集合中的 1 和 C 集合的 2 合并,C 集合的 1 和 A 集合的 2 合并,再来一个 2 吃 3,这样一来 C 中的 3 和 A...
1.7k 2 分钟

题目链接 # 题目描述 # 题目大意: 有 n 种不同数量的细胞,每一个细胞每一秒都会分裂出一个新的,现在要把某一种细胞平均分到 m1m2 个容器里面,问选一种细胞,使得等待的时间最短,如果无法均分到容器中,就输出 - 1 # 做法 要均分就表示 Sit%m1m2==0 求 t 的最小值,看一下数据范围发现 m1 比较小,而 Si 很大,分别对 Si 和 m1 分解质因子,只要 m1 中的每一个质因子 Si 中都有,那么 Si 就可以通过分裂均分到 m1m2 中,因此不需要把 Si 的所有质因子都找到,只需要找到小于等于 m1 的所有质因子即可,因此时间复杂度就是 n*3e3 就是...
1.3k 1 分钟

# B 二进制 题目链接: https://ac.nowcoder.com/acm/contest/8564/B 单纯与或者单纯或单纯异或都支持交换律,但是他们放在一起就不支持交换律了,比如 1 先和 0 与再和 1 或结果是 1,但是 1 先和 1 或再和 0 与结果就不一样,可以设两个数,一个所有位都是 0,一个所有位都是 1,把这两个分别进行上述操作,最后得出来的结果按位对比,如果 0 变成了 1 且 1 变成了 0 则这个位肯定是异或 1,如果 0 变成 0 且 1 变成 0 则这一位是与 0,如果 0 变成 1 且 1 变成 1 这一位肯定是或...
6.5k 6 分钟

凸包(百度百科): 讲解凸包之前先讲解一下极角排序、叉积 # 叉积 就是数学上的叉乘,两个向量叉乘,有正有负,相乘的两个向量前后顺序颠倒符号相反,乘出来的的结果也是一个向量,值等于以这两个向量作为平行四边形的两条边长的面积,方向指向与两个向量垂直的方向,右手定则,拇指指向 x 轴弯向 y...
3.9k 4 分钟

# A. Cards for Friends 给一个宽度和一个长度的蛋糕,只有为长或宽为偶数时才能切一刀数量乘以 2,问给定尺寸的蛋糕能否分够 k 块。 分别对宽和长除 2,只要是偶数就除,看看能除几次,得到两个次数相乘就是能分的最大数量,和 k 比较一下 #include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;typedef long long ll;const int SUP=0x800000;const int...
6.2k 6 分钟

朴素版的线段树只能实现单点修改区间查询,修改和查询的时间复杂度都是 O (logn) # 懒标记问题 加上懒标记后的线段树就可以实现区间修改了,比如我要把 [a,b] 的值加上 k,肯定不会傻到 n 次单点修改,是个人都会想到假如递归到一个包含在 [a,b] 的区间时就不用继续往下递归了,直接告诉这个区间的管理员,把这个区间的和直接给修改了,但是假如你上面第一次增加时增加区间为 [c,d],并且区间 [c,d] 是包含在 [a,b] 中间的,现在又要在 [e,d] 增加 k,e>c 的,这个时候你就会发现 [e,d] 这个区间增加了两次,因为第一次增加时你根本没有递归到...
2.1k 2 分钟

# 2020 年度总结 转眼间已是 2021,想一想我的大学生活已经过去将近一半,真是快呀!总结一下我的 2020 年叭~ # 成就 ACM 天梯赛 (铜奖) CCPC 省赛银奖 CET 成绩还没出,不过感觉是考的不错 体测 79,已经非常满意了,只要过了 75 就满足了~ 学业 比较满足了,相比于上学期确实进步了好多,可能是因为新图书馆建好了的缘故叭~ # 想说的话 # 寒假 ​ 2020 年寒假在家,对视频剪辑,PS,特效制作兴趣比较大,就学了十多天吧,当时还去淘宝上买了好几个教学视频呢,现在都还在百度网盘存着,就是做特效的时候才发现 AE 对电脑的配置需求太大了!5...