-
[综合] 欧几里德与拓展欧几里德算法
做poj1061的时候接触到了拓展欧几里德算法,所以查阅了一下白书和网上的解释,现在整理一下。 欧几里德算法: 欧几里德算法比较简单,就是俗称辗转相除法的一直求两个数的最大公约数的算法,关键在于:gcd(a,b)=gcd(b,amodb),与边界条件gcd(a,0)=a结合就可以递归求得结果。 ...
84
热度 -
[综合] POJ2823 Sliding Window(单调队列)
题意: 给一列数,用一个长度为k的区间在这列区间上从左到右移动,求出每个区间中的最大值和最小值。 要点: 单调队列,主要应用是存储最值,每次找最值只要看队头即可,否则每次都要遍历一次肯定超时。其实直接考单调队列的地方不多,主要是用它优化一些DP什么的。这题主要是注意一下因为区间更新,有时候队头会不在...
86
热度 -
[综合] POJ2002POJ3432 Squares(二分||hash)
题意: 给出一系列坐标,求最多可以组成多少个正方形 要点: 可以用二分或者哈希,哈希我不会,以后学一下。二分比较简单,以两个点作为参考边,可以通过全等三角形得出剩下两个点的坐标。然后二分查找是否存在即可。 已知:(x1,y1)(x2,y2)则: x3=x1+(y1-y2)y3=y1-(x1-x2)x...
2
热度 -
[综合] POJ1017 Packets(贪心)
题意: 有高度相同,底面积为1*1,2*2,3*3……6*6的产品,包裹底面积是6*6的,求最小的包裹数。 要点: 很明显是贪心,思路比较好理清楚,就是优先选大的产品,注意都是向上取整。 15425287 Seasonal 1017 Accepted 164K 16MS C++ 594B ...
81
热度 -
[综合] ZOJ3785 What day is that day?(同余与模算术)
题意: 今天星期六,求1^1+2^2……N^N天后是星期几 要点; 很明显是同余与模算术,用白书上的复杂度为O(logn)的算法。一开始我是想打表,但这题不能开数组,范围太大。后来我也想到找规律了,但我只打了30个的表,而规律从42开始,点背啊!下次注意了,打表尽量打多一点,而且注意一下排版让规律找...
6
热度 -
[综合] 例题10-1 UVa11582 Colossal Fibonacci Numbers!(同余与模算术)
题意: 看白书 要点: 先斐波那契数列打个表,然后用同余与模算术,找个规律就行。注意数的最大值为2^64,用longlong型还不够,必须要用unsignedlonglong型。 #include<stdio.h> #include<stdlib.h> #include&...
40
热度 -
[综合] 例题10-4 UVa10791 Minimum Sum LCM(最小公倍数的最小和)
题意: 看白书 要点: 运用唯一分解定理,使每个ai^pi作为一个单独的整数时最优。例如72=8*9时最优。注意:如果本身是一个素数最后还要+1,而且如果本身分解后只有一种因子,最后也要+1,如1=1*1,答案是2。一开始我担心时间想用线性筛什么的,后来发现做不出,看了一下题解发现只要普通的遍除即可...
33
热度 -
[综合] POJ3041 Asteroids(二分图)
题意: 空间中有很多颗小行星,飞船要每次能清空同一行或同一列上的所有小行星,问最少要几次能将所有小行星清除。 要点: 将小行星的行作为u,列作为v建图,就是一个最小点覆盖集的裸题,最小点覆盖集=最大匹配数,直接套个模板即可。 15480774 Seasonal 3041 Accepted ...
84
热度 -
[综合] POJ2239 Selecting Courses(二分图)
题意 一周7天,每天12节课,现在学校有n种课程可以选择,每种课程给出对应的时间(有的课一周内有好几节),要求选的课没有时间冲突,求最大选课数。 要点: 知道是二分图就简单了,没有冲突不就二分图最大匹配嘛,将n节课作为u,所有时间作为v,因为数据比较小,所以建图直接用三维数组,这题如果一开始不知道是...
12
热度 -
[综合] POJ2724 Purifying Machine(二分图)
题意: 有2^n个奶酪,对应二进制的数,用清理机输入一个二进制数可以清理对应的奶酪,含有*的算成0和1两个,每次只能出现一个*,现在清理机自身感染细菌,它清理的奶酪都被感染,将清理机消毒后,问最少清理几次能把所有感染的奶酪清理干净。 要点: 这题比较复杂,题意就比较难看懂,算是一个有向图的最大匹配问...
51
热度 -
[综合] HDU 2255 奔小康赚大钱 (二分图:KM算法)
题意: 中文题不解释 要点: KM算法是求完备匹配下的最大权匹配:在一个二分图内,左顶点为X,右顶点为Y,现对于每组左右连接X[i]Y[j]有权w[i][j],求一种匹配使得所有w[i][j]的和最大。注意完备匹配定义:|X|=|Y|=匹配数。这算法还是比较难的,证明我还是半懂不懂的,具体流程还是可...
46
热度 -
[综合] HUD3488 Tour(二分图的最小权值和)
题意: 给你一个有向图,边有权值,现在要你求若干个环包含所有的顶点,并且每个顶点只出现一次(除了起点),求所有环中所有边得权值之和最小值。 要点: 因为每个顶点只出现一次,干脆所有环都拆成起点到一个点再回起点,这样就是一个二分图的最小权值和问题。前面做的题都是求最大权值和,最小权值和就是将每条边的权...
51
热度 -
[综合] 例题9-4 UVa116 Unidirectional TSP(DP:多段图的最短路)
题意: 看白书 要点: 一共三种决策:直行,右上,右下。那么就递推,注意题目中可以从第一列的任意一行出发,而且是环形的,最后还得按字典序输出路径,路径输出就直接用数组记录,因为是倒序递推,所以正序直接可以得到路径。 #include<stdio.h> #include<stdl...
14
热度 -
[综合] HDU1248 寒冰王座(完全背包)
题意: 中文题不解释 要点: 就是个完全背包的水题变形,注意因为最后钱用不完,所以d数组一开始全赋值为0。 17160682 2016-05-1514:06:34 Accepted 1248 0MS 1752K 528B C++ seasonal #include<stdio....
43
热度 -
[综合] POJ1276 Cash Machine(多重背包)
题意: 一个零钱机提供多种面值的零钱,每种零钱都有对应的数量,现在要取cash元钱,要求输出小于等于cash中最大的那个值。 要点: 多重背包,直接拆成01背包超时,这题比较特殊,只要判断能不能取到这个值,不用输出具体数目,所以这里有一个优化,写起来比较简单而且复杂度不错,主要就是拆成完全背包并比较...
44
热度 -
[综合] 例题9-9 UVa10003 Cutting Sticks(DP:矩阵链乘)
题意: 看白书 要点: 明显是类似于矩阵连乘问题,用d[i][j]标记i到j中的最优费用,从中间一点k处截成两半,可以写出状态转移方程为d[i][j]=min(d[i][j],d[i][k]+d[k][j]+pos[j]-pos[i]),不难看出这实际是一个区间DP问题,通过j-i小区间不断递增进行...
10
热度 -
[综合] 例题9-11 UVa1331 Minimax Triangulation(DP:最优三角剖分)
题意: 看白书 要点: 基本的三角剖分题,但要注意三个点: 1.已知三角形三个顶点的坐标,可用行列式求面积,则S=(1/2)*(下面行列式)|x1y11||x2y21||x3y31|S=(1/2)*(x1y2*1+x2y3*1+x3y1*1-x1y3*1-x2y1*1-x3y2*1) 2.这题没有说...
75
热度 -
[综合] 例题9-6 UVa11400 Lighting System Design(DP)
题意: 看白书 要点: 其他的白书上讲的比较清楚了,状态转移方程为:d[i]=min(d[i],d[j]+(s[i]-s[j])*bulb[i].c+bulb[i].k),有点难以理解的是如果i到j之中有的不进行换比较合理怎么办?但其实这种情况是不存在的,这个博客进行了详细的数学推导:点击打开链接 ...
77
热度 -
[综合] 例题9-10 UVa1626POJ1141 Brackets Sequence(DP)
题意: 看白书 要点: 状态转移方程真难想,这基本上是个区间DP问题,但还得考虑首尾已经是正规的,这两种情况都要考虑,而且还互相干扰,最后还得打印解,基本就是重新检查一下哪个决策最好。还有个陷阱:输入串可能是空串,所以要用gets。 15546092 Seasonal 1141 Accep...
93
热度 -
[综合] POJ1015 Jury Compromise(DP)
题意: 输入n组数据,选出m个,每组数据有一个D值和一个P值,要求输入|D-P|的和最小时的D和P和选取的数据下标,如果有相同的,输出|D+P|的和最大的那个。 要点: 真的很难这题,因为相同时要输出和最大的那个,所以我们状态转移方程不能只考虑差最小,而且要将k=|D-P|的和放入转移的量,用DP[...
74
热度