标签:算法
传送门 题目: ①所有块之间能够相互到达,即使一个连通图 ②所有块有偶数个邻居 ③规定有n个块有4个邻居 每组测试给定一个n,问你怎么构造一个图。   思路:水题。我们先构造好一个边长为2的矩形,然后我们给该矩形右下角添加三个块就能表达一个“有四个邻居”的块。 1 #include &
题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。 n<=39   这个题目大家在学编程的时候都应该遇到过,但是不能够使用递归解法,因为如果使用递归,就会超出时间,算法的复杂度是2^n。因此这里采用迭代的解法
目录带花树匹配1.算法分析2. 算法模板3. 典型例题3.1 第一个应用3.2 第二个应用 带花树匹配 1.算法分析 2. 算法模板 #include<iostream> #include<cstdio> #include<cstdlib> #inclu
目录一般线段树与权值线段树1.算法分析1.1 一般线段树1.2 权值线段树2.板子2.1 线段树入门2.1.1 单点修改+区间查询2.1.2 区间修改+区间查询2.1.3 区间加乘操作2.1.4 区间染色2.2 权值线段树2.2.1 求第k大、前驱、后继等3. 例题3.1 线段树入门3.2
目录递推与递归1. 算法分析1.1 递推1.2 递归2. 例题2.1 递推2.1.1 思维递推2.2.4 思维最小步数2.1.2 dp类递推2.2 递归 递推与递归 1. 算法分析 1.1 递推     递推强调当前状态与前一个状态的关系,一种考察类似动态规划的思维处理,另一种考察思维:当
暴力算法 1. 算法分析     很多时候题目数据量不是很大的时候都可以暴力处理。 2. 例题 acwing116飞行员兄弟题意: “飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。已知每个把手可以处于以下两种状态之一:打开或关闭。只有当所有把手都打开时,冰箱才会打开。把
本文尽量避免数学公式,使用文字解释列生成算法的原理,争取让读者能形成直观上的理解。 为什么需要了解列生成算法的原理 列生成算法无法简单地调用第三方库来使用,必须根据具体问题,构造不同的算法模型。 只有了解了原理,才能在踩到各种坑时,有所针对地去优化各种细节。不然只能抓瞎或者抓腮。 列生成算
min-max容斥学习笔记 前置知识 二项式反演 [f(n)=sum_{i=0}^nbinom{n}{i}g(i)Leftrightarrow g(n)=sum_{i=0}^n(-1)^{n-i}binom{n}{i}f(i) ] 一些定义 (max (S),min (S))表示分别集
重返现世 kthmin-max容斥板子题 题目要求至少得到(k)种东西的期望时间,转换后是求得到全集倒数第(k)个获得的东西的期望时间,然后可以套式子了 [begin{aligned} max_k(S)&=sum_{varnothingnot=Tsubseteq S}(-1)^{|
一.题目: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 二.题目分析 拿到这个题目我们冥思苦想也没有想到一个好的想法,于是从最简单的找规律开始吧! 另台阶的级数为n,跳法的数量为ret. n=1, ret=1 n=
本文主要详细讲述常见的八种排序算法的思想、实现以及复杂度。   冒泡排序   要点   冒泡排序是一种交换排序。   什么是交换排序呢?   交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。   算法思想   它重复地走访过要排序的数列,一次比