头像

Xie_


访客:1469

离线:5小时前



Xie_
1天前

质数

试除法判断是否为质数

726. 质数

bool is_prime(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}

筛质数

  • 埃氏筛法
int prime[N],st[N];
void (int n)
{
    int cnt=0; 
    for(int i=2;i<=n;i++)
    {
        if(st[N]) continue;
        prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)    st[j]=true;
    }
}
  • 线性筛法
int cnt=0;
for(int i=2;i<=n;i++)
{
    if(!st[i])  prime[cnt++]=i;
    for(int j=0;i*prime[j]<=n;j++) //通过最小质因子来筛走数,注意判断条件
    {
        st[prime[j]*i]=true;
        if(i%prime[j]==0)   break;
    }
}


质因数

试除法求质因数
449. 质因数分解(用哪种看题目需要和x的范围)

//一定要记得对那个可能存在的大于根号x的质因数进行特判处理O(n^1/2)
int main()
{
    cin>>x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int cnt=0;
            while(x%i==0)
            {
                cnt++;
                x/=i;
            }
            cout<<x<<" "<<cnt<<endl;
        }
    }
    if(x>1) cout<<x<<" 1";
}

int main()
{
    cin>>x;
    for(int i=2;i<=x;i++)
    {
        if(x%i==0)
        {
            int cnt=0;
            while(x%i==0)
            {
                cnt++;
                x/=i;
            }
            cout<<x<<" "<<cnt<<endl;
        }
    }
}


约数

约数是建立在质因数分解的基础上进行的
约数个数最多1500个(粗略)

vector<int> devide(int x)
{
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res.push_back(i);
            if(i!=x/i)  res.push_back(x/i);
        }
    }
}
  • 约数的个数

给你一个数求约数时
1.如果你分解成质因数乘积后,约数个数等于各个质因数质数的指数的乘积

2.如果不是分解成质因数,题目给定了你某个连乘式=x,那么就需要计算所有出现的质因数的指数乘积,要用hash表,
因为连乘式中的项可能具有相同的质因数,要进行合并.两者做法是不一样的要注意
(即对于这种情况上面的质因数分解不适用)

//第二种情况
#include<iostream>
#include<unordered_map>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
unordered_map<int,int> primes;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x;i++) //如果x范围大的话应该换成另一种质因数分解的办法否则会tle
        {
            while(x%i==0)
            {
                primes[i]++;
                x/=i;
            }
        }
    }
    ll res=1;
    for(auto prime:primes)  res=res*(prime.second+1)%MOD;
    cout<<res;
}
int gcd(int a,int b) //辗转相除法(欧几里得算法)求最大公约数
{
    return b? gcd(b,a%b):a;
}


公式法求最小公倍数(由最大公约数引入)

对于两个数而言最小公倍数最大公约数=两数相乘(!!!只适用于两个数),
如果想算多个数的最小公倍数,就拿第一个和第二个数算到的最小公倍数再和第三个数求最小公倍数

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

//对于两个数而言
int find_lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

//对于一个数组b而言最小公倍数
int find_lcm(int b[],int n)
{
    int multi=1,lcm=1,gcd=1;  //相当于构造了一个哨兵元素b[-1]=1,跟b[0]进行求最小公倍数,构成递推
    for(int i=0;i<n;i++)
    {
        multi*=b[i];
        g=gcd(lcm,b[i]);
        lcm=multi/g;
        multi=lcm;
    }
    return lcm;
}



Xie_
5天前

双指针可以用于维护两个序列或者一个序列
双指针算法用来把暴力算法的两重遍历进行优化,减小时间复杂度
从两重遍历中找到在上一次遍历中可以优化跳过的部分,j就可以不用再从头开始
O(n^2)——>O(2n)
不好怎么用语言描述看题吧


799.最长连续不重复子序列
朴素做法:用i枚举终点,j遍历(0,i)之间最长的连续不重复子序列;这样做的复杂度是O(n^2)
双指针优化:每次i往后移动一次,此时i对应的j,一定会在i-1对应的j的后面,那么每次j就不用回到0了可以从上次的j继续进行判断扫描;

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],s[N];
int n,res;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0,j=0;i<n;i++)
    {
        s[a[i]]++;          //a[i]出现的次数++
        while(s[a[i]]>1)
        {   
            s[a[j]]--;
            j--;
        }
        res=max(res,i-j+1);
    }
    cout<<res;
}

