头像

violet


访客:417

离线:45分钟前



violet
20小时前

有点搞不明白 蒟蒻太菜了orz 求大佬解释

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ver[N],e[N],ne[N],h[N],idx;
int n,m, dis[N],vis[N];
queue<int> q;
void add(int x,int y,int w)
{
    ver[++idx]=y,e[idx]=w;
    ne[idx]=h[x],h[x]=idx;
}
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    q.push(1);
    dis[1]=0;
   // vis[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;//出队
        for(int i=h[x];i;i=ne[i])
        {
            int y=ver[i],w=e[i];
            if(dis[y]>dis[x]+w)
            {
                dis[y]=dis[x]+w;
             //   if(!vis[y]) q.push(y),vis[y]=0;
                q.push(y);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    spfa();
    if(dis[n]>=0x3f3f3f3f/2) cout<<"impossible";
    else cout<<dis[n];
    return 0;
}



violet
2天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],ver[N],ne[N],deg[N],idx;
int n,m;
queue <int> q;
int a[N],cnt;//存拓扑序列
void add(int x,int y)
{
    ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
    deg[y]++;//入度
}
void topsort()
{
    for(int i=1;i<=n;i++)   //把入度为0的点入队
     if(deg[i]==0) q.push(i);

    while(!q.empty())
    {
        int x=q.front();
        a[++cnt]=x;
        q.pop();

        for(int i=h[x];i;i=ne[i])
        {
            int y=ver[i];
            if(--deg[y]==0) q.push(y);  //入队
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    topsort();
    if(cnt<n) cout<<-1;
    else  for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

violet
2天前
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int h[N],ver[N],ne[N],idx;
bool vis[N];
int ans=1<<30;
void add(int x,int y)
{
    ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
int dfs(int u)//以u为根的子树大小sum
{
    int sum=1;//一开始只有自己 
    int res=0;//左右子树或剩余的那一部分 最大的连通块的大小
    vis[u]=1;
    for(int i=h[u];i;i=ne[i])
    {
        int p=ver[i];
        if(!vis[p])
        {
            int sz=dfs(p);
            res=max(res,sz);
            sum+=sz;
        }
    }
    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1);
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

violet
2天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],ver[N],ne[N],idx;
int n,m,dis[N];
queue <int> q;
void add(int x,int y)
{
    ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void bfs()
{
    q.push(1); dis[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();

        for(int i=h[x];i;i=ne[i])
        {
            int y=ver[i];
            if(dis[y]==0) //没被标记过
            {
            dis[y]=dis[x]+1;
            q.push(y);              //入队
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    bfs();
    cout<<dis[n]-1;
    return 0;
}


活动打卡代码 AcWing 844. 走迷宫

violet
2天前
#include<iostream>
using namespace std;
const int N=105;
int hh=1,tt=1;
bool g[N][N],vis[N][N];
int n,m;
int dis[N][N];
struct node{
    int x;
    int y;
}q[N*N];//要开N*N个点
void bfs()
{
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    q[hh]={1,1};//get 新用法
    vis[1][1]=1;
    while(hh<=tt)
    {
        struct node t=q[hh]; 
        ++hh;                     //元素出队
     for(int i=0;i<4;i++)
    {
        int xx=t.x+dx[i], yy=t.y+dy[i];
        if(!vis[xx][yy]&&!g[xx][yy] &&xx>=1&&xx<=n&&yy>=1&&yy<=m)
        {
            vis[xx][yy]=1;
            dis[xx][yy]=dis[t.x][t.y]+1; 
            q[++tt]={xx,yy};
        }

    }    
    }
    cout<<dis[n][m];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      cin>>g[i][j];
    bfs();
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

violet
2天前
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
int n,vis[N];
int path[N];
bool col[N],dg[N],udg[N];
void out()
{
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=n;j++)
       if(j==path[i]) cout<<'Q';
           else   cout<<'.';

    cout<<endl;    
    }
}
void dfs(int y)
{
    if(y==n+1) 
    {
    out();
    cout<<endl;
    return;
    }
    for(int x=1;x<=n;x++)
    if(!col[x]&&!dg[x+y]&&!udg[y-x+n])
    {
        col[x]=dg[x+y]=udg[y-x+n]=1;
        path[y]=x;
        dfs(y+1);
        col[x]=dg[x+y]=udg[y-x+n]=0;
        path[y]=0;
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



violet
2天前

题目描述

自己看题咯

样例

略略略

以下思路在注释里

C++ 代码

//思路:鲁迅说万物的起源都要从暴力想起(bushi)
//先想暴力,枚举每一个矩形的高度,然后拓展到第一个比这个矩形高度小的左边和右边的编号 ans=h[i]*(right-left-1)
//找前面第一个比当前数矮的 这就是单调栈的典型应用,维护一个(高度)单调上升的单调栈就好      右边找一次
//     |
//   | |
// | | | |   如i=3 左边第一个比它矮的:left=2  右边第一个比它矮的:right=4 ans=h[i]*(right-left-1) = 6*(4-2-1)
// | | | | |   i=2                    left=1                     right=4                      ans= 5*(4-1-1)
// | | | | | |        枚举i=1~n ans取max 
// | | | | | |
// 1 2 3 4 5 6
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100005;
ll n,h[N];
ll l[N],r[N],ans;//l[i]=left[i] r[i]=right[i]
ll sta[N],top;//stack存下标
void find(ll p[N])
{
    h[0]=-1;//处理边界
    top=0;
    for(int i=1;i<=n;i++)
    {
        while(h[sta[top]]>=h[i]) --top;//不满足单调递增就出队 
        p[i]=sta[top];
        sta[++top]=i;//入队
    }
}
int main()
{
    while(cin>>n,n)
    {
        for(int i=1;i<=n;i++) cin>>h[i];

            find(l);
            reverse(h+1,h+1+n);
            find(r);
            ans=0;
            for(int i=1,j=n;i<=n,j>=1;i++,j--)//因为翻转了所以要特殊处理一下
            ans=max(ans,h[i]*(n-r[i]-l[j]));
            cout<<ans<<endl;
    }
    return 0;
}

作者:violet
链接:https://www.acwing.com/activity/content/code/content/423466/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。




活动打卡代码 AcWing 143. 最大异或对

violet
2天前
/*用trie树做的超级妙的做法!!!
  打开了蒟蒻的新世界
  trie树不仅能存字符
  还可以用存二进制位,要找最大的异或对 只需从高位往低位找,使得每一位尽可能找与她不同的,这样找到最后必然是与她异或最大的数 
*/ 
#include<iostream>
using namespace std;
const int N=1e5+10;
int idx,son[N*31][2],n,a[N],ans;
void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;//把第i位取出来
        if(!son[p][u]) son[p][u]=++idx;//没有就新开一个
        p=son[p][u];//走到下一个点
    }
}
int ask(int x)//返回与x最大的异或值
{
    int res=0;//存与X最大的异或值
    int p=0;  //从根开始
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u]) res=res*2+ 1,  p=son[p][!u];  //有就往与当前这位不同的分支走(因为这样异或尽可能大),否则只能将就
                  else res=res*2+ 0,  p=son[p][u];//res左移一位,给新来的那个位置上的数留出空位 ,p走到下一位 
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],insert(a[i]);//插入到tire树里
    for(int i=1;i<=n;i++)
        ans=max(ans,ask(a[i]));
    cout<<ans;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

violet
2天前
//区间极值-->单调队列
#include<bits/stdc++.h>
using namespace std;
const int N=300000+5;
int q[N],hh=1,tt=1,n,m,sum[N];
int x,ans=-1<<30;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>x,sum[i]=sum[i-1]+x;
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&i-q[hh]>m) hh++;
        ans=max(ans,sum[i]-sum[q[hh]]);
        while(hh<=tt&&sum[q[tt]]>=sum[i]) tt--;//要满足单调递增
        q[++tt]=i;
    }
    cout<<ans;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



violet
2天前
//思路:鲁迅说万物的起源都要从暴力想起(bushi)
//先想暴力,枚举每一个矩形的高度,然后拓展到第一个比这个矩形高度小的左边和右边的编号 ans=h[i]*(right-left-1)
//找前面第一个比当前数矮的 这就是单调栈的典型应用,维护一个(高度)单调上升的单调栈就好      右边找一次
//     |
//   | |
// | | | |          如i=3 左边第一个比它矮的:left=2  右边第一个比它矮的:right=4 ans=h[i]*(right-left-1) = 6*(4-2-1)
// | | | | |          i=2                    left=1                     right=4                      ans= 5*(4-1-1)    枚举i=1~n ans取max
// | | | | | |        
// | | | | | |
// 1 2 3 4 5 6
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100005;
ll n,h[N];
ll l[N],r[N],ans;//l[i]=left[i] r[i]=right[i]
ll sta[N],top;//stack存下标
void find(ll p[N])
{
    h[0]=-1;//处理边界
    top=0;
    for(int i=1;i<=n;i++)
    {
        while(h[sta[top]]>=h[i]) --top;//不满足单调递增就出队 
        p[i]=sta[top];
        sta[++top]=i;//入队
    }
}
int main()
{
    while(cin>>n,n)
    {
        for(int i=1;i<=n;i++) cin>>h[i];

            find(l);
            reverse(h+1,h+1+n);
            find(r);
            ans=0;
            for(int i=1,j=n;i<=n,j>=1;i++,j--)//因为翻转了所以要特殊处理一下
            ans=max(ans,h[i]*(n-r[i]-l[j]));
            cout<<ans<<endl;
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~