ACM算法题总结（一）

目录

练习题2.1 最基础的“穷竭搜索”
练习题2.2 一直往前！贪心法
练习题2.3 记录结果再利用的“动态规划”
练习题2.4 加工并存储数据的数据结构
练习题2.5 它们其实都是“图”
练习题2.6 数学问题的解题窍门
辗转相除法
 POJ 2429 GCD & LCM Inverse
POJ 1930 Dead Fraction
素数
 POJ 3126 Prime Path
POJ 3421 X-factor Chains
POJ 3292 Semi-prime H-numbers
快速幂运算
 POJ 3641 Pseudoprime numbers
POJ 1995 Raising Modulo Numbers

练习题2.1 最基础的“穷竭搜索”

练习题2.2 一直往前！贪心法

练习题2.3 记录结果再利用的“动态规划”

练习题2.4 加工并存储数据的数据结构

练习题2.5 它们其实都是“图”

练习题2.6 数学问题的解题窍门

辗转相除法

素数

POJ 3126 Prime Path

题意：给定两个四位素数a，b，要求把a变换到b。变换的过程要保证每次变换出来的数都是一个四位素数，而且当前这步的变换所得的素数与前一步得到的素数只能有一个位不同，而且每步得到的素数都不能重复。

注意点：

素数筛预处理1000~9999中的素数加快速度。
bfs不要写残了

本题重点是BFS搜索，注意姿势。对于vis数组，本题的范围较小可以直接用，且复杂度为O(1)。如果用Map来作为这个哈希表，则会产生额外的复杂度。

C++ STL使用哈希表需要#include<hash_map>，其他用法与map类似。总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。

现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

本题部分代码如下：

const int INF = 1<<30;
int t,a,b,prime[10010],vis[10010];
void bfs(int a,int b){
	int res=INF;
	queue<pair<int,int> >qu;
	qu.push(mp(a,0));
	CLR(vis);
	vis[a]=1;
	while(!qu.empty()){
        pair<int,int> pr = qu.front();
        qu.pop();
        int num = pr.first;
        if(num==b){
            res = min(res,pr.second);
        }
        int bas = 1;
        RREP(k,4,1){
            int l = 0,r=9;
            if(k==1) l=1;
            int pos = num%10;
            REP(i,l,r){
                if(i!=pos){
                    int pm = pr.first + (i-pos)*bas;
                    if(!vis[pm] && prime[pm]){
                        vis[pm]=1;
                        qu.push(mp(pm,pr.second+1));
                    }
                }
            }
            bas *= 10;
            num /= 10;
        }
    }
    if(res==INF) printf("Impossible\n");
    else printf("%d\n",res);
}

C++ hash_map原理：首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
存放key和value在桶内

其取值过程是：

得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
取出相等的记录的value

hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候)。

POJ 3421 X-factor Chains

题意：因子链是将一个数X分解成从1到X的数列，前一个数可以整除后一个数。求出一个数字\(n(1<=n<=2^{20})\)最大链长和链的个数。

注意点：分解质因数和组合数的简便优雅写法。

本题关键代码如下：

int n;
int res[2000];

int Cnm(int n,int m){
    int res = 1;
    REP(i,1,m){
        res = res * (n-i+1)/i;
    }
    return res;
}

void solve(int n){  //分解质因数形成链
    CLR(res);
    int len=0,s=0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            int cnt=0;
            while(n%i==0){
                cnt++;
                n /= i;
            }
            len += cnt;
            res[++s]=cnt;
        }
    }
    if(n!=1){
        len ++;
        res[++s]=1;
    }
    printf("%d ",len);
    int ans = 1;
    REP(i,1,s){  //组合数求值
        ans *= Cnm(len,res[i]);
        len -= res[i];
    }
    printf("%d\n",ans);
}

POJ 3292 Semi-prime H-numbers

题意：一个H-number是所有的模四余一的数。如果一个H-number是H-primes当且仅当它的因数只有1和它本身（除1外）。
一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。H-number剩下其他的数均为H-composite。
给你一个数h,问1到h有多少个H-semi-prime数。(\(1<=h<=10^{6}\))

注意点：如果按照已知素数然后进行乘积组合的方法进行判断，则一定要求出\(10^6\)范围内的全部素数，不能因为1000左右的两个H-prime乘积会超过\(10^6\)，就之求解1~1000范围内的”H-prime”。

如果已经求解出范围内的所有”H-primes”，然后需要判断\(10^{6}\)范围内的数字是不是”H-semi-prime”。注意如果相乘后的数字大于\(10^{6}\),需要break掉。

预处理得出所有结果，根据输入输出相应值即可。

本题关键部分代码：

const int maxn=1000010;
int n,flag[maxn],hprime[maxn],ans[maxn];

void solve(){
    REP(i,2,maxn){
        flag[i] = 1;
    }
    flag[1]=0;
    int s=0;
    REP(i,2,maxn){
        if(flag[i]){
           if(i%4!=1) flag[i]=0;
           else{
             for(int j=2*i;j<=maxn;j+=i)
                flag[j]=0;
             hprime[++s]=i;
           }
        }
    }
    REP(i,1,s){
        REP(j,i,s){
            ll res = (ll)hprime[i]*hprime[j];
            if(res>maxn) break;
            ans[hprime[i]*hprime[j]]=1;
        }
    }
    REP(i,1,maxn) ans[i]+=ans[i-1];
}

还有一种方法是一次循环全部迭代更新结束，写法很优雅，速度更快。注意姿势！！

const int size=1000001;   
int H_Number[size+1];  
  
/*筛法打表*/  
void Table(void)  
{  
    memset(H_Number,0,sizeof(H_Number));  //H_Number[i]=0 表示 i为H-prime  
  
    for(int i=5;i<=size;i+=4)  
    {  
        for(int j=5;j<=size;j+=4)  
        {  
            int multiply=i*j;  
            if(multiply>size)  
                break;  
  
            if(H_Number[i]==0 && H_Number[j]==0)  //i与j均为H-prime  
                H_Number[multiply]=1;  //multiply为H-semi-primes  
            else  
                H_Number[multiply]=-1; //multiply为H-composite  
        }  
    }  
  
    int Pcount=0; //H-prime计数器  
    for(int k=1;k<=size;k++)  
    {  
        if(H_Number[k]==1)  
            Pcount++;  
        H_Number[k]=Pcount;   //从1到k有Pcount个H-semi-primes  
    }  
    return;  
}  

快速幂运算

POJ 3641 Pseudoprime numbers

题意：输入两个数p和a，两个数如果p是素数输出no；如果p不是素数，判断\(a^{p}%p==a\)是否成立，如果成立输出yes,否则输出no。

水题。

POJ 1995 Raising Modulo Numbers

题意：快速幂求和取模。

注意点：注意取模的时候别出错。取模公式ans=(ans+pow_mod(a,b,mod))%mod。