个人空间 - AcWing

Fingerscrossed

算法基础课，提高课

关注数

粉丝数

阅读量

295

+关注发消息

离线：1天前

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

Fingerscrossed
1天前

dfs表示返回以u为根节点子树的点的个数（包括n）,每次dfs下一层迭代一次删除u子树后的节点最大值，将这些最大值的最小值迭代成答案。

#include<iostream>
#include<cstring>
using namespace std;
const  int N =100010;
int head[N],e[N],ne[N],idx;
bool view[N];
int ans=N,n;
void insert(int a,int b)
{
    e[idx]=b,ne[idx]=head[a],head[a]=idx++;
}
int dfs(int u)
{
    view[u]=true;
    int size=0,sum=0;
    for(int i=head[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(view[j])continue;//第一次遍历
        int s =dfs(j);
        size=max(size,s);
        sum+=s;
    }
    size = max(size, n - sum - 1);
    ans = min(ans, size);
    return sum + 1;
}
int main()
{
    cin>>n;
    memset(head,-1,sizeof head);
    for(int i=0;i<n-1;++i)
    {
        int a,b;
        cin>>a>>b;
        insert(a,b),insert(b,a);
    }
    dfs(1);
    printf("%d",ans);
    return 0;
}

题解 AcWing 2360. 星球大战

Fingerscrossed
2天前

题目描述

由于并查集不支持删除操作，这里可以逆向思维一波，使用反向并查集，
如果按照正序，求打击一次，二次连通块的数目，会超时，此时可以求将k次全部打击完的连通块数目，
接着将k-1次打击的点补上求连通块数目，一直补到第0次打击的数目，然后逆序输出就可。

样例

#include<iostream>
using namespace std;
const int N =400010;
int head[N],ans[N],p[N],d[N],idx=0;//头节点，答案，父亲，打击点
bool e[N];//是否被打击
//邻接表
struct edge{int u,v,next;}ed[400010];
//并查集
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
//邻接表插入
void insert(int u,int v)
{
    ed[idx].u=u;
    ed[idx].v=v;
    ed[idx].next = head[u];
    head[u]=idx++;
}
int main()
{
    int n,m,k,tol,x,y,u;
    cin>>n>>m;
    //初始化
    for(int i=0;i<n;++i)
    {
        head[i]=-1;
        p[i]=i;
    }
    //m个点连接
    for(int i=0;i<m;++i)
    {
        cin>>x>>y;
        insert(x,y);
        insert(y,x);
    }
    cin>>k;
    tol = n-k;//打击k次后的点
    //记录打击
    for(int i =1;i<=k;++i)
    {
        cin>>x;
        d[i] =x;
        e[x]=true;
    }
    //先连通没有被打击的点
    for(int i =0;i<2*m;++i)
    {
        if(!e[ed[i].u]&&!e[ed[i].v])
        {
            int s = find(ed[i].u),t=find(ed[i].v);
            if(s!=t)
            {
                tol--;
                p[find(ed[i].u)]=find(ed[i].v);
            }
        }
    }
    //再一个个连接打击点
    ans[k+1]=tol;//打击k次的连通块

    //从打击k次算打击k-1次一直算到打击0次
    for(int j=k;j>=1;j--)
    {
        //修复点
        u=d[j];
        e[u]=false;
        tol++;
        //修复连接所有它所连接的点
        for(int i=head[u];i!=-1;i=ed[i].next)
        {
            if(!e[ed[i].v]&&find(ed[i].v)!=find(u))
            {
                tol--;
                p[find(ed[i].v)]=find(u);
            }
        }
        ans[j]=tol;
    }
    for(int i=1;i<=k+1;++i) cout<<ans[i]<<endl;
    return 0;
}

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

Fingerscrossed
2天前

                数组模拟队列，注意tt与tt区别
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int ,int>PII;
const int N =110;
int g[N][N];
int d[N][N];
PII p[N*N];
int n,m;
//g存放迷宫，d存放到每个点到端点的距离，p存放经过的点
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    d[0][0]=0;
    p[0]={0,0};
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(hh<=tt)
    {
        auto t =p[hh++];
        for(int i =0;i<4;++i)
        {
            int x =t.first+dx[i];int y=t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;
                p[++tt]={x,y};
            }

        }
    }
    return d[n-1][m-1];
}

int main()
{
    cin>>n>>m;
    for(int i =0;i<n;i++)
        for(int j =0;j<m;j++)
            scanf("%d",&g[i][j]);

    cout<<bfs();
    return 0;
}


使用queue
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int ,int>PII;
const int N =110;
int g[N][N];
int d[N][N];
PII p[N*N];
int n,m;
queue<PII>q_idx;
//g存放迷宫，d存放到每个点到端点的距离，p存放经过的点
int bfs()
{
    memset(d,-1,sizeof d);
    d[0][0]=0;
    queue<PII>q;
    q.push({0,0});
    q_idx.push({0,0});
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(q.size())
    {
        auto t = q.front();
        q_idx.push(q.front());
        q.pop();
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }

    }
    return d[n-1][m-1];
}

int main()
{
    cin>>n>>m;
    for(int i =0;i<n;i++)
        for(int j =0;j<m;j++)
            scanf("%d",&g[i][j]);

    cout<<bfs()<<endl;
    while(q_idx.size())
    {
        auto t = q_idx.front();
        cout<<"("<<t.first<<", "<<t.second<<")";
        q_idx.pop();
    }
    return 0;
}

            

活动打卡代码 AcWing 788. 逆序对的数量

Fingerscrossed
2天前

                #include<iostream>
