竞赛快速及常用（后续更新）

短命女 2021-12-15 08:19 182阅读 0赞

\*\* **筛法求素数** （根据素数的倍数都是非素数进行筛选）

int a[1000000]= {1,1,0};
    void is_prime()
    {
        int I,J,n;
        for(I=2; I<=2000100; I++)
        {
            if(a[I]==0)
                for(J=I+I; J<=2000100; J=J+I)
                    a[J]=1;
        }
    }

求点到直线的距离公式（点C到直线AB的距离）

struct Node
    {
        double x;
        double y;
    };
    double dist(Node A,Node B,Node C)
    {
        if(B.x!=A.x)
        {
            double k=(B.y-A.y)/(B.x-A.x);
            return fabs((C.y-A.y)-k*(C.x-A.x))/sqrt(1+k*k);
        }
        else
            return fabs(C.x-A.x);
    }

判断两个直线是否想交

#include<stdio.h>
    struct point
    {
        double x;
        double y;
    };
    point A,B,C,D,E;
    double cross(point a,point b,point c)
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    bool in_line(point a,point b,point c,point d)
    {
        if(cross(a,b,c)==0&&cross(a,b,d)==0) return true;
        return false;
    }
    double b1,b2,k1,k2,y1,y2,x1,x2;
    int T,i;
    int main(void)
    {
        scanf("%d",&T);
        while(T--)
        {
            scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
            if(in_line(A,B,C,D)) printf("Interseetion\n");  ///共线
            else if(cross(A,B,C)*cross(A,B,D)>0||cross(C,D,A)*cross(C,D,B)>0) printf("Not Interseetion\n");  ///平行
            else ///相交
                printf("Interseetion\n");
        }
        return 0;
    }

欧拉函数（求\[1,n)中，和n互素的数的个数）

int eular(int n)
    {
      int ret=1,i;
      for(i=2;i*i<=n;i++)
        if(n%i==0)
        {
          n/=i,ret*=i-1;
          while(n%i==0)
          n/=i,ret*=i;
        }
      if(n>1)
        ret*=n-1;
      return ret;
    }

\*\* **同余冥取模算法**（求a^b%c，当a,b,c都非常大的时候可以用这个算法，把b转化成二进制数，然后如果第n位为1的话乘以a的n次方，每次都取模）

long long fun(long long x,long long y,int Max)
    {
        long long res=1;
        while(y>0)
        {
            if(y%2==1)
            {
                res=(res*x)%Max;
            }
            x=(x*x)%Max;
            y/=2;
        }
        return res%Max;
    }

\*\* **快速排序算法（sort）**

在\#include <algorithm>头文件中包含的sort函数当然是最常用的也是首选的排序函数，sort(a,a+m);写法就是这么简单，当然它是不稳定的，因为它在排序的同时对其中相同的值得位置可能发生改变，所以如果想要用稳定的就用stable\_sort(a,a+m);这个在排序的同时不会对位置改变，当然stable\_sort也可以在结构体的排序中运用，就只在写函数的时候把不等于部分去掉就OK，下面就贴一个对一个结构体的二级排序的代码：

#include <stdio.h>
    #include <algorithm>
    using namespace std;
    struct BB
    {
        int num;
        int chang;
        int duan;
    }a[1100];
    int cmp(BB a1,BB a2)
    {
        if(a1.num!=a2.num)
            return a1.num<a2.num;
        if(a1.chang!=a2.chang)
            return a1.chang<a2.chang;
        if(a1.duan!=a2.duan)
            return a1.duan<a2.duan;
    }
    int main()
    {
        int N,n,t,i;
        scanf("%d",&N);
        while(N--)
        {
            scanf("%d",&n);
            for(i=0;i<n;++i)
            {
                scanf("%d %d %d",&a[i].num,&a[i].chang,&a[i].duan);
            }
            sort(a,a+n,cmp);
            for(i=0;i<n;++i)
            {
                printf("%d %d %d\n",a[i].num,a[i].chang,a[i].duan);
            }
        }
        return 0;
    }

\*\* **移位操作**

