一题组合
题目 设集合A={1,2,...,n}A=\{1,2,...,n\}A={1,2,...,n}，XXX和YYY均为AAA的非空子集，允许X=YX=YX=Y。XXX中的最大元和YYY中的最小元分别记为maxXmax XmaxX和minYmin YminY。求满足maxX>minYmax X \gt min YmaxX>minY的有序集合对(X,Y)(X,Y)(X,Y)的个数。 解答 解法一：正向思路 对于给定的max X = mmax\ X\ =\...
NOIP 模版总结
前言 NOIP 中有很多可以也是应该背会的模版，从数论，图论等等方面皆有很强的兼容性 先做一个简单的总结。其中的写法是我在写程序的过程中的写法。 小序 注重拆分程序，分解问题。 如下程序中： void init() 表示程序初始化 void getdata() 表示程序读入数据 void putdata() 表示程序输出数据 void work() 表示程序主要运行逻辑 结构与存取 图的边 struct Side { int _node; int node_; int next; int...
管道储液系统
测评请前往##Luogu## 题目背景 A 市有一个管道储液系统，每次可以用来存储很多 A 市生产出的一些有特殊性质的液体。 题目描述 管道系统一共有MMM条海拔水平一致的管道，每个管道都有一个容积ViV_iVi，管道由NNN个控制阀门 (编号为111至NNN) 相互连接。 由于一些原因，要使这些控制阀门在用管道互相连接后形成一棵或多棵树的结构。为了防止内部溶液流出，每条管道一定在两端各连接着控制阀门。 对于每条管道，都有一个允许的内部液体的相对压强范围[Bi,Ei](Bi≥0,Ei≥0)[B_i,E_i] (B_i \ge 0,E_i \ge...
函数零点
测评请前往##Luogu## 题目背景 二分法求解函数零点有着很多应用价值。 题目描述 给定精确度ξξξ,用二分法求函数f(x)f(x)f(x)零点近似值的步骤如下： 确定区间[a,b][a,b][a,b],验证f(a)⋅f(b)<0f(a)·f(b) \lt 0f(a)⋅f(b)<0。 求区间(a,b)(a,b)(a,b)的中点ccc. 计算f(c)f(c)f(c). 若f(c)=0f(c)=0f(c)=0,则 c 就是函数的零点; 若f(a)⋅f(c)<0f(a)·f(c) \lt...
王小二卖糖
...
割点
图的割点 在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。 核心思想 给每一个点一个访问顺序称为orderorderorder 在 dfs 过程中如果访问到了割点kkk则此时图会被kkk分为 2 部分：已访问的点和未访问的点 在未访问的点中至少存在一个点满足在不经过kkk的前提下再也回不到已经访问过的点 如果不是连通图，则需要遍历全部可能作为根的节点 [1]--[3] | | [4]--[2]--[6] | | ...
逛公园
##Luogu## 题目描述 ShortestPath DynamicProgramming NOIP 2017 D1T3 策策同学特别喜欢逛公园。公园可以看成一张NNN个点MMM条边构成的有向图，且没有自环和重边。其中111号点是公园的入口，NNN号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从 1 号点进去，从NNN号点出来。 策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到NNN号点的最短路长为...
扩展欧几里得
从欧几里得讲起…… 欧几里得的辗转相除法计算的是两个自然数 a 和 b 的最大公约数 g，意思是能够同时整除 a 和 b 的自然数中最大的一个。 两个数的最大公约数通常写成 GCD(a, b)，或者简写成 (a, b)。 (Greatest Common Divisor) 计算方法……辗转相除！ 作为数论中一个很基础的内容，它的形式很漂亮，代码也很干净。 gcd(a,b)=gcd(b,agcd(a,b) = gcd(b,a % b) gcd(a,b)=gcd(b,a 证明过程 令r=ar = a % br=a则有a=k×b+ra = k \times b +...
十七岁
...