using namespace std;
const int N  =100010;
int q[N],temp[N];
typedef long long ll;

ll merge_sort(int q[],int l ,int r)
{
    if(l>=r)return 0;
    int mid = (l+r)/2;
    ll res = merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
    int i =l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        q[i]<=q[j]?temp[k++]=q[i++]:(res+=mid-i+1,temp[k++]=q[j++]);
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r)temp[k++]=q[j++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = temp[j];
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    cout << merge_sort(q, 0, n-1) << endl;

    return 0;
}

            

活动打卡代码 AcWing 2816. 判断子序列

Fingerscrossed
2天前

check为a[i]=b[j]

#include<iostream>
using namespace std;
const int N  = 100010;
typedef long long ll;
int a[N],b[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i =0;i<n;i++)scanf("%d",&a[i]);
    for(int i =0;i<m;i++)scanf("%d",&b[i]);
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j])i++;
        j++;
    }
    if(i==n)cout<<"Yes";
    else cout<<"No";
}

活动打卡代码 AcWing 798. 差分矩阵

Fingerscrossed
2天前

注意insert

#include<iostream>
using namespace std;
const int N =1010;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int l)
{
    b[x1][y1]+=l;
    b[x2+1][y1]-=l;
    b[x1][y2+1]-=l;
    b[x2+1][y2+1]+=l;
}

int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i =1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i =1;i<=n;++i)
    {
        for(int j =1;j<=m;++j)cout<<b[i][j]<<" ";
        cout<<endl;
    }
}

活动打卡代码 AcWing 797. 差分

Fingerscrossed
2天前

假想b[N]的前缀和是a[N]

比如第一个插入的数为a,第二个插入的数为b,则
b数组中第一次b[1]=a,b[2]=-a,第二次b[1]=a,b[2]=-a+b,b[3]=-b.

#include<iostream>
using namespace std;
const int N  =100010;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)b[i]+=b[i-1];
    for(int i =1;i<=n;i++)printf("%d ",b[i]);
}

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

Fingerscrossed
4天前

                方法一：从每一行开始搜索
#include<iostream>
using namespace std;
const int N =15;
bool que[N],zug[N],fug[N];  //列，主对角，反对角
char g[N][N];
int n;
void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;++i)cout<<g[i]<<endl;
        cout<<endl;
    }
    for(int i=0;i<n;++i)
    {
        if(!que[i]&&!zug[u+i]&&!fug[n-u+i])
        {
            g[u][i] = 'Q';
            que[i] = true;
            zug[u+i]=true;
            fug[n-u+i]=true;
            dfs(u+1);
            g[u][i] = '.';
            que[i] = false;
            zug[u+i]=false;
            fug[n-u+i]=false;

        }
    }
}

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 ;
}



方法2从每一个格子搜索
#include<iostream>
using namespace std;
const int N =15;
bool row[N],col[N],dg[N*2],udg[N*2];//从每一个点开始搜索
char g[N][N];
int n;
void dfs(int x,int y,int s)
{
    if(s>n)return;
    if(y==n)y=0,x++;//超过右边格子数
    if(x==n)
    {
        if(s==n)
        {
            for(int i =0;i<n;i++)cout<<g[i]<<endl;
            cout<<endl;
        }
        return;
    }
    g[x][y]='.';
    dfs(x,y+1,s);
    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])
    {
        g[x][y]='Q';
        row[x] = col[y]=dg[x+y]=udg[x-y+n]=true;
        dfs(x,y+1,s+1);
        g[x][y]='.';
        row[x] = col[y]=dg[x+y]=udg[x-y+n]=false;
    }
}

int main()
{
    cin>>n;
    for(int i =0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';
        }
    }
    dfs(0,0,0);
    return 0 ;
}


            

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

Fingerscrossed
4天前

                bool数组判断是否前一个数被用过，记得dsf后回溯回去恢复原来的值
#include<iostream>
using namespace std;
const int N =10;
int path[N];
int n;
bool used[N];//判断是否被用过
void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)cout<<path[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i =1;i<=n;i++)
    {
        if(!used[i])
        {
            path[u]=i;
            used[i]=true;
            dfs(u+1);
            used[i]=false;
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

            

活动打卡代码 AcWing 837. 连通块中点的数量

Fingerscrossed
6天前

                s数组有点小坑
#include<iostream>
using namespace std;
const int N = 100010;
int p[N],s[N];//size[N]用来存储头节点所拥有元素的个数，N表示头节点
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i =1;i<=n;++i)
    {
        p[i]=i;
        s[i]=1;
    }
    while(m--)
    {
        string op;int a,b;
        cin>>op;
        if(op=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
            {
                s[find(b)]+=s[find(a)];
                p[find(a)]=find(b);
                /*p[find(a)]=find(b);
                  s[find(b)]+=s[find(a)];
                  错误，如果先连接的话，s里面访问find(a)找到的就是b，这样加的话就
                  相当于新的b的元素个数加原来b的元素个数，而不是原来b的元素个数加a的元素个数
                */
            }
        }
        else if(op=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<s[find(a)]<<endl;

        }

    }
    return 0;
}

            

0 评论

题目描述

样例

0 评论

数组模拟队列，注意tt与tt区别

使用queue

0 评论

0 评论

0 评论

0 评论

假想b[N]的前缀和是a[N]

0 评论

方法一：从每一行开始搜索

方法2从每一个格子搜索

0 评论

bool数组判断是否前一个数被用过，记得dsf后回溯回去恢复原来的值

0 评论

s数组有点小坑

0 评论