Capturing my Thoughts,
Hoping to Connect with Yours.

很伤心，为什么NOIP不能用 C++11……

CodeForces 510D Fox And Jumping：510D

0/1 分数规划是一种常见的模型：给你 n 个价值 $a_i$ 与 n 个代价 $b_i$，让你选出 m 个数字，使得 $ \sum \frac {a_i} {b_i} $ 最大。显然这种题目可以用二分，但是有一种更优秀的方法：Dinkelbach 迭代法。

做CF上的英文题真是不容易…… 题目链接 CodeForces 555B：Case of Fugitive

这题是XJOI上看到的……不过HDU上也有：折线分割平面

洛谷链接：P1577 切绳子

看到我写这么简单的题的题解不要奇怪，因为这题很坑……XJ一大堆dalao都已经被坑害了……

当我们取模的时候，被模数很大，无法直接计算其值，我们就会用取模运算的下面两个性质：

$$ (a+b) \bmod x=((a \bmod x)+(b \bmod x))\bmod x \ (a\ast b) \bmod x=((a \bmod x)\ast (b \bmod x))\bmod x $$

那么对于除法，是否也满足这个式子呢？

$$(a \div b) \bmod x=((a \bmod x)\div (b \bmod x))\bmod x$$

在数论中，对正整数 n，欧拉函数 $\varphi (n)$ 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 φ 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。（来自维基百科）

欧几里德算法（Euclidean algorithm）又叫做辗转相除法，用于求最大公约数。这个算法已经十分常见了。扩展欧几里德算法（Extended Euclidean algorithm）是欧几里德算法的扩展（废话……），这个算法在解不定方程的时候十分常见。

现在有N个数，分别为1到N，如果要问你这些数的所有排列中，从小到大数的第N个是多少，如何求解？

显然当N很小时直接写个模拟就可以了。但是这样写的时间复杂度至少是$A_N^N$，也就是$N!$，很容易超时。想想$13!$已经是6227020800了……有没有更快的方法呢？

线段树是非常基础的算法了……

线段树是一种二叉树，可视为树状数组的变种，最早出现在2001年，由程序竞赛选手发明。我们ZS老师说过：“所有可以用树状数组解决的题目都可以用线段树解决，但是部分线段数可以解决的题目却无法用树状数组解决。”由此可见线段树十分强大……