Ellipse 题目描述Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth..Look at this sample picture: An ellipse in a plane centered on point $O$ 2018-03-08 OI > Number Theory #Simpson's Rule
Clever Y 题目描述Little Y finds there is a very interesting formula in mathematics: $$X^Y \bmod Z=K$$ Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y 2018-03-08 OI > Number Theory #GCD-LCM #Multiplicative Inverse #Baby-Step Giant-Step
MathJax in WordPress BackgroundMathJax 允许我们在 Blog 中插入漂亮的数学公式。WordPress 里有许多 MathJax 插件,但大多都不尽如人意,总是缺少这样那样的功能。下面介绍一种不使用插件的方法,可以近乎完美地解决问题。 Steps 点击仪表盘左侧“外观”选项卡中的“编辑”选项,进入“编辑主题”; 在右侧的“主题文件”中,选择“主题页眉”(header.php); 找到其中的<he 2018-03-06 Coding > Blog Construction #WordPress
Ceizenpok's Formula 题目描述Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery - the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its va 2018-03-05 OI > Number Theory #GCD-LCM #Prime #Combinatorics #Chinese Remainder Theorem #Lucas's Theorem #Multiplicative Inverse
Strange Way to Express Integers 题目描述Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following: Choose $k$ different positive integers $a_1, a_2, 2018-03-04 OI > Number Theory #GCD-LCM #Chinese Remainder Theorem #Multiplicative Inverse #Bézout's Identity
Desert King 题目描述David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which ar 2018-03-03 OI > Number Theory #Minimum Spanning Tree #Fractional Programming
排序 题意概述给定一个$1$到$n$的全排列。有$m$次操作,每次操作将第$l$项到第$r$项之间的数按升序或降序排序。求所有操作完成后第$q$项的值。 数据范围:$1 \le n, m \le 10^5$。 算法分析用 set 维护所有有序的区间,每个区间用一棵权值线段树来维护。这样就把排序操作变成了区间的分裂与合并(即线段树的分裂与合并)。 看起来线段树的复杂度很玄学,但可以大致证明一下: 初始时 2018-03-03 OI > Data Structure #Segment Tree
Dynamic Rankings 题目描述The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have deve 2018-03-01 OI > Common Skill #Prefix Sum #Binary Indexed Tree #Persistent #Segment Tree #Binary-Search #Discretization
Template of Simplex Algorithm 任务给定一个$n$维向量$a$、一个$m \times n$的矩阵$b$和一个$m$维向量$c$。要求构造一个$n$维向量$x$,使得在满足 $$\forall i \in [1, m], \ \sum_{j=1}^n b_{i, j}x_j \le c_i$$ 的前提下 $$\sum_{i=1}^n a_ix_i$$ 最大。 接口int solve() 返回$-1$表示无解 2018-02-23 OI > Number Theory #Linear Programming #Template
Hide 题意概述有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。 数据范围:$1 \le N \le 10^5, \ 1 \le Q \le 5 \times 10^5$。 算法分析考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。 设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个 2018-02-20 OI > Common Skill #Lowest Common Ancestor #Tree #Centroid Decomposition #Priority Queue