4.20学习记录

P4281 [AHOI2008]紧急集合 / 聚会

看样子像是树剖就写了树剖，，
虽然当时看到了125mb的内存限制但是我依然头铁

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define mid (l+r)/2
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 5e5+1000;
int n,m;
struct node
{
    
    int nex,to;
};
node edge[N<<1];
int head[N],tot;
int dep[N],son[N],fa[N],siz[N];
int top[N],cnt,nid[N];
void add(int from,int to)
{
    
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void DFS1(int now,int fath)
{
    
    dep[now]=dep[fath]+1;
    siz[now]=1;son[now]=0;
    fa[now]=fath;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to==fath)
            continue;
        DFS1(edge[i].to,now);
        siz[now]+=siz[edge[i].to];
        if(siz[edge[i].to]>siz[son[now]])
        {
    
            son[now]=edge[i].to;
        }
    }
}
void DFS2(int now,int topx)//topx，先重儿子再轻儿子
{
    
    top[now]=topx;
    nid[now]=++cnt;
    if(son[now])
    {
    
        DFS2(son[now],topx);
    }
    else
        return ;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to!=fa[now]&&edge[i].to!=son[now])
        {
    
            DFS2(edge[i].to,edge[i].to);
        }
    }
}
int LCA(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
        {
    
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return dep[x]>dep[y]?y:x;
}
//segtree
int tree[N<<2];
void up(int p)
{
    
    tree[p]=tree[ls]+tree[rs];
}
void bulid(int l,int r,int p)
{
    
     if(l==r)
     {
    
         tree[p]=1;
         return ;
     }
     bulid(l,mid,ls);
     bulid(mid+1,r,rs);
     up(p);
}
int query(int l,int r,int p,int nl,int nr)
{
    
    int res=0;
    if(l>=nl&&r<=nr)
    {
    
        return tree[p];
    }
    if(nl<=mid)
    {
    
        res+=query(l,mid,ls,nl,nr);
    }
    if(nr>mid)
    {
    
        res+=query(mid+1,r,rs,nl,nr);
    }
    return res;
}

//use
int q_range(int x,int y)
{
    
    int ans=0;
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
        {
    
            swap(x,y);
        }
        ans+=query(1,n,1,nid[top[x]],nid[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
    {
    
        swap(x,y);
    }
    ans+=query(1,n,1,nid[x],nid[y]-1);
    return ans;
}
int main()
{
    
    fastio
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=n-1;i++)
    {
    
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    DFS1(1,0);
    DFS2(1,1);
    bulid(1,n,1);
    for(int i=1,x,y,z,u,v,t,f,ans;i<=m;i++)
    {
    
        cin>>x>>y>>z;
        u=LCA(x,y);v=LCA(y,z);t=LCA(z,x);
        f=dep[u]>dep[v]?u:v;
        f=dep[f]>dep[t]?f:t;
        ans=q_range(x,f)+q_range(y,f)+q_range(z,f);
        cout<<f<<" "<<ans<<endl;
    }
    return 0;
}
/* 1 2 3 4 5 6 */

然后喜提5个点MLE

发觉这题其实用不上树剖的线段树部分，只要求个LCA就行了。

#include <bits/stdc++.h>
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define mid (l+r)/2
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 5e5+1000;
int n,m;
struct node
{
    
    int nex,to;
};
node edge[N<<1];
int head[N],tot;
int dep[N],son[N],fa[N],siz[N];
int top[N],cnt,nid[N];
void add(int from,int to)
{
    
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void DFS1(int now,int fath)
{
    
    dep[now]=dep[fath]+1;
    siz[now]=1;son[now]=0;
    fa[now]=fath;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to==fath)
            continue;
        DFS1(edge[i].to,now);
        siz[now]+=siz[edge[i].to];
        if(siz[edge[i].to]>siz[son[now]])
        {
    
            son[now]=edge[i].to;
        }
    }
}
void DFS2(int now,int topx)//topx，先重儿子再轻儿子
{
    
    top[now]=topx;
    nid[now]=++cnt;
    if(son[now])
    {
    
        DFS2(son[now],topx);
    }
    else
        return ;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to!=fa[now]&&edge[i].to!=son[now])
        {
    
            DFS2(edge[i].to,edge[i].to);
        }
    }
}
int LCA(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
        {
    
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return dep[x]>dep[y]?y:x;
}
int main()
{
    
    fastio
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=n-1;i++)
    {
    
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    DFS1(1,0);
    DFS2(1,1);
    for(int i=1,x,y,z,u,v,t,f,ans;i<=m;i++)
    {
    
        cin>>x>>y>>z;
        u=LCA(x,y);v=LCA(y,z);t=LCA(z,x);
        f=dep[u]>dep[v]?u:v;
        f=dep[f]>dep[t]?f:t;
        ans=dep[x]+dep[y]+dep[z]-dep[u]-dep[v]-dep[t];
        cout<<f<<" "<<ans<<endl;
    }
    return 0;
}
/* 1 2 3 4 5 6 */

Image Perimeters

上课的时候老师给的一个题。
题意：给定一张图，然后又“X”有“.”，我们认为一个“X”的四周（上下左右）以及四个对角的“X”都是相连的，那么请问，一张图中联通的一片“X”的周长最大是多少。
注意：不会有“X”包围“.”的情况。
思路1：直接按照联通块去搜索，但是发现对角相连的情况过于复杂，结合DFS很难实现，考虑到应该是铜牌级别的题目，所以想想别的方法

思路2：将原图拓展一圈“.”，然后对于“.”只要碰壁就让周长加1，但是发现无法判断是否属于同一联通块，所以我打算用dsu重构哈希映射来做，但是好像也不是最优解

思路3：将原图拓展一圈“.”，然后对于“X”，去标记X的边界

#include <stdio.h>
#include <string.h>

char maps[35][35];
int flag[35][35];
int mov1[4][2]= {
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};
int mov2[4][2]= {
    {
    1,1},{
    1,-1},{
    -1,1},{
    -1,-1}};
int r,c;
int click_x,click_y;
int total;///周长
void dfs(int x,int y)
{
    
    if(flag[x][y]!=0) return ;
    else
    {
    
        flag[x][y]=1;
        int tx;
        int ty;
        for(int k=0; k<4; k++)
        {
    
            tx=x+mov1[k][0];
            ty=y+mov1[k][1];

            if(maps[tx][ty]=='X'&&flag[tx][ty]==0)
                dfs(tx,ty);
            else if(maps[tx][ty]=='.')
                total++;
        }
        for(int k=0; k<4; k++)
        {
    
            tx=x+mov2[k][0];
            ty=y+mov2[k][1];
            if(maps[tx][ty]=='X'&&flag[tx][ty]==0)
                dfs(tx,ty);
        }
    }
}
int main()
{
    
    while(scanf("%d%d%d%d",&r,&c,&click_x,&click_y),r)
    {
    
        total=0;
        memset(flag,0,sizeof(flag));
        memset(maps,'.',sizeof(maps));
        for(int i=1; i<=r; i++)
        {
    
            scanf("%s",maps[i]+1);
            maps[i][c+1]='.';
        }
        dfs(click_x,click_y);
        printf("%d\n",total);
    }
    return 0;
}