“算法课笔记”
ACM程序课算法笔记9——计算几何入门
ACM程序课算法笔记9——计算几何入门 线段属性 1.给两条有向线段p0p1和p0p2，线段1是否在线段2顺时针方向？ 2.给两条有向线段p0p1和p1p2，线段2是左拐还是右拐？ 3.给两条有...
ACM程序课算法笔记8——二分答案
ACM程序课算法笔记8——二分答案 问题一：序列划分 问题描述： 给定n个正整数数组a，将这个序列从左到右划分成m段，使得每段至少有一个数；你需要让数字之和最大的那一段的数字和尽可能的小；求最大...
ACM程序课算法笔记7——母函数
ACM程序课算法笔记7——母函数 定义 母函数实际上就是一个多项式和其系数表达的关系， 对于多项式x2 + 2x + 1就是序列1 2 1的母函数 母函数的基础转化 问题 若有1克、2克、3克、...
ACM程序课算法笔记6——二分图匹配
ACM程序课算法笔记6——二分图匹配 前置定义 二分图(Bipartite Graph )：如果一个图的顶点可以分为两个集合X和Y，图的所有边连接的两个点都来自不同的集合，则称该图为“二分图”或...
ACM程序课算法笔记5——组合博弈
ACM程序课算法笔记5——组合博弈 问题引入 问题：一共有10张牌，你与一个人进行游戏，每次只能取走1或2或3张牌，谁取走最后一张，你是先手，如何获胜。 题解：根据以前的经验，我们能保证一轮取走...
ACM程序课算法笔记4——背包问题
ACM程序课算法笔记4——背包问题 基本模型 给你一个容量为V的背包和若干种物品，在一定的限制条件下（每种物品都占用一定容量），问最多能放进多少价值的物品。 最典型最基本的动态规划问题，DP问...
ACM程序课算法笔记3——动态规划
ACM程序课算法笔记3——动态规划 问题一：HDOJ2084——数塔问题 问题描述： 有一个数塔，从顶部出发，要求找到一条从顶部到底部的一条路径，使路径上的和最大 解题思路： 如果去掉左上方一条...
ACM程序课算法笔记2——递推求解
ACM程序课算法笔记2——递推求解 基本方法 确认：能否容易的得到简单情况的解？ 假设：规模为N-1的情况已经得到解决。 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种...
ACM程序设计课笔记1——贪心算法
ACM程序设计课笔记1——贪心算法 表面理解：在对问题求解的时候每次都选择对当前情况的最优解（多次的局部最优解）。 基本步骤 从问题的某个初始解出发。 采用循环语句，当可以向求解目标前进一步时...