头像

不高兴的兽奶




离线:1小时前


最近来访(119)
用户头像
种花家的蒟蒻
用户头像
我是雷电将军的狗
用户头像
月亮供电不足
用户头像
77777777777
用户头像
fw_orz
用户头像
志者
用户头像
baiwang
用户头像
sg100615
用户头像
种花家的兔兔
用户头像
Skuy
用户头像
知北游
用户头像
Serendipity-s
用户头像
山川不念
用户头像
不要不听话
用户头像
天元之弈
用户头像
ht_th
用户头像
Balance_1
用户头像
牛马人
用户头像
V1
用户头像
XoeT.

活动打卡代码 AcWing 1221. 四平方和

#include<bits/stdc++.h>

using namespace std;

const int N = 2500010;

int n,m;

struct Sum
{
    int s,c,d;
    bool operator< (const Sum &t) const 
    {
        if(s!=t.s) return s<t.s;
        if(c!=t.c) return c<t.c;
        return d<t.d;
    }
}sum[N];

int main()
{
    cin>>n;

    //将c和d存起来
    for(int c=0;c*c<=n;c++)
        for(int d=c;c*c+d*d<=n;d++)
            sum[m++]={c*c+d*d,c,d};

    sort(sum,sum+m);

    //枚举a和b
    for(int a=0;a*a<=n;a++)
        for(int b=a;a*a+b*b<=n;b++)
        {
            int t=n-a*a-b*b;

            int l=0,r=m-1;
            while(l<r)
            {
                int mid=l+r>>1;
                if(sum[mid].s>=t) r=mid;
                else l=mid+1;
            }

            if(sum[l].s==t)
            {
                printf("%d %d %d %d\n",a,b,sum[l].c,sum[l].d);
                return 0;
            }
        }
}


活动打卡代码 AcWing 99. 激光炸弹

#include<bits/stdc++.h>

using namespace std;

const int N = 5010;

int n,R;
int s[N][N];

int main()
{
    cin>>n>>R;

    while(n--)
    {
        int x,y,w;
        cin>>x>>y>>w;
        s[++x][++y]+=w;
    }

    for(int i=1;i<=5001;i++)
        for(int j=1;j<=5001;j++)
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

    int res=0;      
    for(int i=R;i<=5001;i++)
        for(int j=R;j<=5001;j++)
            res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);

    if(R>=5000) res=s[5001][5001];

    cout<<res<<endl;

    return 0;
}



#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
int h[N];

bool check(int e)
{
    for(int i=1;i<=n;i++)
    {
        e=e*2-h[i];
        if(e>=1e5) return true;
        if(e<0) return false;
    }
    return true;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>h[i];

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

    cout<<l<<endl;

    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m,q;
int a[N][N],s[N][N];

int main()
{
    cin>>n>>m>>q;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }

    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 795. 前缀和

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,m;
int a[N],s[N];

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include<bits/stdc++.h>

using namespace std;

int main()
{
    double n;
    cin>>n;

    double l=-22,r=22;
    while(r-l>1e-9)
    {
        double mid=(l+r)/2;
        if(mid*mid*mid<=n) l=mid;
        else r=mid;
    }

    printf("%lf\n",r);

    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,m;
int a[N];

int SL(int q[],int l,int r,int x)
{
    while(l<r)
    {
        int mid=l+r>>1;
        if(q[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l;
}

int SR(int q[],int l,int r,int x)
{
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(q[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) cin>>a[i];

    while(m--)
    {
        int x;
        cin>>x;

        if(a[SL(a,0,n-1,x)]!=x) cout<<"-1 -1"<<endl;
        else cout<<SL(a,0,n-1,x)<<' '<<SR(a,0,n-1,x)<<endl;
    }

    return 0;
}



莫欺少年穷,修仙之旅在这开始—>算法基础课题解

注意:

1. 将字符串映射成 P 进制的哈希值
2. 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA皆为0
3. 冲突问题:通过巧妙设置P (131 或 13331) , Q (2 ^ 64)的值,一般可以理解为不产生冲突
4. h[i] 表示 str[1~i],即 str 的前缀和数组
#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n,m;
char str[N];
int p[N],h[N];

//获取[l,r]的字符串哈希值
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    cin>>n>>m>>str+1;

    //预处理p数组和h数组
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];    
    }

    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1,r1)==get(l2,r2)?"Yes":"No")<<endl;
    }

    return 0;
}



