一题组合
题目 设集合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 value; }; 图的节点 struct...
管道储液系统
测评请前往##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...
扩展欧几里得
从欧几里得讲起…… 欧几里得的辗转相除法计算的是两个自然数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 + ra=k×b+r故可知r=a−k×br = a...
十七岁
...