【OI考古】图论 | 强连通分量 SCC | 缩点
简介
强连通分量(Strongly Connected Components)指有向图 GGG 中的极大子图,其满足子图内所有顶点都可以互相到达。
强连通分量是有向图 GGG 上的一种等价关系,每个 SCC 可以缩成一个点,便于后续的处理。
顺便吐槽一下最近在学校学的图论:把“连通分量”称为“连通分支”我忍了,把“二分图”称为“偶图”我也忍了,把“二叉树”叫“二元树”是什么鬼。虽然在图论学界术语不统一的背景下,对对象的称呼仅仅是习惯问题,但血压依然上来了((
模板题 | P3916 | 图的遍历
题目描述
给出 NNN 个点, MMM 条边的有向图,对于每个点 vvv ,求 A(v)A(v)A(v) 表示从点 vvv 出发,能到达的编号最大的点。
输入格式
第 111 行, 222 个整数 NNN , MMM 。 接下来 MMM 行,每行 222 个整数 UiU_iUi , ViV_iVi ,表示边 (Ui,Vi)(U_i,V_i)(Ui,Vi) 。点用 1,2,⋯ ,N1, 2, \cdots , N1,2,⋯,N 编号。
输出格式
NNN 个整数 A(1),A(2),⋯ , ...
【OI考古】基础算法 | 高精度计算
高精度计算(Arbitrary-Precision Arithmetic),也被称作大整数(bignum)计算,运用了一些算法结构来支持更大整数间的运算(数字大小超过语言内建整型)。
先决条件
快读
C++重载运算符
高精度算法
模板题:洛谷 P1932 | A+B A-B A*B A/B A%B Problem
求 A、BA、BA、B 的和差积商余!
题目描述
两个数两行
A BA \ BA B
输入格式
五个数
和 差 积 商 余
输出格式
输入输出样例
输入
1211
输出
1234520110
说明/提示
leng(A),leng(B)<=104leng(A),leng(B)<=10^4leng(A),leng(B)<=104
A,B>0A,B>0A,B>0 每个点 3s3s3s。
解决方案
原理
用数组模拟高精度类型,如1024可以表示成:
123456789索引:+---+---+---+---+---+| 0 | 1 | 2 | 3 | 4 |+---+---+---+---+---+内容:+---+---+---+---+---+| ...
蓝桥杯2021省赛游记 | C/C++ | 大学A组
蓝桥杯2021省赛游记
Bullet Journal | 子弹笔记 | 2021
VonBrank的2021年度子弹笔记
HIT | 集合论与图论 | 课程笔记 | 2021春季
哈工大-离散数学引论-课程笔记
【OI考古】数论基础 | 扩展欧几里得算法
帮助你对扩欧形成直观而专业的理解
【OI考古】数据结构 | 树状数组
树状数组或二元索引树(英语:Binary Indexed Tree,Fenwick Tree),是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。
树状数组的元素所管理的序列结构如下图所示:
树状数组(单点修改)
模板题:洛谷 P3374 | [模板] 树状数组 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
将某一个数加上 xxx
求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,mn,mn,m ,分别表示该数列数字的个数和操作的总个数。
第二行包含 nnn 个用空格分隔的整数,其中第 iii 个数字表示数列第 iii 项的初始值。
接下来 mmm 行每行包含 333 个整数,表示一个操作,具体如下:
1 x k 含义:将第 xxx 个数加上 kkk
2 x y 含义:输出区间 [x,y][x,y][x,y] 内每个数的和
输出格式
输入输出样例
输入
12345675 51 5 4 2 31 1 32 2 51 3 -11 4 22 1 4
输出
121416
说明/提示
【数据范围】
对于 30%30\%30% ...
HIT | 工科数学分析 | 课程笔记 | 2021春季
哈工大-微积分B-课程笔记
利用Sympy求解常系数微分方程
昨天接到一个需求,要求用Python实现求解常系数微分方程,虽然后来咕掉了,但是让我发现了Sympy这个科学计算库竟然有如此神奇的功能。本文将介绍如何用Sympy解决初值问题。
先决条件
Anaconda先决条件
我们强烈建议您使用免费的Anaconda Python发行版,该发行版为您处理如Numpy, Sympy, Scipy等软件包依赖项提供了一种简便的方法。
你可以参考 这篇文章 来部署Anaconda。
Sympy先决条件
SymPy是一个符号计算的Python库。它的目标是成为一个全功能的计算机代数系统,同时保持代码简洁、易于理解和扩展。支持符号计算、高精度计算、模式匹配、绘图、解方程、微积分、组合数学、离散数学、几何学、概率与统计、物理学等方面的功能。
在开始用Sympy求解微分方程之前,不妨先入门一下Sympy。
求微分方程通解
以初值问题:
y′′+2y′+2y=xe−x,y(0)=y′(0)=0y''+2y'+2y=xe^{-x}, \quad y(0)=y'(0)=0
y′′+2y′+2y=xe−x,y(0)=y′(0)=0 ...
【Codeforces】 题解 - Round 709 (Div.2)
本文合作者:laybxc
题解持续补充…
赛事信息
名称
出题人
开始时间
时长
官方题解
Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)
Aleks5dAndreySerguninDiegogrcGolovanov399KANamethyst0
Mar/21/202121:20 (UTC+8)
02:15
Codeforces Round #709 Editorial
A. Prison Break
题目
题目描述
给出 a×ba \times ba×b 的网格,问最少去掉多少条边,可以使得所有格子和外界连通。
输入格式
一行一个整数 t(1≤t≤100)t(1 \leq t \leq 100)t(1≤t≤100) ,表示数据组数。
第二行两个整数,表示参数 a,b(1≤a,b≤100)a,b(1 \leq a,b \leq 100)a,b(1≤a,b≤100) 。
输出格式
一个整数,表示答案
输入输出样例
输入
12322 21 3
输出
1243
说明/提示
两组测试数据 ...