算法与acm

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081131113145832/

虽然网上有很多介绍了，我还是要写一下吧，尽量从它的起源，如何被发现，以及为什么应该是这样的来写，单纯的使用很简单，也不是学习的目的，理解有助于记忆吧，当然可能还有理解不到的地方。 read more

先看一下匈牙利算法的dfs实现，很简洁

//二分匹配模板
bool g_map[MAX_N][MAX_N];
int r[MAX_N];
int l[MAX_N];
bool used[MAX_N];
int n;
bool path(int u,int n){
    for(int v = 0 ; v < n ; v++){
        if(g_map[u][v] && !used[v]){
            used[v] = true;   
            if(r[v] == -1 || path(r[v],n)){
                l[u] = v;
                r[v] = u;   
                return true;
           }           
        }
    }
    return false;
}
int bin_match(int n){
    int res = 0;
    memset(r,-1,sizeof(r));
    memset(l,-1,sizeof(l));
    for(int i = 0 ; i < n ; i++){
        memset(used,false,sizeof(used));
        if(l[i] == -1){
           if(path(i,n)) res++;   
        }
    }
    return res;
} read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/709717672008111064351431/

很明显，对于算法的证明过程的理解有助于算法本身的理解。

关于二分图，算法的流程在这篇blog里讲的很清楚，很多算法都结合了图形，所以讲讲得很易懂，推荐一下 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081198472074/

二分图，是图论中的一个经典模型，关于二分图，涉及了很多问题，比如最大匹配，最优匹配，完美匹配，最小覆盖。网络流也是这样，再求最大匹配的时候，实际上可以利用转化的思路，就像利用最短路算法求解差分约束系统，利用单源最短路求单目标最短路，利用单源最大流求多源最大流，都是利用了转换的思想，将一个不熟悉的问题转换或者规约为一个熟知的问题。 read more

转载请注明作者：phylips@bmy

出处：http://duanple.blog.163.com/blog/static/70971767200811344425606/

引言：
现实中的很多问题都可以看成搜索问题
众里寻她千百度，蓦然回首那人却在灯火阑珊中。
就算是人类的思维，很多时刻也是在进行着搜索，搜索存储在脑中的记忆元素
就算身在社会中，我们也还是在不同的时间搜索着不同的东西。 read more

经典问题,如果只要求额外空间O(1)，实际下面这篇文章就是这种，但是我怀疑它的时间不是O(n)

利用了手摇算法进行swap.

http://www.cppblog.com/converse/archive/2008/09/28/63008.aspx?opt=admin

原文作为附录贴在本文后面了。

实际上该题出现在taocp。

taocp:5.2.4 18. read more

转载请注明作者：phylips@bmy  出处：http://duanple.blog.163.com/blog/static/709717672008102885325526/

poj 1275 3159 1364 1716 1201 3169
这类问题，就像网络流，图论，dp，关键在列出满足的表达式，建立好数学模型，剩下的过程就很简单了。所以主要难点在于构图，从实际的描述抽象成模型。准确找到约束条件。 read more

http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
ok，这道题，的意思是给你一堆钱，各种面值的都有，比如10块的5张，5块的3张，2块的1张，请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额，比如cash=33块。
我们可以取3张10块+2张1块=32，就是我们可以找到的那个最接近且小于33的数额。 read more

http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
这个方法很简单，思路是这样的，对于每次输入一个关系后，我们就对输入进行一次拓扑排序，拓扑排序的结果有三种情况。
结果确定的两种情况：
第一种，如果排序后，序列中的节点数目<n,说明出现了环，因此应该直接输出，一旦结果确定，以后的输入就不用判断了。
第二种，如果排序后，节点数目刚好等于n，并且序列里相邻的节点已经明确出现了<,关系，说明大小关系已经确定了
还有一种，只能说明到目前为止知道的信息不足以判断，还需要继续看以后的输入才行
第三种情况，即排序后，节点数目刚好等于n，但是序列里相邻的节点还未明确出现<关系 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200810165100622/

http://acm.pku.edu.cn/JudgeOnline/problem?id=3406 Last digit

