头像

李乾


访客:12401

离线:4小时前


新鲜事 原文

李乾
9天前
居然不报错??还AC了!
图片


新鲜事 原文

李乾
9天前
划水中...
图片


活动打卡代码 AcWing 238. 银河英雄传说

李乾
19天前

AcWing 238. 银河英雄传说

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
const int N=30010 ;
int p[N],sizes[N],dist[N] ;
int find(int x)
{
    if(p[x]!=x) 
    {
        int root=find(p[x]) ;
        dist[x]+=dist[p[x]] ;
        p[x]=root ;
    }
    return p[x] ;
}
int t ;
int main()
{
    scanf("%d",&t) ;
    for(int i=1;i<N;i++) p[i]=i,sizes[i]=1 ;
    while(t--)
    {
        int a,b ;
        char op ;
        getchar() ;
        op=getchar() ;
        getchar() ;
        scanf("%d%d",&a,&b) ;
        int pa=find(a),pb=find(b) ;
        if(op=='M')
        {
            if(pa!=pb)
            {
                dist[pa]=sizes[pb] ;
                sizes[pb]+=sizes[pa] ;
                p[pa]=pb ;
            }
        }
        else
        {
            if(pa!=pb) puts("-1") ;
            else printf("%d\n",max(0,abs(dist[a]-dist[b])-1)) ;
        }
    }
    return 0 ;
}



李乾
19天前
/*
用法说明
1.resize函数:传入并查集的长度,程序会为您分配足够的数组空间
2.father函数:传入并查集的一个节点,返回它的根节点
3.query函数:传入2个节点,判断两个节点是否在同一连通块中
4.merge函数:传入2个节点,将这两个节点所在的连通块合并
5.get函数,传入1个字符串与1个vector,分别表示想要查询的类型与装载查询结果的容器。
查询分3种
(1) string="fa",vector表示每个节点的根节点节点的集合
(2) string="size",vector表示每个节点所在连通块的大小
(3) string="dist",vector表示每个节点与根节点的距离
*/


#include <iostream>
#include <algorithm>
using namespace std ;
class DSU
{
    public:
        void resize(int n)
        {
            dist.resize(n) ;
            len=n ;
            for(int i=1;i<=n;i++) 
            {
                fa.push_back(i) ;
                sizes.push_back(1) ;
            }
        }
        int father(int x)
        {
            if(fa[x]!=x) 
            {
                int root=father(fa[x]) ;
                dist[x]+=dist[fa[x]] ;
                fa[x]=root ;
            }
            return fa[x] ;
        }
        bool query(int a,int b)
        {
            return father(a)==father(b) ; 
        }
        void merge(int a,int b)
        {
            if(!query(a,b))
            {
                a=fa[a],b=fa[b] ;
                dist[a]=sizes[b] ;
                sizes[b]+=sizes[a] ;
                fa[a]=b ;
            }
        }
        void get(string str,vector<int> &vec)
        {
            if(str=="fa")
                for(int i=1;i<=len;i++) vec.push_back(father(i)) ;
            else if(str=="size") vec=sizes ;
            else if(str=="dist") vec=dist ;
        }
    private:
        vector<int> fa ;
        vector<int> sizes ;
        vector<int> dist ;
        int len ;
} ;


活动打卡代码 AcWing 237. 程序自动分析

李乾
19天前

AcWing 237. 程序自动分析

#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#define x first
#define y second
using namespace std ;
const int N=2000010 ;
typedef pair<int,int> PII ;
int p[N] ;
map<int,int> h ;
PII query[N][2] ;
int q_cnt,cnt,m ;
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]) ;
    return p[x] ;
}
int add(int a)
{
    if(!h[a]) h[a]=++cnt ;
    return h[a] ;
}
int main()
{
    int t ;
    scanf("%d",&t) ;
    while(t--)
    {
        scanf("%d",&m) ;
        q_cnt=cnt=0 ;
        h.clear() ;
        for(int i=1;i<=m;i++)
        {
            int a,b,c ;
            scanf("%d%d%d",&a,&b,&c) ;
            query[i][c]={add(a),add(b)} ;
            query[i][!c]={0,0} ;
        }
        for(int i=1;i<=cnt;i++) p[i]=i ;
        for(int i=1;i<=m;i++)
            if(query[i][1].x)
            {
                int pa=find(query[i][1].x) ;
                int pb=find(query[i][1].y) ;
                p[pa]=pb ;
            }
        bool flag=true ;
        for(int i=1;i<=m;i++)
            if(query[i][0].y)
            {
                int pa=find(query[i][0].x) ;
                int pb=find(query[i][0].y) ;
                if(pa==pb)
                {
                    flag=false ;
                    break ;
                }
            }
        if(flag) puts("YES") ;
        else puts("NO") ;
    }
    return 0 ;
}


新鲜事 原文

李乾
19天前
...
图片


活动打卡代码 AcWing 1252. 搭配购买

李乾
19天前

AcWing 1252. 搭配购买

#include <iostream>
#include <algorithm>
using namespace std ;
const int N=10010 ;
int w[N],v[N],f[N] ;
int n,m,maxv ;
int p[N] ;
int find(int x)
{
    if(p[x]==x) return x ;
    return p[x]=find(p[x]) ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&maxv) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]) ;
        p[i]=i ;
    }
    while(m--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        a=find(a),b=find(b) ;
        if(a!=b) p[a]=b,w[b]+=w[a],v[b]+=v[a] ;
    }
    for(int i=1;i<=n;i++)
        if(p[i]==i)
            for(int j=maxv;j>=v[i];j--)
                f[j]=max(f[j],f[j-v[i]]+w[i]) ;
    printf("%d",f[maxv]) ;
    return 0 ;
}


活动打卡代码 AcWing 1250. 格子游戏

李乾
20天前

AcWing 1250. 格子游戏

#include <iostream>
#include <algorithm>
#define get(x,y) x*n+y
using namespace std ;
const int N=210*210 ;
int n,m ;
int p[N] ;
int find(int x)
{
    if(p[x]==x) return x ;
    return p[x]=find(p[x]) ;
}
int main()
{
    scanf("%d%d",&n,&m) ;
    int res=0 ;
    for(int i=1;i<=n*n;i++) p[i]=i ;
    for(int i=1;i<=m&&!res;i++)
    {
        int x,y ;
        char ch ;
        scanf("%d%d",&x,&y) ;
        getchar() ;
        ch=getchar() ;
        getchar() ;
        x--,y-- ;
        int a=get(x,y) ;
        int b= ch=='D'? get(x,y+1):get(x+1,y) ;
        int pa=find(a),pb=find(b) ;
        if(pa==pb) res=i ;
        p[pa]=pb ;
    }
    if(res) printf("%d",res) ;
    else puts("draw") ;
    return 0 ;
}


新鲜事 原文

李乾
20天前
有质量的问题回答的人数反而少



李乾
20天前

如题