聪明的质监员 vs 借教室

两题出自NOIP的肥常肥常肥肠经典的二分题目，学习二分时候，特别适合用来练手ヾ(•ω•`)o一、借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希

最大乘积 - 刺杀大使

这两题并不难，写这篇博客的原因是觉得这两题挺好玩的hhhhhhh最大乘积题目描述一个正整数一般可以分为几个互不相同的自然数的和，如 $3=1+2$，$4=1+3$，$5=1 + 4 = 2 + 3$，$6=1+5=2+4$。现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数的和，且使

蒙德里安的梦想 - 状压dp

状压dp好抽象，这题要是没理解的话，是真的难＞︿＜，但是这题又是一道非常非常非常经典的状压dp入门题。题目描述求把 $N * M$ 的棋盘分割成若干个 $1 * 2$ 的的长方形，有多少种方案。例如当 $N = 2$，$M = 4$ 时，共有 $5$ 种方案。当 $N = 2$，$M = 3$ 时，

最长上升子序列（LIS）问题总结

最长上升子序列 I题目描述给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数N。第二行包含N个整数，表示完整序列。输出格式输出一个整数，表示最大长度。数据范围$1 \le N \le 1000$，$-109\le$ 数列中的数 $\le 109$输入样例：73

平淡无奇的八数码难题

题目描述在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。例如：1 2 3x 4 67 5 8在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：1 2 34 5 67 8

食物链（带权并查集）

题目描述动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是”1 X Y”，表示X和Y是同类。第二种

位运算 + 递归 - 做题总结

题目描述给定一张 $n$ 个点的带权无向图，点从 ${0} \sim $ 标号，求起点 $0$ 到终点 $ - {1}$ 的最短 $Hamilton$ 路径。 $Hamilton$ 路径的定义是从 $0$ 到 $ - {1}$ 不重不漏地经过每个点恰好一次。输入格式第一行输入整数 $n$。接下来 $

最长回文子串（子序列）问题总结

最近在学习动态规划中遇到了这一类型的题目，这里将这一类型的所有题目总结了一下1、 最长回文子串1.1、题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad"输出: "bab"注意: &quo

Floyd-傻子也能看懂的弗洛伊德算法

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点