莫欺少年穷,修仙之旅在这开始—>算法基础课题解

1. STL的map使用方法

#include<bits/stdc++.h>

using namespace std;

int n;
string op,str;
map<string,int> cnt;

int main()
{
    cin>>n;

    while(n--)
    {
        cin>>op>>str;

        if(op=="I") cnt[str]++;

        if(op=="Q") cout<<(cnt[str]?"Yes":"No")<<endl;
    }

    return 0;
}

2. 拉链法

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,x;
char op;
int h[N],e[N],ne[N],idx;

//插入一个数 x
void insert(int x)
{
    //使k是0~N-1内的数
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}

//寻找一个数 x
bool find(int x)
{
    int k=(x%N+N)%N;
    for(int i=h[k];~i;i=ne[i])
        if(e[i]==x)
            return true;

    return false;
}

int main()
{
    cin>>n;

    //初始化数组
    memset(h,-1,sizeof h);

    while(n--)
    {
        cin>>op>>x;

        if(op=='I') insert(x);

        if(op=='Q') cout<<(find(x)?"Yes":"No")<<endl;
    }

    return 0;
}

3. 开放寻址法

#include<bits/stdc++.h>

using namespace std;

const int N = 200003, INF = 0x3f3f3f3f;

int n,x;
char op;
int h[N];

//寻找 x,如果有人但不是 x,则找下一个坑位,若发现一个空位,则 x 不存在,并返回该位置
int find(int x)
{
    int k=(x%N+N)%N;
    while(h[k]!=INF&&h[k]!=x)
    {
        k++;
        if(k==N) k=0;
    }

    return k;
}

int main()
{
    cin>>n;

    //初始化数组
    memset(h,0x3f,sizeof h);

    while(n--)
    {
        cin>>op>>x;

        if(op=='I') h[find(x)]=x;

        if(op=='Q') cout<<(h[find(x)]!=INF?"Yes":"No")<<endl;
    }

    return 0;
}



莫欺少年穷,修仙之旅在这开始—>算法基础课题解

注意:

1. ph[m] = cnt表示第 m 个插入的数的下标是 cnt,hp[cnt] = m表示下标是 cnt 的数是第 m 个插入的数
2. heap_swap(a,b)表示交换 h[a] 和 h[b],并维护 ph 和 hp 两个数组
3. 删除第 k 个数时,需要提前把第 k 个数的下标存储起来
#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
string op;
int k,x;
int h[N],ph[N],hp[N],cnt,m;

//交换h[a]和h[b],并维护ph和hp两个数组
void heap_swap(int a,int b)
{
    swap(h[a],h[b]);
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
}

//往下移
void down(int u)
{
    int t=u;
    if(u*2<=cnt&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cnt&&h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}

//往上移
void up(int u)
{
    while(u/2&&h[u/2]>h[u])
    {
        heap_swap(u,u/2);
        u>>=1;
    }
}

int main()
{
    cin>>n;

    while(n--)
    {
        cin>>op;

        //插入一个数 x
        if(op=="I")
        {
            cin>>x;
            ph[++m]=++cnt;
            hp[cnt]=m;
            h[cnt]=x;
            up(cnt);
        }

        //输出当前集合中的最小值
        if(op=="PM") cout<<h[1]<<endl;

        //删除当前集合中的最小值
        if(op=="DM") 
        {
            heap_swap(1,cnt--);
            down(1);
        }

        //删除第 k 个插入的数
        if(op=="D")
        {
            cin>>k;
            k=ph[k];
            heap_swap(k,cnt--);
            down(k);
            up(k);
        }

        //修改第 k 个插入的数,将其变为 x
        if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;
            down(ph[k]);
            up(ph[k]);
        }
    }

    return 0;
}