哈尔滨理工大学ACM集训第二周总结

你的名字 2021-11-05 17:48 334阅读 0赞

二分查找：

int erfen(int *a,int l,int r,int v){         //a为待查找数组，l为下界下标，r为上界下标，v为目标值
    
             int mid;
    
             while(l<=r){ 
    
                      mid=l+r;
    
                      mid/=2;
    
                      if(a[mid]==v)   return mid;
    
    
                      else if(a[mid]>v)      r=mid-1;
    
                      else  l=mid+1;
    
             }      
    
             return -1;
    
    }

已排序二分法o(log2^n)
    
    未排序的二分法o(n^2)+o(log2^2)

分（Divide）  
将规模为n的问题分解为 k 个规模较小的子问题  
治（Conquer）  
对k个子问题分别求解，然后将各个子问题的解合并得到原问题的解  
分治策略是从下至上求解并将合并得到解

/*二分查找法分治策略*/
    Begin
        输入有序数组a[],查找元素x,数组最左边下标i，最右边下标j
        i->0,j->a.length
      1.while(i>=j)循环执行: 
        1.1 设置 m =(i+j)/2;
        1.2 if(x==a[m]) return m;
        1.3 if(x<a[m]) j=m-1; else i=m+1;
      2.return -1; 
    End

GCD

int gcd(int a,int b){ 
    
             int temp;
    
             while(a%b!=0){ 
    
                      temp=a;
    
                      a=b;
    
                      b=temp%b;
    
             }
    
             return b;
    
    }

int gcd(int big, int small)
    { 
        if (small > big) swap(big, small);
        int temp;
        while (small != 0){  // 辗转相除法
            if (small > big) swap(big, small);
            temp = big % small;
            big = small;
            small = temp;
        }
        return(big);
    }

全排列

void Pern(int list[], int k, int n) {    // k表示前k个数不动仅移动后面n-k位数
        if (k == n - 1) { 
            for (int i = 0; i < n; i++) { 
                printf("%d", list[i]);
            }
            printf("\n");
        }else { 
            for (int i = k; i < n; i++) {    // 输出的是满足移动条件所有全排列
                swap(list[k], list[i]);
                Pern(list, k + 1, n);
                swap(list[k], list[i]);
            }
        }
    }

除此之外 库函数 do whle（nex_permutation）

大数模拟

**大数加法**

string add1(string s1, string s2)
    { 
        if (s1 == "" && s2 == "")   return "0";
        if (s1 == "")   return s2;
        if (s2 == "")   return s1;
        string maxx = s1, minn = s2;
        if (s1.length() < s2.length()){ 
            maxx = s2;
            minn = s1;
        }
        int a = maxx.length() - 1, b = minn.length() - 1;
        for (int i = b; i >= 0; --i){ 
            maxx[a--] += minn[i] - '0'; // a一直在减 ， 额外还要减个'0'
        }
        for (int i = maxx.length()-1; i > 0;--i){ 
            if (maxx[i] > '9'){ 
                maxx[i] -= 10;//注意这个是减10
                maxx[i - 1]++;
            }
        }
        if (maxx[0] > '9'){ 
            maxx[0] -= 10;
            maxx = '1' + maxx;
        }
        return maxx;
    }

**大数阶乘**

#include <iostream>
    #include <cstdio>
     
    using namespace std;
     
    typedef long long LL;
     
    const int maxn = 100010;
     
    int num[maxn], len;
     
    /* 在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度 tip: 阶乘都是先求之前的(n-1)!来求n! 初始化Init函数很重要，不要落下 */
     
    void Init() { 
        len = 1;
        num[0] = 1;
    }
     
    int mult(int num[], int len, int n) { 
        LL tmp = 0;
        for(LL i = 0; i < len; ++i) { 
             tmp = tmp + num[i] * n;    //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）
             num[i] = tmp % 10; // 保存在对应的数组位置，即去掉进位后的一位数
             tmp = tmp / 10;    // 取整用于再次循环,与n和下一个位置的乘积相加
        }
        while(tmp) {     // 之后的进位处理
             num[len++] = tmp % 10;
             tmp = tmp / 10;
        }
        return len;
    }
     
    int main() { 
        Init();
        int n;
        n = 1977; // 求的阶乘数
        for(int i = 2; i <= n; ++i) { 
            len = mult(num, len, i);
        }
        for(int i = len - 1; i >= 0; --i)
            printf("%d",num[i]);    // 从最高位依次输出,数据比较多采用printf输出
        printf("\n");
        return 0;
    }

itoa() //将整形转换成字符串

#include <iostream>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    int main() 
    { 
    int n;
    cin>>n;
    char a[100];
    char b[100];
    char c[100];
    itoa(n,a,2);
    cout<<strlen(a);
    cin>>n;
    itoa(n,b,16);
    cout<<b;
    cin>>n;
    itoa(n,c,10);
    cout<<c;
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

atoi() //把字符串转换成整型数

#include <iostream>
    #include<cstdlib>
    using namespace std;
    int main()
    { 
    	int n;
    	cin >> n;
    	char a[100];
    	char b[100];
    	_itoa_s(n, a, 2);
    	n =atoi(a);
    	cout << n<<endl;
    	int m;
    	cin >> m;
    	_itoa_s(m, b, 16);
    	cout << b<<endl;
    	m = atoi(b);
    	cout << m<<endl;
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70 1]  
  
计算几何之求多边形面积

![在这里插入图片描述][20190809100225996.png]  
这个多边形上的点都连了一条到原点的线段，相邻两点间的连线与两点和原点的连线构成了8个三角形（多边形共八条线段），如果把其中一些三角形的面积加起来，再减掉另一些三角形的面积，就是所求多边形的面积！而且与原点位置什么都无关！

所以只要判断哪些三角形加上，哪些三角形减去即可！

x=[1]
    y=[1]
    ans=0
    n=0
    n=input()
    for i in range(1,n+1):
        x.append(0)
        y.append(0)
        x[i],y[i] = [int(j) for j in raw_input().split()]
    for i in range(2,n+1):
        ans=ans+(float)(x[i]*y[i-1]-x[i-1]*y[i])/2.0
    ans=ans+(float)(x[1]*y[n]-x[n]*y[1])/2.0
    if ans<0:
        ans=-ans
    print (ans)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20211104/067906bd0a50461da92cfbd76a996af9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70 1]: /images/20211104/775c0e964199467498bb10973d23f00d.png
[20190809100225996.png]: /images/20211104/31d1d8a5a3284428b7dc2209b98612ac.png