头像

ベ断桥烟雨ミ_53




离线:1天前


最近来访(7)
用户头像
小灰灰我是
用户头像
sacave
用户头像
顽童
用户头像
......_519
用户头像
ermu99
用户头像
目目目
用户头像
大头娃娃菜

活动打卡代码 AcWing 1207. 大臣的旅费

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct Edge
{
    int id,w;
};
vector<Edge> h[N];
int dist[N];
void dfs(int u,int father,int distance)
{
    dist[u]=distance;
  for(int i=0;i<h[u].size();i++)
  if(h[u][i].id!=father)
  dfs(h[u][i].id,u,distance+h[u][i].w);
}
int main(){
    int n;
    cin>>n;
    int t=n-1;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    }
    dfs(1,-1,0);
    int u=1;
    for(int i=1;i<=n;i++)
    if(dist[i]>dist[u])
    u=i;

    dfs(u,-1,0);
    for(int i=1;i<=n;i++)
    if(dist[i]>dist[u])
    u=i;

    int s=dist[u];
    cout<<((long long)21+s)*s/2;
    return 0;
}



活动打卡代码 AcWing 1233. 全球变暖

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
bool st[N][N];
 int n;
typedef pair<int,int> PII;
#define x first
#define y second
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int  bfs(int x,int y)
{
    int total=0,bound=0;
    queue<PII> q;
    q.push({x,y});
    while(q.size())
    {
       PII t=q.front();
       q.pop();
       total++;
       st[t.x][t.y]=true;
       bool has_hy=false;
       for(int i=0;i<4;i++)
       {
           int a=t.x+dx[i],b=t.y+dy[i];
           if(a<1||b<1||a>n||b>n)continue;
           if(st[a][b])continue;
           if(g[a][b]=='.'){
               has_hy=true;
               continue;
           }
           if(g[a][b]=='#')
           {
               q.push({a,b});
               st[a][b]=true;
           }
       }
       if(has_hy==true)bound++;
    }
    if(total==bound)return 1;
    else return 0;
}
int main(){

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

        int cnt=0;//被淹岛屿的数量
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {

        if(g[i][j]=='#'&&!st[i][j])
        {

           cnt+=bfs(i,j);
        }
    }
    cout<<cnt<<endl;;
    return 0;
}


活动打卡代码 AcWing 1096. 地牢大师

#include <bits/stdc++.h>
using namespace std;
const int N=110;
struct Point
{
    int x,y,z;
};
int dx[6] = {1, 0, -1, 0, 0, 0};
  int dy[6] = {0, 1, 0, -1, 0, 0};
  int dz[6] = {0, 0, 0, 0, -1, 1};
int L,R,C;
char g[N][N][N];
int dist[N][N][N];
void bfs(Point start,Point end)
{
    queue<Point> q;

    q.push({start.x,start.y,start.z});
    dist[start.x][start.y][start.z]=0;
    while(q.size())
    {
        Point t=q.front();
        q.pop();
        for(int i=0;i<6;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
            if(x<1||y<1||z<1||x>L||y>R||z>C)continue;
            if(g[x][y][z]=='#')continue;
            if(dist[x][y][z]!=-1)continue;

            q.push({x,y,z});
            //g[x][y][z]='#';
            dist[x][y][z]=dist[t.x][t.y][t.z]+1;
        }
    }
}
int main(){
    while(cin>>L>>R>>C,L&&R&&C)
    {
        memset(dist, -1, sizeof(dist));
        Point start,end;
        for(int i=1;i<=L;i++)
        for(int j=1;j<=R;j++)
        for(int k=1;k<=C;k++)
        {
            cin>>g[i][j][k];
            if(g[i][j][k]=='S')
            start.x=i,start.y=j,start.z=k;
            else if(g[i][j][k]=='E')
            end.x=i,end.y=j,end.z=k;

        }
        bfs(start,end);
        int distance=dist[end.x][end.y][end.z];
        if(distance==-1)cout<<"Trapped!"<<endl;
        else printf("Escaped in %d minute(s).\n",distance);
    }
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
int a[100010];

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

    int maxv=0;
    int sd=1;
    for(int d=1,i=1;i<=n;i*=2,d++)//d为深度,或层数,i为每层开始的起点
    {
        long long  s=0;
        for(int j=i;j<i+i&&j<=n;j++)
        s+=a[j];
        if(maxv<s)
        {
            maxv=s;
            sd=d;
        }
    }
    cout<<sd;
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

宽搜bfs

#include <bits/stdc++.h>
using namespace std;
const int N=25;
typedef pair<int,int> PII;
#define x first
#define y second
char a[N][N];
int w,h;
int bfs(int sx,int sy)
{
    int cnt=0;
    queue<PII> q;
    q.push({sx,sy});
    a[sx][sy]='#';
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        cnt++;
        for(int i=0;i<4;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i];
            //if(x<1||x>h||y<1||y>w||a[x][y]=='#')continue;
            if(a[x][y]=='.')
            {
                q.push({x,y});
                a[x][y]='#';
            }
        }
    }
    return cnt;
}
int main(){

    while(cin>>w>>h,w&&h)
    {
        int startx,starty;
        for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='@')
            {
               startx=i,starty=j; 
            }
        }
        cout<<bfs(startx,starty)<<endl;
    }
    return 0;
}

