头像

zhaoly




在线 


活动打卡代码 AcWing 154. 滑动窗口

zhaoly
8小时前
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int q[N];//存储的是下标 
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1 )hh++;//保证队首元素的下标在队列中,队首元素出队 
        while(hh<=tt && a[q[tt]]>=a[i])tt--;
        //for(int j=hh;j<=tt;j++)cout<<a[q[j]]<<' ';
        //cout<<endl;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    printf("\n");
    tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1)hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

zhaoly
1天前
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素,则出栈
        if (!tt) printf("-1 ");//如果栈空,则没有比该元素小的值。
        else printf("%d ", stk[tt]);//栈顶元素就是左侧第一个比它小的元素。
        stk[ ++ tt] = x;
    }
    return 0;
}





活动打卡代码 AcWing 826. 单链表

zhaoly
1天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int head;
int e[N],ne[N],idx;
void init()
{
    head=-1;
    idx=0;
}
void add_head(int a)
{
    e[idx]=a,ne[idx]=head,head=idx++;
}
void add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(int k)
{
    ne[k]=ne[ne[k]];
}
int main()
{
    int m;
    cin>>m;
    init();
    while(m--)
    {
        char opt;
        cin>>opt;
        if(opt=='H')
        {
            int x;
            cin>>x;
            add_head(x);
        }
        else if(opt=='D')
        {
            int k;
            cin>>k;
            if(k==0)head=ne[head];
            remove(k-1);
        }
        else
        {
            int k,x;
            cin>>k>>x;
            add(k-1,x);
        }

    }
    for(int i=head;i!=-1;i=ne[i])
        printf("%d ",e[i]);

    return 0;
} 



zhaoly
1天前

```

include[HTML_REMOVED]

using namespace std;
const int N=510;
int g[N][N];
int n,m;
int s[N],dist[N];
int dfs()
{
dist[1]=0;

for(int i=1;i<=n;i++)
{
    int t=-1;//假设还没有找到这样的点 
    for(int j=1;j<=n;j++) //先找到当前剩下的最短路径
    {
        if(!s[j] && (t==-1 || dist[t]>dist[j]))
            t=j;
    }
    s[t]=1;
    for(int j=1;j<=n;j++)
        if(dist[j]>dist[t]+g[t][j]) 
            dist[j]=dist[t]+g[t][j];

}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];

}
int main()
{

scanf("%d%d",&n,&m);
int x,y,z;
memset(g,0x3f,sizeof g);
memset(dist,0x3f,sizeof dist);

for(int i=1;i<=m;i++)
{
    scanf("%d%d%d",&x,&y,&z);
    g[x][y]=min(g[x][y],z);
}
printf("%d",dfs());
return 0;

}
```



活动打卡代码 AcWing 843. n-皇后问题

zhaoly
1天前
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int col[N],dg[N],udg[N],n;
char g[N][N]; 
void dfs(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                printf("%c",g[i][j]);
            } 
            printf("\n");

        }
        printf("\n");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!col[i] && !dg[k+i] && !udg[n-k+i])
        {
            g[k][i]='Q';
            col[i] = dg[k+i] = udg[n-k+i] = 1;
            dfs(k+1);
            col[i] = dg[k+i] = udg[n-k+i] = 0;
            g[k][i]='.';
        }
    }
}



int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]='.';
    dfs(1);
    return 0;
}


活动打卡代码 AcWing 842. 排列数字

zhaoly
1天前
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int a[N],n,u[N];

void dfs(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!u[i])
        {
            a[k]=i;
            u[i]=1;
            dfs(k+1);
            u[i]=0;
        }
    }
}



int main()
{
    cin>>n;
    memset(u,0,sizeof u);
    dfs(1);
    return 0;
} 


活动打卡代码 AcWing 788. 逆序对的数量

zhaoly
6天前
//这里填你的代码^^ 注意爆int
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int a[N],q[N];
int n;
ll res=0;
void merge_sort(int l,int r)
{
    if(l==r)return ;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1;
    int cnt=0;
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])
            q[++cnt]=a[i++];
        else
        {
            q[++cnt]=a[j++];
            res+=mid-i+1; 
        }

    }
    while(i<=mid)
        q[++cnt]=a[i++];
    while(j<=r)
        q[++cnt]=a[j++];
    for(int i=l,j=1;i<=r;i++,j++)
        a[i]=q[j];  

}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    merge_sort(1,n); 
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

zhaoly
6天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int a[N],q[N];
int n;
void merge_sort(int l,int r)
{
    if(l==r)return ;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1;
    int cnt=0;
    while(i<=mid && j<=r)
    {
        if(a[i]<a[j])
            q[++cnt]=a[i++];
        else
            q[++cnt]=a[j++]; 
    }
    while(i<=mid)
        q[++cnt]=a[i++];
    while(j<=r)
        q[++cnt]=a[j++];
    for(int i=l,j=1;i<=r;i++,j++)
        a[i]=q[j];  

}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    merge_sort(1,n); 
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}



zhaoly
7天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
int qsort(int l,int r,int k)
{
    if(l==r)return a[l];
    //l+=rand()%(r-l+1); 
    int x=a[l];
    int i=l,j=r;
    while(i<j)
    {
        while(i<j && a[j]>x)j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j && a[i]<x)i++;
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=x;
    if(i-l+1>=k)
        qsort(l,i,k);
    else
        qsort(i+1,r,k-(i-l+1));

}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    cout<<qsort(1,n,k)<<endl;
    return 0;
} 


活动打卡代码 AcWing 785. 快速排序

zhaoly
7天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
void qsort(int l,int r)
{
    if(l>=r)return ;
    swap(a[l], a[l + rand() % (r - l + 1)]);
    int x=a[l];
    int i=l,j=r;
    while(i<j)
    {
        while(i<j && a[j]>x)j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j && a[i]<x)i++;
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=x;
    qsort(l,i-1);
    qsort(i+1,r);

}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    qsort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]); 
    return 0;
}