个人空间 - AcWing

楚天

God Bless You

关注数

粉丝数

阅读量

2055

+关注发消息

在线

活动打卡代码 AcWing 106. 动态中位数

楚天
4小时前

                #include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
    cin>>T;
    while(T--)
    {   
        int n,m;
        cin>>n>>m;
        priority_queue<int,vector<int> , less<int> > max_heap;//
        priority_queue<int, vector<int>, greater<int> > min_heap;
        int cnt=0;
        printf("%d %d\n",n,(m+1)/2);
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            max_heap.push(x);
            if(min_heap.size()&&(min_heap.top()<max_heap.top()))
            {
                int a=min_heap.top();
                int b=max_heap.top();
                min_heap.pop();
                max_heap.pop();
                min_heap.push(b);
                max_heap.push(a);
            }
            if(max_heap.size()>min_heap.size()+1)
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
            if(i&1)
            {
                printf("%d ",max_heap.top());
                 if ( ++ cnt % 10 == 0) puts("");
            }
        }
         if (cnt % 10) puts("");
    }
    return 0;
}


            

活动打卡代码 AcWing 106. 动态中位数

楚天
5小时前

                #include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
    cin>>T;
    while(T--)
    {   
        int n,m;
        cin>>n>>m;
        priority_queue<int,vector<int> , less<int> > max_heap;//
        priority_queue<int, vector<int>, greater<int> > min_heap;
        int cnt=0;
        printf("%d %d\n",n,(m+1)/2);
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            max_heap.push(x);
            if(min_heap.size()&&(min_heap.top()<max_heap.top()))
            {
                int a=min_heap.top();
                int b=max_heap.top();
                min_heap.pop();
                max_heap.pop();
                min_heap.push(b);
                max_heap.push(a);
            }
            if(max_heap.size()>min_heap.size()+1)
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
            if(i&1)
            {
                printf("%d ",max_heap.top());
                 if ( ++ cnt % 10 == 0) puts("");
            }
        }
         if (cnt % 10) puts("");
    }
    return 0;
}

            

题目讨论 AcWing 106. 答案错误

楚天
5小时前

#include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
    cin>>T;
    while(T--)
    {   
        int a,b;
        cin>>a>>b;
        priority_queue<int,vector<int> , less<int> > max_heap;
        priority_queue<int, vector<int>, greater<int> > min_heap;
        int cnt=0;
        printf("%d %d\n",a,(b+1)/2);
        for(int i=1;i<=b;i++)
        {
            int x;
            cin>>x;
            max_heap.push(x);
            if(min_heap.size()&&(min_heap.top()<max_heap.top()))
            {
                int a=min_heap.top();
                int b=max_heap.top();
                min_heap.pop();
                max_heap.pop();
                min_heap.push(b);
                max_heap.push(a);
            }
            if(max_heap.size()>min_heap.size()+1)
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
            if(!(i&1))
            {
                printf("%d ",max_heap.top());
                 if ( ++ cnt % 10 == 0) puts("");
            }
        }
         if (cnt % 10) puts("");
    }
    return 0;
}

大佬能看一下吗，不知道这份代码哪里出错了

新鲜事原文

楚天
10小时前

AcWing《语法基础课》拼团优惠！https://www.acwing.com/activity/content/introduction/21/group_buy/1989/

活动打卡代码 AcWing 1076. 迷宫问题

楚天
21小时前

                #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