下面就是常用的一些移位操作，之前看过人家的代码中的移位操作，很蛋疼，不知道是干嘛的，最近亲自写了一个程序实验了一下，算是懂了。n>>1出来的结果是n/2，而n<<1的结果就是n\*2，其实可以这么理解，就比如右移一位，n转化为二进制所有位右移，而原来的第一位丢失了，这不就是相当于除以2吗，但是1<<n呢？它的结果是2的n次方，这个在以后很常用，在这里记下来。我们程序猿也需要专业，写n/2一看就知道不是专业的，呵、、、可能对大神来说是笑话了，只是写在这儿，一边自己记忆和初学者也懂一下。

\*\*对一个string类型的字符串可以通过下面这个函数转化为chari型的字符，比较实用的。

const char \*p1=num1.c\_str(); // 将string转为 const char \*  
const char \*p2=num2.c\_str(); // 将string转为 const char \*

\*\***sprintf 和 sscanf 函数**

sprintf是把格式化的数据写入某个字符串缓冲区。也就是将一些东西输出到字符串，其用法是sprintf(buf,"%d%d%d%d%d",a,b,c,d,e);

例子：char* who = "I";
    char* whom = "CSDN";
    sprintf(s, "%s love %s.", who, whom); //产生："I love CSDN. "  这字符串写到s中
    
    sprintf(s, "%10.3f", 3.1415626); //产生：" 3.142"

sscanf()是将一些东西输入到字符串，利用它可以从字符串中取出整数、浮点数和字符串等等

#include <cstdio>
    int main()
    {
        char str[512] = {0};
        sscanf("123456 ", "%s", str);   //读出字符串中的字符
        printf("str=%s/n", str);
        sscanf("123456 ", "%4s", str);  //读出其中的前n个
        printf("str=%s/n", str);
        sscanf("12345 abcdef","%[^e],str");  //读到某个函数为止
        printf("str=%s\n",str);
        sscanf("123456abcFDSdedfBCDEF", "%[1-9a-z]", str);  //读出其中特定的字符
        printf("str=%s/n", str);
        sscanf("123456abcHdedfBCDEF", "%[^A-Z]", str);   //读到某个字符为止
        printf("str=%s/n", str);
        return 0;
    }

\*\***运行栈的工作原理**

大家编程的时候有没有思考过这样一个问题，当你运行一个递归函数时，就会存在当一个函数尚未返回，对它的另一次调用又发生的情况，对于这种调用，相同的名称的局部变量会有不同的值，这些值必须同时保存在相同的内存中，而且要不相互影响，这样的话它们就要有不同的内存地址，但是一个局部变量怎样能够实现这么多值的保存呢？

函数的形参的情形，与局部变量非常的相似，它们不能想全局变量那样用一个固定的地址来定位，这就需要存储在一个特殊的结构中，这就是栈。

对于一组递归调用的函数，其越早开始调用的函数，返回的就会越晚，调用时的形参和局部变量，调用开始时生效，调用完就会失效。这样，对于一组嵌套调用的函数，变量生效的时间越早，失效的时间就会越晚，这刚好满足栈的先进先出顶点特性，因此函数的形參和局部变量，可以用栈来储存，这种栈叫做运行栈。

为什么要写这个呢，我感觉这会加深我们对递归调用的认识，当我们在递归调用返回函数中间值的时候，我们不用深入模拟，直接诶运用栈的这种特性，枚举其中的值就ok。对初学者来说这个能够很好的加深对函数递归调用的认识。

\* **\*字符串流函数。**

**将一个字符串转化为数：**

#include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    
    template <class T>
    inline T fromString(const string &str)
    {
        istringstream is(str);
        T v;
        is>>v;
        return v;
    }
    int main()
    {
        string s="465153";
        int a=fromString<int>(s);
        cout<<a<<endl;
        return 0;
    }

**将一个值转化为string字符**

#include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    
    template <class T>
    inline string toString(const T &v)
    {
        ostringstream os;
        os << v;
        return os.str();
    }
    int main()
    {
        string s;
        int a=415641;
        s=toString(a);
        cout<<a<<endl;
        return 0;
    }

\*\*\*根据日期求是一年中周几的计算公式：int ans=(Day +1+ 2\*Month + 3\*(Month+1)/5 + Year + Year/4 - Year/100 + Year/400) % 7;