计算n!/(m!*(n-m)!)也就是C(n,m)的最后一个非零位—-poj3406

因为(m!*(n-m)!)不是n!的一个子集，所以这个不能利用1150的方法,而且观察它的input,实际上只有一个case，而且n ，m< 1000000，所以nlogn的方法是可以过的。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081016113033592/

http://acm.pku.edu.cn/JudgeOnline/problem?id=1150

最最原始的问题，是那个计算n!的结果中的0的个数的问题，对于这个问题的解答是，我们只需要观察1*2*3…n的因子中，因子5的个数就可以了。因为末尾0的个数，实际上反映了结果中因子10的个数，而10=2*5，由于在1*2*3…n中，2的个数始终是大于5的，所以10的个数实际上是由因子5的个数决定的，所以需要计算出5的个数就好了。 read more

写了老长时间，主要是中间犯了很多小错，写的时候不够严谨啊。。。
写凸包算法时犯的一些错误
1.while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention ! …
当时忘了加这个！。。。
2.去除同线的点的时候，出错，光记得排除那些共线的点，反而忘了添加其他的不共线的普通点             
3.排序时候，交换写错，下面的end应该是swap(points_set[j],points_set[i++]);
                if(cmp(&points_set[j],&points_set[end]) < 0){
                      swap(points_set[end],points_set[i++]);         
                }                                                    
4.去除同线的点的时候，计算两点距离出错，两点间的距离公式竟然忘了求平方。。。
直接：(x1-x2)+(y1-y2)                                    
5.忘了在while循环中，更新convex_next_top，convex_top
            while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
               convex.pop_back();     
            } 
6.提交的时候忘了把#undef DEBUG加上 read more

http://acm.pku.edu.cn/JudgeOnline/problem?id=1426

如果想到方法，写起来蛮快，无奈我写的if,else逻辑太复杂，直接导致wa，而且很难查错，只好重新重构了下条件判断的组合方式，才ac。

想来，这个题目的算法是晚上睡觉，偶尔想起以前在smth灌水的时候，遇到过一个题目，在脑中搜索了许久，终于想起来，那是一道求n位全1整数除以某个数m的余数为0，求n为多少之类的。。。 read more

1.三角形面积公式

已知三角形三个顶点，求其面积，直接使用叉积，如（x1,y1）(x2,y2) (x3,y3)

叉积是指(x2-x1,y2-y1) (x3-x1,y3-y1)两向量的叉积

s=0.5*abs( (x2-x1)*(y3-y1) -(y2-y1)*(x3-x1) )

2.平面多边形面积

对于凸多边形实际上利用了三角形面积求法，将多边形划分成了三角形 read more

http://acm.pku.edu.cn/JudgeOnline/problem?id=2084

很久没用java了，忘了很多了，因为java处理大整数运算非常方便，今天时间紧迫，破例使用一次

递推公式很简单

f(0) = f(1) = 1

f(n) = f(0)*f(n-1) + f(1)*f(n-2) 。。。+f(n-1)*f(0)

import java.io.*;
import java.util.*;
import java.math.BigInteger;
public  class Main {
public static void main(String[]args){
Scanner sin=new Scanner(new BufferedInputStream(System.in));
int n;
int i = 0;
BigInteger big[] = new BigInteger[101];
for(i = 0 ; i < 101 ; i++)
big[i] = new BigInteger("0");
big[0] = big[1].add(new BigInteger("1"));
big[1] = big[1].add(new BigInteger("1"));
for(i=2; i < 101 ; i++){
 for(int j = 0 ; j < i ; j++){
  big[i] = big[i].add(big[j].multiply(big[i-1-j]));  
  }//System.out.println(big[i].toString()); 
} read more

题目的意思是这样的：http://acm.pku.edu.cn/JudgeOnline/problem?id=2411

给你一个h*w的矩形，用一个1*2的小矩形去填充，问有多少种填充方法，不考虑对称性。

关键点提示：

 1.DFS部分

实际上是在枚举第i行的放置方法，由此便可以确定出该行及上一行的状态。 read more