头像

Pecoz


访客:302

离线:1分钟前


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

Pecoz
18小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,e[N],ne[N],h[N],num[N],idx;
int ans=N+10;
int v[N];
void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x)
{
    v[x]=1,num[x]=1;
    int res=0;
  for(int i=h[x];i!=-1;i=ne[i])
  {
    int y=e[i];
    if(!v[y])
    {
        dfs(y);
      num[x]+=num[y];
      res=max(res,num[y]);
    }
  }
  res=max(res,n-num[x]);
  ans=min(ans,res);
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++)
    {
      int a,b;
      cin>>a>>b;
      add(a,b);
      add(b,a);
    }
    dfs(1);
    cout<<ans;
return 0;
}



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

Pecoz
19小时前
BFS遍历
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n,m,e[N],ne[N],h[N],d[N],idx;
void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
  queue<int>q;
  q.push(1);
  while(!q.empty())
  {
    int x=q.front();
    q.pop();
    for(int i=h[x];i!=-1;i=ne[i])
    {
      int y=e[i];
      if(!d[y])
      {
       d[y]=d[x]+1;
       q.push(y);
      }
    }
  }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
      int a,b;
      cin>>a>>b;
      add(a,b);
    }
    bfs();
    if(!d[n])
        cout<<-1;
    else
        cout<<d[n];
return 0;
}




Pecoz
1天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,cnt,e[N],ne[N],idx,d[N],h[N],a[N];
void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topo()
{
   queue<int>tp;
   for(int i=1;i<=n;i++)
   {
     if(d[i]==0)
     {
        tp.push(i);
     }
   }
   while(!tp.empty())
   {
     int x=tp.front();
     tp.pop();
     a[cnt++]=x;
     for(int i=h[x];i!=-1;i=ne[i])
     {
       int y=e[i];
       if(--d[y]==0)
        tp.push(y);
     }
   }
   return cnt==n;
}
int main()
{
   cin>>n>>m;
   memset(h,-1,sizeof h);
   for(int i=1;i<=m;i++)
   {
     int a,b;
     cin>>a>>b;
     add(a,b);
     d[b]++;
   }
   if(topo())
   {
    for(int i=0;i<cnt;i++)
        cout<<a[i]<<' ';
   }
   else
    cout<<-1;
return 0;
}




Pecoz
1天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N],dir[4][2]={1,0,-1,0,0,1,0,-1};
bool v[N][N];
int n,m;
struct node
{
 int x,y,step;
}pre[N][N];//开一个记忆数组
queue<node>tp;
stack<node>hh;
int bfs(int x,int y,int step)
{
   node s,t;
   while(!tp.empty())
    {
      s=tp.front();
      tp.pop();
      if(s.x==n&&s.y==m)
      {
          int a=n,b=m;
        while(pre[a][b].x!=1||pre[a][b].y!=1)
        {
          hh.push({pre[a][b].x,pre[a][b].y});
          int aa=a,bb=b;
          a=pre[aa][bb].x;
          b=pre[aa][bb].y;
        }
        return s.step;
      }
      for(int i=0;i<4;i++)
      {
         t.x=s.x+dir[i][0];
         t.y=s.y+dir[i][1];
         if(!v[t.x][t.y]&&1<=t.x&&t.x<=n&&1<=t.y&&t.y<=m&&!a[t.x][t.y])
         {
           v[t.x][t.y]=1;
           t.step=s.step+1;
           pre[t.x][t.y].x=s.x;
           pre[t.x][t.y].y=s.y;
           tp.push(t);
         }
      }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=m;j++)
       {
          cin>>a[i][j];
       }
    }
    tp.push({1,1,0});
    v[1][1]=1;
    cout<<bfs(1,1,0)<<endl;
    while(!hh.empty())//从栈中输出的即为顺序
    {
      cout<<hh.top().x<<' '<<hh.top().y<<endl;
      hh.pop();
    }
return 0;
}


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

Pecoz
1天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N],dir[4][2]={1,0,-1,0,0,1,0,-1};
bool v[N][N];
int n,m;
struct node
{
 int x,y,step;
};
queue<node>tp;
int bfs(int x,int y,int step)
{
   node s,t;
   while(!tp.empty())
    {
      s=tp.front();
      tp.pop();
      if(s.x==n&&s.y==m)
      {
        return s.step;
      }
      for(int i=0;i<4;i++)
      {
         t.x=s.x+dir[i][0];
         t.y=s.y+dir[i][1];
         if(!v[t.x][t.y]&&1<=t.x&&t.x<=n&&1<=t.y&&t.y<=m&&!a[t.x][t.y])
         {
           v[t.x][t.y]=1;
           t.step=s.step+1;
           tp.push(t);
         }
      }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=m;j++)
       {
          cin>>a[i][j];
       }
    }
    tp.push({1,1,0});
    v[1][1]=1;
    cout<<bfs(1,1,0);
return 0;
}



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

Pecoz
2天前
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
char g[N][N];
int dg[N],col[N],udg[N],n;
void dfs(int u)
{
   if(u==n)
   {
    for(int i=0;i<n;i++)
        puts(g[i]);
    puts("");
    return ;
   }
   else
   {
     for(int i=0;i<n;i++)
     {
       if(!col[i]&&!dg[u+i]&&!udg[n-i+u])
       {
          col[i]=dg[u+i]=udg[n-i+u]=1;
          g[u][i]='Q';
          dfs(u+1);
          col[i]=dg[u+i]=udg[n-i+u]=0;
          g[u][i]='.';
       }
     }
   }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
      {
        g[i][j]='.';
      }
    }
    dfs(0);
return 0;
}



活动打卡代码 AcWing 899. 编辑距离

Pecoz
2天前
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
char g[N][N];
int dg[N],col[N],udg[N],n;
void dfs(int u)
{
   if(u==n)
   {
    for(int i=0;i<n;i++)
        puts(g[i]);
    puts("");
    return ;
   }
   else
   {
     for(int i=0;i<n;i++)
     {
       if(!col[i]&&!dg[u+i]&&!udg[n-i+u])
       {
          col[i]=dg[u+i]=udg[n-i+u]=1;
          g[u][i]='Q';
          dfs(u+1);
          col[i]=dg[u+i]=udg[n-i+u]=0;
          g[u][i]='.';
       }
     }
   }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
      {
        g[i][j]='.';
      }
    }
    dfs(0);
return 0;
}



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

Pecoz
2天前
#include<bits/stdc++.h>
using namespace std;
int a[10],v[10];
int n;
void dfs(int x)
{
   if(x==n)
   {
     for(int i=0;i<n;i++)
        cout<<a[i]+1<<' ';
     puts("");
     return ;
   }
   else
   {
      for(int i=0;i<n;i++)
      {
        if(!v[i])
        {
          a[x]=i;
          v[i]=1;
          dfs(x+1);
          v[i]=0;
        }
      }
   }
}
int main()
{
    cin>>n;
    dfs(0);
return 0;
}



新鲜事 原文

Pecoz
4天前
发现y总模板总是学了就忘,得放慢下脚步沉淀一下了


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

Pecoz
5天前
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int P =131,N = 1e6+10;
ull p[N],h[N];
char a[N];
ull get(int l,int r)
{
  return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int m;
    cin>>a+1>>m;
    int n=strlen(a+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
     h[i]=h[i-1]*P+a[i]-'a'+1;
     p[i]=p[i-1]*P;
    }
    while(m--)
    {
      int l1,r1,l2,r2;
      cin>>l1>>r1>>l2>>r2;
      if(get(l1,r1)==get(l2,r2))
        puts("Yes");
      else
        puts("No");
    }
return 0;
}