PII pre[N][N];
int g[N][N];
int st[N][N];
queue<PII> q;
int n;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
void bfs()
{
    q.push({n-1,n-1});  
    st[n-1][n-1]=1;
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {

            int a=t.first+dx[i];
            int b=t.second+dy[i];
            if(a>=n||a<0||b>=n||b<0)continue;
            if(g[a][b]==1)continue;
            if(st[a][b]==1)continue;
            st[a][b]=1;
            q.push({a,b});
            pre[a][b]=t;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>g[i][j];
    bfs();
    PII end; 
    end.first=0;
    end.second=0;;
    while(end.first!=n-1||end.second!=n-1)
    {
       cout<<end.first<<' '<<end.second<<endl;
        end=pre[end.first][end.second];

    }
    cout<<n-1<<' '<<n-1<<endl;
    return 0;
}


            

活动打卡代码 AcWing 175. 电路维修

楚天
22小时前

                #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
const int N=600;
int n,m;
char g[N][N];
int dist[N][N];
int st[N][N];

int bfs()
{
    memset(st,0,sizeof(st));
    memset(dist,0x3f,sizeof(dist));
    deque<PII> q;
    q.push_back({0,0});
    dist[0][0]=0;

    int dx[4]={-1,-1,1,1};
    int dy[4]={-1,1,1,-1};
    int ix[4]={-1,-1,0,0};
    int iy[4]={-1,0,0,-1};
    char cs[10]="\\/\\/";
    while(q.size())
    {
        PII t=q.front();
        q.pop_front();
        int x=t.first;
        int y=t.second;
        if(st[x][y])continue;
        st[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            int ga=x+ix[i];
            int gb=y+iy[i];
            if(a>=0&&a<=n&&b>=0&&b<=m){
            int w=0;
            if(g[ga][gb]!=cs[i])w=1;
            if(dist[a][b]>dist[x][y]+w)
            {
                dist[a][b]=dist[x][y]+w;
                if(w)q.push_back({a,b});
                else q.push_front({a,b});
            }
        }
    }
    }
    if(dist[n][m]==0x3f3f3f3f)return -1;
     return dist[n][m];
}

int main()
{
 int t;
 cin>>t;
 while(t--) 
 {
     cin>>n>>m;
     for(int i=0;i<n;i++)scanf("%s",g[i]);
     int t=bfs();
     if(t==-1)cout<<"NO SOLUTION"<<endl;
     else cout<<t<<endl;
 }

}

            

问题循环队列有什么用处

楚天
1天前

循环队列有什么用处

活动打卡代码 AcWing 346. 走廊泼水节

楚天
2天前

                #include<bits/stdc++.h>
using namespace std;
const int N=4e5;
int fa[N];
int siz[N];
struct node{
    int a,b,c;
}e[N];
int t,n;
int res;
bool cmp(node a,node b)
{
    return a.c<b.c;
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

int main()
{
    cin>>t;
    for(int y=1;y<=t;y++)
    {
        res=0;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            e[i]={a,b,c};
        }
        sort(e+1,e+n,cmp);//记得这里的边的上界是n，注意细节问题
        for(int i=1;i<=n;i++)
        {siz[i]=1;fa[i]=i;}
        for(int i=1;i<=n-1;i++)
        {
            int u=find(e[i].a);
            int v=find(e[i].b);
            int w=e[i].c;
            if(u!=v)
            {
                fa[u]=v;
                res=res+(siz[u]*siz[v]-1)*(w+1);
                siz[v]+=siz[u];
            }
        }
        cout<<res<<endl;
    }
    return 0;
}


            

活动打卡代码 AcWing 861. 二分图的最大匹配

楚天
2天前

                #include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int head[N],ne[N],idx,ver[N];
void add(int u,int v)
{
    ne[idx]=head[u];
    ver[idx]=v;
    head[u]=idx;
    idx++;
}
int n1,n2 ,m;
int res;
int match[N],st[N];
bool find(int x)
{
    for(int i=head[x];i!=-1;i=ne[i])
    {
        int j=ver[i];
        if(!st[j])
        {
            st[j]=1;
            if(match[j]==0||find(match[j]))
            {
                match[j]=x;
                return true;
            }
        }
    }
    return false;   
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n1>>n2>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n1;i++)
    {
        memset(st,0,sizeof(st));
        if(find(i))res++;
    }
    cout<<res<<endl;
}

            

活动打卡代码 AcWing 1145. 北极通讯网络

楚天
2天前

                #include<bits/stdc++.h>
using namespace std;
const int N=2e6;
int fa[N];
int n,k;
typedef pair<int,int> PII;
#define x first
#define y second
PII q[N];
int shu;
double res;
int cnt;
int find(int x)
{
    if(fa[x]==x)return fa[x];
    return fa[x]=find(fa[x]);
}
struct node{
    int a,b;
    double c;
}e[N];
double get_dist(PII a,PII b)
{
    int dx=a.x-b.x;
    int dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

bool cmp(node a,node b)
{
    return a.c<b.c;
}
int main()
{
    cin>>n>>k;
    shu=n;  
    for(int i=1;i<=n;i++)   fa[i]=i;
    for(int i=1;i<=n;i++)
    cin>>q[i].x>>q[i].y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
                double w=get_dist(q[i],q[j]);
                e[++cnt]={i,j,w};
        }
    sort(e+1,e+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
    {
        int a=e[i].a;
        int b=e[i].b;
        if(shu<=k)break;
        if(find(a)!=find(b))
        {
            fa[find(a)]=find(b);
            shu--;
            res=e[i].c;
        }
    }
    printf("%.2lf",res);
}


            

0 评论

0 评论

1 评论

0 评论

0 评论

0 评论

2 评论

0 评论

0 评论

0 评论