NOIP模版总结
前言 NOIP中有很多可以也是应该背会的模版,从数论,图论等等方面皆有很强的兼容性 先做一个简单的总结。其中的写法是我在写程序的过程中的写法。 小序 注重拆分程序,分解问题。 如下程序中: void init()表示程序初始化 void getdata()表示程序读入数据 void putdata()表示程序输出数据 void work()表示程序主要运行逻辑 结构与存取 图的边 struc ...
管道储液系统
测评请前往##Luogu## 题目背景 A市有一个管道储液系统,每次可以用来存储很多A市生产出的一些有特殊性质的液体。 题目描述 管道系统一共有MMM条海拔水平一致的管道,每个管道都有一个容积ViV_iVi,管道由NNN个控制阀门(编号为111至NNN)相互连接。 由于一些原因,要使这些控制阀门在用管道互相连接后形成一棵或多棵树的结构。为了防止内部溶液流出,每条管道一定在两端各连接着控制阀门。 ...
函数零点
测评请前往##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( ...
王小二卖糖
测评请前往##Luogu## 题目背景 王小二的糖果店每天都在做着美味的糖果,今天他突发奇想,看着不同大小的盒子他生出了一个奇妙的想法。 题目描述 小二一共有NNN个不同大小的盒子,每个盒子有自己的长,宽,高。他想知道把这些盒子一个一个套起来,就像俄罗斯套娃一样,最多能套起来多少的盒子。 盒子不能旋转,一个盒子的宽大于另一个盒子就不能放入,不用考虑长宽互换。每个盒子中不可能同时放入222个独立的 ...
割点
图的割点 在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。 核心思想 给每一个点一个访问顺序称为orderorderorder 在dfs过程中如果访问到了割点kkk则此时图会被kkk分为2部分:已访问的点和未访问的点 在未访问的点中至少存在一个点满足在不经过kkk的前提下再也回不到已经访问过的点 ...
逛公园
##Luogu## 题目描述 ShortestPath DynamicProgramming NOIP 2017 D1T3 策策同学特别喜欢逛公园。公园可以看成一张NNN个点MMM条边构成的有向图,且没有自环和重边。其中111号点是公园的入口,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( ...
十七岁
5e15dcdb3bbbdb8d74e8dcafcadae52551c066d20e4ef052d985c24a93b467bd0169c6d9339b48e9e626e7659e0541c95cdc34129ad97eaeedbd03c186afa6a091ed194ff2503b68342795c4451358a509ada3b2904b0c4a6494466cd2d4390f36867 ...
二进制原码,反码,补码
原码,反码,补码 Emmm就是用来表示数字的啊…… 对于有符号数: 在二进制数前面加上一个符号位表示正负,0表示正,1表示负 规则 负数的反码求法: 符号位不变。 其他位取反。 负数的补码求法: 符号位不变。 其他位取反。 最后一位加1。 对于有符号数而言: 二进制的最高位是符号位:0表示正数,1表示负数; 正数的原码、反码、补码都一样; 负数的反码 = 它的原码符号位不 ...
进制转换
进制转换(最大支持62进制) 很久之前就一直想搞这个东西,一直没有做出来,今天心血来潮写了出来。 因为中间存储数据的是long long所以如果一个进制表达的数字超出范围就无法转换了 Code #include <bits/stdc++.h> using namespace std; class NumConversion { private: long long _ ...