ACM一些常用小技巧（博客收集+总结）

清疚 2022-06-12 03:23 201阅读 0赞

**1,素数打表**

这个几乎涉及到数学的题都要用，素数筛法打表是最快的，甚至同时可以求欧拉函数（这个在之前的博客说过）

素数打表推荐博客：[http://blog.csdn.net/dinosoft/article/details/5829550][http_blog.csdn.net_dinosoft_article_details_5829550]

然后素数打表例题和欧拉函数的讲解：[http://blog.csdn.net/qq\_37497322/article/details/74859502][http_blog.csdn.net_qq_37497322_article_details_74859502]

**2，stl神器**

stl很强大，虽然效率不是很高但是对于很多题足够了，可以省去很多的代码，如果卡内存卡时间就老老实实手写吧

我之前的博客讲过：[http://blog.csdn.net/qq\_37497322/article/details/74914999][http_blog.csdn.net_qq_37497322_article_details_74914999]

**3，欧几里得求最大公约数**

int ojld(int x,int y)
    {
        int r=x%y;
        while(r!=0)
        {
            x=y;
            y=r;
            r=x%y;
        }
        return y;
    }

如果求最小公倍数就用两数相乘除最大公约数就好了

**4，快速幂**

常规的求幂方法一般难一些的题都会超时，这里给出模板

假如x为底，y为指数

int mi(int x,int y)
    {
        int t=1;
        while(y!=0)
        {
            if(y%2==1)
                t*=x;
            x=x*x;
            y=y/2;
        }
        return t;
    }

假如要%上一个数，假如要模的数为mod，写法

int mod=1e5+7;
    long long mi(long long x,long long y)
    {
        long long t=1;
        x=x%mod;
        while(y!=0)
        {
            if(y%2==1)
                t=(t*x)%mod;
            x=(x*x)%mod;
            y=y/2;
        }
        return t;
    }

这里long long防爆

**5.sort+结构体**

这个用途很多很多，基本属于必会，用了stl里的sort

sort（a,a+n）;这样写就是普通将一个数组a\[n\]从小到大排序，那么如果要从大到小呢，很简单，加上第三个参数

首先写一个函数

int cmp(int x,int y)
    {
        return x>y;
    }

任何加上sort（a,a+n,cmp）；

这样数组就按从大到小排好了

那么如果是结构体呢（最常用）

假如定义一个结构体

struct node
    {
        int p1,p2;
    };
    node a[105];

要按照优先级值p1按照从小到大排序，如果相同就按p2从小到大排序

那么这样写cmp函数

int cmp(node x,node y)
    {
        if(x.p1!=x.p1)
            return x.p1<y.p1;
        else
            return x.p2<x.p2;
    }

然后sort（a,a+n,cmp）；就按照要求排好了，如果还不懂就自己操作几遍看他们的排序情况，毕竟我一开始也不是很懂

还有优先队列的排序也是同理，要重载小于或者大于号，这个在stl里面有讲

[http_blog.csdn.net_dinosoft_article_details_5829550]: http://blog.csdn.net/dinosoft/article/details/5829550
[http_blog.csdn.net_qq_37497322_article_details_74859502]: http://blog.csdn.net/qq_37497322/article/details/74859502
[http_blog.csdn.net_qq_37497322_article_details_74914999]: http://blog.csdn.net/qq_37497322/article/details/74914999