Von Brank

ba35f41bb0a9ae090ef81b9f5e9a06395b39bf7d90df296da5959d85553e6905d46b93cde6fa73b78dba8abbd54988eca2a66463f551e6d6e34ee2959cc585d571e46aae91b3396731a4303cad24947b228fff82936e1b666739d2c11cb5aa0a98bc3c6e5c5302bf3ffeb3ebb3fafbc39f1c84731f7d1aa553e421151a453d42c3ee4f8c63aa26dd28ca02871900dd80ff3fff81f0380a821e1a68b213fb2504e69e4125c5802de4620fa8439c3c30d18458c1837045389c388dc443bbb32b9a8100a52b100081996f9cbc1e01910f10f124c8f80c59a97a1692e0ac485c73ef5f83910141d9e4101a6a2922987153df75a5fc3dab8024510 ...

ba35f41bb0a9ae090ef81b9f5e9a0639d875ea69fe3eb31751cc3f2eba24cb51e400c3c12841d8a6164e87829aa2d26474328984ddcbf4f2d2b6e5dcdbeda8e993f99d89c67362034d00422f2fdd81af18d502927454eada2d0bd4586b5dca2feb2bb0f97705e85b923f1048761190cb0fa72b9a05adbe9281623b35c186f193b52c6305fbe60722b439bd94d09caa81c6726fd70c82fc4457b59888bb30487fad987125dc2417bf942d28288711537bc688d17d7309c893ad17955c9c4f0ccf02a6115f90d5b52a2223ab66b85cfcc3e1d775d1381476318a835815ec33e9ba7cad5f5d660f4e47e5a2af049138916aa424ed6a1e11221c8 ...

印象中之前每次复习扩展欧几里得算法时，Google到的大佬们对扩欧的解释常常晦涩难懂。因此，在这文章中，我将根据自己的理解，试图以一种优雅的方式解释扩展欧几里得算法，希望能够使读者对扩展欧几里得算法形成直观而专业的理解。 先决条件 欧几里得算法 在了解扩展欧几里得算法前，当然要先知道欧几里得算法是什么。 如果你还不会求GCD，请先到 这里 复习一下欧几里得算法。 1234567int gcd(int a, int b){ if (a % b) return gcd(b, a % b); else return b;} 裴蜀定理 裴蜀定理的描述是这样的： ∀a,b∈Z,∃(x,y)∈Z,∀a,b∈Z,∃(x,y)∈Z, \quad ∀a,b∈Z,∃(x,y)∈Z, s.t.ax+by=gcd(a,b)s.t. \quad ax+by=gcd(a,b) s.t.ax+by=gcd(a,b) ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b) 被称为裴蜀等式。 这里不多解释，知道有这个定理就行。 ...

树状数组或二元索引树（英语：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% ...

ba35f41bb0a9ae090ef81b9f5e9a06398b3c19e2a3a7df5891295294bafc0c9e7a8d8fce43bc22da6a11f5c124d97154423a38fc52c7a0cf2dad17239ed692876c4b89bfb8b6673eca553c6f86e8efd72b24bac2da1536bfc2b73fe7bfeae1fb4d1df8e3163ca027bb222dae7281a205e4d3869725f750c4f1f1d4135af61a63cbc6828909eba7ba43119529c8b2ec042318299558cc025d05385652da8db2fa90da62d59c66f1ed3fc7905e0badedccb660f3a1d2bcd5817f41ea0dc5cfc37e05f9dc0d6faf25ca5d83774ec337b2ad802e57ccfe167a970ccf9c6fd7742b2a427a6a4f4a6f01c32dcab56e47221f1925a0d7a6382382d1d ...

昨天接到一个需求，要求用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 ...

本文合作者：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 说明/提示 两组测试数据 ...

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 以人的肉眼看来，一棵树上任意两点的 LCA 位置是显然的，然而对于计算机来说，最朴素的算法便是遍历整棵树来寻找 LCA，当询问次数很多的时候，朴素算法的效率将非常低下。本文将介绍几种常见的快速求解 LCA 的算法。 模板题：洛谷 P3379 | [模板] 最近公共祖先（LCA） 题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M,SN,M,SN,M,S ，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N−1N-1N−1 行每行包含两个正整数 x,yx, yx,y ，表示 xxx 结点和 yyy 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 MMM 行每行包含两个正整数 a,ba, ba,b ，表示询问 aaa 结点和 bbb 结点的最近公共祖先。 输出格式 输出包含 MMM 行，每行包含一个正整数，依次为每一个询问的结果。 输入输出样例 输入 #1 123 ...

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 nlog⁡nn\log_{}{n}nlog​n 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 333 取模然后对 444 取模，两个操作就不能合并在一起做）。 加法线段树 模板题：洛谷 P3372 | [模板] 线段树 1 题目描述 如题，已知一个数列，你需要进行下面两种操作： 将某区间每一个数加上 kkk 。 求出某区间每一个数的和。 输入格式 第一行包含两个整数 n,mn, mn,m 分别表示该数列数字的个数和操作的总个数。 第二行包含 nnn 个用空格分隔的整数，其中第 iii 个数字表示数列第 iii 项的初始值。 接下来 mmm 行每行包含 333 或 444 个整数，表示一个操作，具体如下： 1 x y k：将区间 [x,y][x, y][x,y] 内每个数加上 kkk 。 2 x y：输出区间 [x, ...

本文合作者：laybxc 赛事信息 名称 出题人 开始时间 时长 官方题解 Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics) 4qqqqAkulyatAleks5dDebNatkhEndagorionGlebsHPKiKoSNebuchadnezzarNiceClockSiberianZloboberalexX512biectioncdkrotch_egorgrphilisaf27ismagilov.codemeshanyavintage_Vlad_Makeevvoidmaxwrg0ababd Mar/13/202117:05 (UTC+8) 02:30 Codeforces Round #707 Editorial A. Alexey and Train 题目 题目描述 从时间0开始出发，要依次经过在一条直线上的 nnn 个站点，问到达站点n的时间。 每个站点 iii 都有对应的时间 ai,bi,tia_i,b_i,t_iai​,bi​,ti​ 从站点 i−1i ...