800.数组元素的目标和
朴素做法:对于每个i都遍历一遍j看是否=x
双指针:思考是否上一次的i对应的j可以对这一次的i的j的定位起到影响,
可以想到j从b数组最后一个数开始遍历(即从b数组中的最大数开始)如果上一次的a[i]+b[j]都大于了x
a[i+1]>a[i]
那么a[i+1]+b[j]也一定会大于目标元素.可以知道就只需要遍历上次的j的前面的数即(0,1,2,3..j)

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N]
int n,m,x;
int main()
{
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    for(int i=0,j=m-1;i<n;i++)
    {
        while(a[i]+b[j]>x)  j--;
        if(a[i]+b[j]==x)    cout<<i<<" "<<j;
    }
}


分享 高精度

Xie_
5天前

高精度加法

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> add(vector<int>& A,vector<int> B)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size())  t+=A[i];
        if(i<B.size())  t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)
        C.push_back(t);
    return C;
}
int main()
{
    string a,b;
    vector<int> A,B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)    A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)    B.push_back(b[i]-'0');
    vector<int> C;
    C=add(A,B);

    for(int i=C.size()-1;i>=0;i--)    cout<<C[i];
}

高精度减法

用(大数-小数)避免边界判断

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
bool cmp(vector<int>&A,vector<int>&B)
{
    if(A.size()!=B.size())
        return A.size()>B.size();
    else
    {
        for(int i=A.size()-1;i>=0;i--)
        {
            if(A[i]!=B[i])
                return A[i]>B[i];
        }
        return true;
    }


}
vector<int> sub(vector<int>& A,vector<int>& B)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size())  t-=B[i];
        C.push_back((t+10)%10);
        if(t>=0) t=0;
        else    t=-1;
    }
    while(C.size()>1&&C.back()==0)  C.pop_back();
    return C;
}
int main()
{
    string a,b;
    vector<int> A;
    vector<int> B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)    A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)    B.push_back(b[i]-'0');
    vector<int> C;
    if(cmp(A,B))
        C=sub(A,B);
    else
    {
        C=sub(B,A);
        cout<<"-";
    }

    for(int i=C.size()-1;i>=0;i--)    cout<<C[i];
}

高精度乘法(大整数/int)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> multi(vector<int>& A,int b)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        t+=b*A[i];
        C.push_back(t%10);
        t/=10;
    }
    return C;
}
int main()
{
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)    A.push_back(a[i]-'0');
    vector<int> C;
    C=multi(A,b);

    for(int i=C.size()-1;i>=0;i--)    cout<<C[i];
}

高精度除法(大整数/int)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> div(vector<int>& A,int b)
{
    vector<int> C;
    int t=0;
    for(int i=A.size()-1;i>=0;i--)
    {
        t=t*10+A[i];
        C.push_back(t/b);
        t=t%b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0)  C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)    A.push_back(a[i]-'0');
    vector<int> C;
    C=div(A,b);

    for(int i=C.size()-1;i>=0;i--)    cout<<C[i];
}



Xie_
7天前

记得写递归终止条件,总是不记得

快速排序

个人错误总结

1.不可以用>=和<=
可能会造成越界问题

2.分界值的选择与递归传入条件
i会指向x所在位置的后一个数(i所指向的数大于等于x)
j会指向x所在位置的前一个数(j所指向的数小于等于x)
为了让所分区间仍然满足左边的小于等于x右边的大于等于x
对于不同的分界元素(用i或者用j)写法就不一样

3.swap的交换条件不可省
否则最后一次出循环的时候可能发生不必要的交换

代码模板

void quick_sort(int* q,int l,int r)
{
    if(l>=r)    return;
    int x=q[(l+r)>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

另外一种

void quick_sort(int[] q,int l,int r)
{
    if(l>=r)    return;
    int x=q[(l+r+1)>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j])
    }
    quick_sort(q,l,i-1);
    quick_sort(q,i,r);
}

归并排序

(详见之前的排序分享)
排序

二分算法

二分的本质是一部分元素满足题目性质,另一半部分不满足

整数二分

789. 数的范围
check函数的定义,我们一般是先考虑题目的条件,分成满足和不满足题意,把满足题意且包含mid的放于check()中写
并且要保证此时check(mid)是true
就像数的范围这道题,一半是小于该数,另一半是大于等于该数,就会考虑把大于等于mid放进if判断语句中,而不是小于该数
(即保证mid是被包含在该合法区域内)
一般是小于等于该数,另一半是大于该数,
就是if(check(mid)) 要让mid不能被直接排除在答案之外

