CoolGuang!

分类

atcoder(4) kuangbin刷题记录(9) Task In College(1) 二分查找(5) 位运算(2) 动态规划(10) 博弈论(1) 图论(27) 备忘录(2) 大模拟(7) 字符串算法(3) 思维锻炼(14) 搜索(9) 数据结构(10) 数论(6) 暴力与随机数(3) 未归档(8) 矩阵练习(6) 组合数学(3) 计算几何(1) 计算机知识/辅助工具(1) 贪心算法(4) 路漫漫其修远兮(2) 题解(27)

/ 注册

全部文章（共165篇）

【贪心】种树

今晚把困扰了好久的贪心题做出来了，给大家分享一下思路。题目描述一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最...

2020-01-13

0 831

【贪心】线段不重合最大值（界点位置移动）

题目描述数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。输入第一行为一个正整数n；在接下来的n行中，每行有2个数ai,bi，描述每条线段。输出输出一个整数，为k的最大值。样例输入复制样例数据 3 0 2 2 4 1...

2020-01-13

1 482

0-1背包问题总结【递归算法与二进制算法】

听学长讲了算法之后，总结了一下背包问题的两种方法，当然这并不是最优的，会tle。题目描述给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。输入...

2020-01-13

0 533

upc新生训练第二场A朋友【字符串转为数组下标】

题目描述同学们应该学会多交一些好朋友。朋友关系是相互的，A 是 B 的好朋友，则 B 也是 A 的好朋友。朋友关系是不传递的，A 是 B 的好朋友，B 是 C 的好朋友，但 A 和 C 不一定是好朋友。现在给出某小学部分同学之间的朋友关系，请编程统计朋友最多的人有多少个好朋友。输入 ...

2020-01-13

0 615

最强素数【区间长度】

题目描述小李在你帮助之下轻松战胜了他的同学们，于是满怀恶意的同学出了一个题目来为难小李，作为小李神一样的队友，你又要出力了。素数41能写成连续6个素数之和：41=2+3+5+7+11+13。现在要求n以内的素数中，能表示为最多连续素数之和的那个数，如果有多个答案，请输出最大的那个素数。 ...

2020-01-13

0 832

爱好数学的国王【唯一分解定理】

题目描述 Z 国的国王是一个非常爱好数学的国王。一天他对着他的那些大臣说：“素数真是一种神奇的正整数，除了1和它本身外，不能被其他任何正整数整除，2是最小的素数，有无穷多个啊……它还有一个美妙的名字：质数，……数学多么有趣啊……”。 Z 国今年风调雨顺，百姓丰衣足食。为了奖励他那帮管理有方的大...

2020-01-13

0 983

扩展欧几里得算法【笔记】

一、欧几里得算法 (1).gcd(a,b)=gcd(b,a%b) reason:用例子来证明，假设a=38，b=8,则38=4*8+6;此时求a与b的最大公约数，肯定为6与8的最大公约数，因为4*8可以被8整除。 (2)根据上述等式求解 ax+by=gcd(a,b) {gcd(a,b)为a,b...

2020-01-13

0 508

DAG最长最短路【搜索与动态规划】【笔记】

一、DAG的定义 DAG为一个有向无环图，任意一条边有方向，但是不存在环路。 A→B→C即为有向无环图。二、搜索与记忆化搜索经典例题：有N个矩形，每个矩形可以用ab来描述，a和b分别为矩形的长与宽。矩形X可以嵌套在矩形Y中当且仅当a<a1&&b<b1或者a&l...

2020-01-13

0 948

图的储存【邻接矩阵，邻接表，优化链式前向星】【图论】【笔记】

图的存储 1.简单储存（邻接矩阵）：第一行输入n与m,表示n个点，m条边然后输入 u,v 表示 u与v相连，代码： int vis[500][500]; void save(int u, int v) { int m,n; scanf("%d%d",&am...

2020-01-13

0 888

求最短路的四种算法【 dijkstra算法】【Floyd算法】【Spfa】【优化Spfa-优先队列】【图论】

首先，何为最短路？假设有五个点，每个点之间都有一条连线，并且赋予距离。给予一对起点与终点，让你求出从起点到终点的最短距离，或者最短时间。 HDU2544. 这个问题可以枚举，从1-2，1-3,1-2-3等等并求出其最短的路线，但是如果数据太多怎么办。假如有1000个点，挨个枚举可能会枚...

2020-01-13

0 769