深搜dfs

#include <bits/stdc++.h>
using namespace std;
int w,h;
char g[25][25];
int dfs(int x,int y)
{
    int cnt=1;
    g[x][y]='#';
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=h&&b>=1&&b<=w&&g[a][b]=='.')
        {
            cnt+=dfs(a,b);
        }
    }
    return cnt;
}
int main(){
    while(cin>>w>>h,w||h)
    {
        int sx,sy;
        for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
        {
            cin>>g[i][j];
            if(g[i][j]=='@')
            sx=i,sy=j;
        }
        cout<<dfs(sx,sy)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1224. 交换瓶子

#include <bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int count=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(i==a[j])
                {
                    count++;
                    swap(a[i],a[j]);
                }
            }
        }
    }
    //for(int i=1;i<=n;i++)cout<<a[i];
    cout<<count;
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=210;

char a[N][N];
int dist[N][N];
void bfs(PII start)
{
    queue<PII> q;
    q.push(start);
    int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
    while(!q.empty())
    {
        PII u=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=u.x+dx[i],y=u.y+dy[i];
            if(a[x][y]=='#')continue;
            if(a[x][y]=='.')
            {

                dist[x][y]=dist[u.x][u.y]+1;
                a[x][y]='#';
                q.push({x,y});
            }
            if(a[x][y]=='E')
            {
                cout<<dist[u.x][u.y]+1<<endl;
                return;
            }
        }
    }
    cout<<"oop!"<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)
    {
        memset(a,'#',sizeof a);
        memset(dist,0,sizeof dist);
        int r,c;
        cin>>r>>c;
        PII start;
        for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='S')
            start.x=i,start.y=j;
        }
        bfs(start);
    }
    return 0;
}


活动打卡代码 AcWing 1238. 日志统计

#include <bits/stdc++.h>
#define ts first
#define id second
using namespace std;
const int N=100010;
bool st[N];
int cnt[N];
pair<int,int> tz[N];

int main(){
    int n,d,k;
    cin>>n>>d>>k;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&tz[i].ts,&tz[i].id);
    }
    sort(tz,tz+n);
    for(int i=0,j=0;i<n;i++)
    {
        int id=tz[i].id;
        cnt[id]++;
        while(tz[i].ts-tz[j].ts>=d){
            cnt[tz[j].id]--;
            j++;
        }
        if(cnt[id]>=k)st[id]=true;
    }
    for(int i=0;i<=N;i++)
    if(st[i])cout<<i<<endl;
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int w[N];
struct Node{
    int l,r;
    int maxv;
}tr[N*4];
void build(int u,int l,int r)
{
    if(l==r)tr[u]={l,r,w[r]};
    else {
        tr[u]={l,r};
        int mid=(l+r)>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
    }
}
int query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;
    int mid=(tr[u].l+tr[u].r)>>1;
    int maxv=INT_MIN;
    if(mid>=l)maxv=query(u<<1,l,r);
    if(mid+1<=r)maxv=max(maxv,query(u<<1|1,l,r));
    return maxv;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    build(1,1,n);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,x,y));
    }
    return 0;
}


活动打卡代码 AcWing 1265. 数星星

#include <bits/stdc++.h>
using namespace std;
const int N=32010;
int tr[N],lever[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x,int v)
{
    for(int i=x;i<=N;i+=lowbit(i))tr[i]+=v;
}
int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        x++;
        lever[query(x)]++;
        add(x,1);
    }
    for(int i=0;i<n;i++)
    cout<<lever[i]<<endl;
    return 0;
}