int main()
{
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=(l+r>>1)
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
}
int main()
{
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=(l+r+1>>1)
        if(check(mid))  l=mid;
        else    r=mid-1;
    }
}

浮点数二分

790. 数的三次方根
由于浮点数是没有向上向下取整的,所以就可以直接进行除也不用+1,或者-1
不过要小心负数的存在,还有r-l的值会影响结果精度

#include<iostream>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double r,l;
    if(x>=0)
        r=x,l=0;
    else
        r=0,l=x;
    while(r-l>1e-8)
    {
        double mid=(r+l)/2;
        if(mid*mid*mid>=x)  r=mid;
        else l=mid;
    }
    printf("%.6f",r);
}


活动打卡代码 AcWing 138. 兔子与兔子

Xie_
8天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int base=131,N=1000010;
char s[N];
ull prefix[N],p[N];
ull get(int l,int r)
{
    return prefix[r]-prefix[l-1]*p[r-l+1];
}
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);    //注意第一位是0所以要s+1,否则遇到第一位就会停止,然后len=0了
    p[0]=1;
    for(int i=1;i<=len;i++)
    {
        prefix[i]=prefix[i-1]*base+s[i]-'a'+1;   //在前面一位的基础上进行操作
        p[i]=p[i-1]*base;           //在前面一位的基础上进行操作
    }
    int m;
    cin>>m;
    while(m--)
    {
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }



}



Xie_
9天前

注意pair函数自带cmp函数,所以有时候要用两个元素,那定义pair比定义struct更好,要不然要自己写cmp

Set

在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。
set由于不会检验定位器的合法性,所以要注意哨兵元素的使用.
* 可以利用set的有序性来查找大于等于给定值的最小值小于等于给定值的最大值. 136. 邻值查找

s.lower_bound(key_value) //返回第一个大于等于key_value的定位器
s.upper_bound(key_value) //返回第一个一个大于key_value的定位器
set<int>::iterator it
迭代器不想定义可以用auto it=s.lower_bound(key_value);
  • 元素只出现一次,可以用来检验是否存在过重复关系(即如果题目要求输入重复的话就不进行操作,那么可以用set存储)
    count() 用来查找set中某个某个键值出现的次数,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。 101. 最高的牛
s.count(val);
  • 其他基础函数
begin()            返回set容器的第一个迭代器
end()            返回set容器的最后一个迭代器
clear()            删除set容器中的所有的元素
empty()           判断set容器是否为空
max_size()          返回set容器可能包含的元素最大个数
size()           返回当前set容器中的元素个数
insert()             插入元素进入set容器中
erase(iterator)      删除定位器iterator指向的值
erase(first,second)  删除定位器first和second之间的值
erase(key_value)     删除键值key_value的值

Multiset

它可以看成一个序列,插入一个数,删除一个数都能够在O(logn)的时间内完成
而且他能时刻保证序列中的数是有序的,而且序列中可以存在重复的数
* 可以利用set的有序性来查找大于等于给定值的最小值小于等于给定值的最大值区别是可以存在重复的元素.
127. 任务
67. 数字在排序数组中出现的次数

s.lower_bound(key_value) //返回第一个大于等于key_value的定位器
s.upper_bound(key_value) //返回第一个一个大于key_value的定位器
multiset<int>::iterator it
迭代器不想定义可以用auto it=s.lower_bound(key_value);


活动打卡代码 AcWing 136. 邻值查找

Xie_
9天前
/*
这道题目思想很简单就是找大于给定值的最小数和小于给定值的最大数
1.
找的方法使用upper_bound()前提是题目没有重复元素.需要序列有序,所以用set来维护.
需要注意的是大于给定值的最小数可以用upper_bound()由于有序那么小于给定值的最大数就是其下标-1
2.
注意哨兵元素的应用,由于upper_bound()和upper_bound()--存在越界的偶然性问题,所以要插入INT_MAX和INT_MIN否则可能会出错
*/

#include<iostream>
#include<algorithm>
#include<set>
#include<limits.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int> PII;

