SCU预备役Day 1

patrick-star- / 2023-07-29 / 原文

2023-07-28 22:13:56

基本算法

二分与三分

使用范围：答案具有单调性时。

原理：判断远比求解简单

定义域：

为整数域的时候，若区间长度为N，则需要进行log2N次运算
为实域的时候，判断R-L精度是否达到要求，需要R-L>=eps（但因为实数运算带来的精度问题，若eps太小会导致是循环，往往指定二分次数更好）

整数域：

 1 while(l<r){
 2     int mid=(l+r)>>1;
 3     if(check(mid)) r=mid;
 4     else l=mid+1;
 5     return l;
 6 }
 7 
 8 while(l<r){
 9     int mid=(l+r+1)>>1;
10     if(check(mid)) l=mid;
11     else r=mid-1;
12     return l;
13 }
14 
15 while(l<=r){
16     int mid=(l+r)>>1;
17     if(check(mid)) ans=mid,l=mid+1;
18     else r=mid-1;
19 }

实数域：

while(fabs(l-r)>dlt){
    mid=(l+r)/2.0;
    if(check(mid)) r=mid;
    else l=mid;
}

还有一种方法：如果指定二分次数为t，那么结束时区间长度为L/pow(2,t)，根据这个值是否符合我们的精度就可以了。

三分模板

使用范围：求凸性函数的极值问题（单峰函数）

#include<bits/stdc++.h>
using namespace std;
int n;
double l,r,a,b,c,d;
double s[20];
double ans(double x){
    double sum=0,t=1.0;
    for(int i=1;i<=n;i++){
        t*=x;
        sum+=s[i]*t;
    }
    return sum;
}
bool check(double m1,double m2){
    if(ans(m1)>ans(m2)) return true;
    else return false;
}
int main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>s[n-i+1];
    }
    int k;
    cin>>k;
    while(fabs(l-r)>=0.00001){
        double m1=l+(r-l)/3.0,m2=r-(r-l)/3.0;
        if(check(m1,m2)) r=m2;
        else l=m1;
    }
    cout<<(l+r)/2.0<<endl;
    return 0;
}

前缀和与差分：

典例1：求L - R 区间的和

Sum[r]-Sum[l]

二维情况：

复杂度：O(nm)

Sum[a][b]=sum[a-1][b]+sum[a][b-1]-sum[a-1][b-1]+x[a][b];

如果求（x1,y1）到（x2,y2）的矩阵和的话就是s[x2,y2]-s[x1-1,y2]-s[x2,y1-1]+s[x1-1,y1-1];

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。

差分数组：

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1], b[2], b[3],,,,,, b[i];

使得 a[i] = b[1] + b[2] + b[3] + ,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

何构造差分b数组：

a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

........

b[n] = a[n] - a[n - 1];

运用：m个操作，将区间[l,r]的数都加上c，最后输出区间数组。

我们知道a数组是b的前缀和，那么b[l]+c会影响l之后的a数组，最后我们再打个补丁：b[r+1]-c。

二维差分

　　构造公式：b[i][j]=a[i][j]-a[i-1][j]-a[i][j]+a[i-1][j-1];

void insert(int x1,int y1,int x2,int y2,int c)
{     //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

位运算

运算符优先情况

常见技巧

^（异或运算的运算法则）

　　1. a ^ b = b ^ a
　　2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
　　3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
　　4. a ^ b ^ a = b.

问题定义：有2n+1个数，只有一个单着，别的都是成对的，找出这个单着的数。比如：2 1 3 2 1。
答：异或计算，一趟搞定。时间复杂度o(n)，答案为３，因为两个相同的数异或为０．

问题：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

解答：
令，1^2^…^1000（序列中不包含n）的结果为T
则1^2^…^1000（序列中包含n）的结果就是T^n。
T^(T^n)=n。
所以，将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数。

问题：在一堆数中，有且仅有两种数，出现了奇数次，而其他种的数，都出现了偶数次，请找出出现了奇数次的这两种数。

int main()
{  
    int a=0,b=0;//设出现奇数次的数为a,b
    int t=0,i;
    int rightone;//二进制下，从右往左的第一个1
    int arr[20];

    for( i=0;i<20;i++)
    {
        t^=arr[i];
    }
    //现在的t==a^b，这两个出现奇数次的数异或

    //因为t==a^b;
    //a!=b
    //所以t的二进制肯定有一位上是1
    rightone=t&(~t+1);
    //一个数与(&)上自己取反+1的数，结果得到这个数二进制下最右侧的1
    //并且我们知道，a和b两者在这一位上，只有一者位上是1，另一个一定是0.
    for(i=0;i<20;i++)
    {
        if(t^arr[i]==0)//将该最右位是1和0的区分开
        {
            a^=arr[i];//此时a等于一种奇数次数^一些出现过偶数次数且该位也是1的数
                      //而出现偶数次可以抵消，所以直接得到了第一个出现了奇数次的数
        }
    }
    b=t^a;//由此再得到b
}