set<PII> datas;
set<PII>::iterator it,jt;
int n;
ll a;
PII res;
int main()
{
    cin>>n;
    cin>>a;
    res.first=INT_MAX;
    datas.insert({INT_MAX,0});
    datas.insert({INT_MIN,0});
    datas.insert({a,1});
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        it=datas.upper_bound({a,0});
        jt=it;
        jt--;
        res.first=min(abs(it->first-a),abs(jt->first-a));
        if(res.first==abs(jt->first-a)) res.second=jt->second;
        else res.second=it->second;
        cout<<res.first<<" "<<res.second<<endl;
        datas.insert({a,i});
    }
}


活动打卡代码 AcWing 133. 蚯蚓

Xie_
10天前
/*
题目思路是维护三个队列
因为发现1.还未被选钟截断 2.被截断后的x-px 3.被截断后的px 各自内部都存在着单调性,且头部最大
同时每次截断要从三类中挑选最长的
偏移量设置很巧妙可以多学习一下,
不方便每次都改变数组的每个值,那么就存上一个偏移量,插入的时候-偏移量,取出来的时候+偏移量
*/
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010,M = 7000010;;
int n,m,q,u,v,t;
int delta;
int q1[N],q2[M],q3[M];
int tt1,hh1,hh2,hh3,tt2=-1,tt3=-1;
int get_max()
{
    int x=-0x3f3f3f3f;
    if(hh1<=tt1)    x=max(x,q1[hh1]);
    if(hh2<=tt2)    x=max(x,q2[hh2]);
    if(hh3<=tt3)    x=max(x,q3[hh3]);
    if(hh1<=tt1&&x==q1[hh1])    hh1++;
    else if(hh2<=tt2&&x==q2[hh2])    hh2++;
    else if(hh3<=tt3&&x==q3[hh3])    hh3++;

    return x;
}
int main()
{
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=0;i<n;i++)
    {
        cin>>q1[i];
    }
    sort(q1,q1+n);
    reverse(q1,q1+n);
    tt1=n-1;
    for(int i=1;i<=m;i++)
    {
        int temp=get_max();
        temp+=delta;
        if(i%t==0)
            cout<<temp<<" ";
        int left=temp*1ll*u/v;
        int right=temp-left;
        delta+=q;
        q2[++tt2]=left-delta;
        q3[++tt3]=right-delta;
    }
    cout<<endl;
    for(int i=1;i<=n+m;i++)
    {
        int m=get_max();
        if (i % t== 0) 
            cout<<m+delta<<" ";
    }
}


活动打卡代码 AcWing 135. 最大子序和

Xie_
10天前
/*
单调递增队列,头部元素最小.实际上是一个头部最小,末尾插入删除的队列,
这里的插入和删除都是用的覆盖而不是真的插入删除
注意边界的初始化,如果一开始有元素那么tt=0,否则tt=-1;hh初始化任何情况下应该都为0
for 遍历所有元素
    if(不满足题目限制条件)
        对hh或者tt进行操作
    res=statement(求解题目答案)
    while(hh<=tt&&a[q[tt]]>=a[i])   tt--;
    q[++tt]=i;

*/
#include<iostream>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=300010;

int sum[N];
queue<int> que;
int q[N];
int main()
{
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    int hh=0,tt=0;
    ll res=-INF;
    for(int i=1;i<=n;i++)
    {
        if(i-q[hh]>m)    hh++;
        res=max(res,1ll*sum[i]-sum[q[hh]]);
        while(hh<=tt&&sum[q[tt]]>=sum[i])     tt--;
        q[++tt]=i;
    }
    cout<<res;
}


活动打卡代码 AcWing 132. 小组队列

Xie_
10天前
#include<iostream>
#include<queue>
using namespace std;
const int N=1000010;

int teamid[N];

int main()
{
    int n;
    int count=1;
    while(cin>>n,n)
    {
        queue<int> teams[1010];     //要放在循环里,否则某个情况没pop完就会出情况
        queue<int> nums;
        while(n--)
        {
            int cnt;
            cin>>cnt;
            for(int i=0;i<cnt;i++)
            {
                int x;
                cin>>x;
                teamid[x]=n;
            }
        }
        string command;
        cout<<"Scenario #"<<count<<endl;
        while(cin>>command,command!="STOP")
        {
            if(command=="ENQUEUE")
            {
                int x;
                cin>>x;
                int t=teamid[x];
                if(teams[t].empty()) nums.push(t);
                teams[t].push(x);
            }
            else
            {
                int t=nums.front();
                cout<<teams[t].front()<<endl;
                teams[t].pop();
                if(teams[t].empty())    nums.pop();
            }

        }
        cout<<endl;
        count++;
    }


}