头像

2357




离线:8天前


最近来访(103)
用户头像
violet_garden
用户头像
LimboMaster
用户头像
wink
用户头像
test-test
用户头像
SunEup
用户头像
WangJY
用户头像
Cieu
用户头像
ants
用户头像
RyanMoriarty
用户头像
快乐的空指针
用户头像
ZQCa
用户头像
天梯蒟蒻


2357
10天前

参考文献

当存在一个可移动整数时,完成下面事情:
(1) 求出最大的可移动整数m.
(2)交换m和它的箭头所指向的与它相邻的整数·
(3)交换所有满足p>m的整数p上的箭头的方向·

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline") 
int n;
vector<int> px,mp,fx;
/*
px数组
mp位置
fx方向 -1:<-  1:->
*/
vector<string> st;
void go(){
    int pd=1;
    while(pd==1){
        pd=0;
        for(int i=n;i>=1;i--){
            int wz=mp[i];
            if(wz+fx[i]<1||wz+fx[i]>n){
                fx[i]*=-1;
            }else if(px[wz+fx[i]]<px[wz]){
                pd=1;
                mp[px[wz+fx[i]]]=wz;
                mp[px[wz]]=wz+fx[i];
                swap(px[wz+fx[i]],px[wz]);
                break;
            }else{
                fx[i]*=-1;
            }
        }
        if(pd==1){
            string qt="";
            for(int i=1;i<=n;i++){
                qt+=char(px[i]+'0');
                qt+=" ";
            }
            st.push_back(qt);
        }
    }
    if(st.size()>0){
        sort(st.begin(),st.end());
        for(int i=0;i<st.size();i++){
            cout<<st[i]<<endl;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    mp.push_back(0);
    fx.push_back(-1);
    px.push_back(0);
    for(int i=1;i<=n;i++){
        px.push_back(i);
        mp.push_back(i);
        fx.push_back(-1);
        cout<<i<<" ";
    }cout<<endl;
    if(n>1){
        sort(px.begin(),px.end());
        go();   
    }
    return 0;
}


活动打卡代码 AcWing 376. 机器任务

2357
3个月前
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline")
int N,M,K; 
int a,b;
int tu[105][105];
int pd[105],mat[105];
bool dfs(int u){
    for(int i=1;i<M;i++){
        if(pd[i]==0&&tu[u][i]==1){
            pd[i]=1;
            if(mat[i]==-1||dfs(mat[i])){
                mat[i]=u;
                return true;
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin>>N){
        if(N==0){
            break;
        }
        cin>>M>>K;
        for(int i=0;i<=100;i++){
            for(int j=0;j<=100;j++){
                tu[i][j]=0;
            }
        }
        for(int i=0;i<=100;i++){
            mat[i]=-1;
        }

        for(int i=0;i<K;i++){
            int id;
            cin>>id>>a>>b;
            if(a!=0&&b!=0){
                tu[a][b]=1;
            }
        }
        int ans=0;
        for(int i=1;i<N;i++){
            for(int i=0;i<=100;i++){
                pd[i]=0;
            }
            if(dfs(i)){
                ans++;
            }
        }       
        cout<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 372. 棋盘覆盖

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline")
int n,t;
int tu[105][105];
int pd[105][105];
int X[5]={-1,0,1,0};
int Y[5]={0,-1,0,1};
bool dfs(int x,int y){
    for(int i=0;i<4;i++){
        int jx=x+X[i],jy=y+Y[i];
        if(jx>=1&&jx<=n&&jy>=1&&jy<=n&&tu[jx][jy]!=-1){
            if(pd[jx][jy]==0){
                pd[jx][jy]=1;
                if(tu[jx][jy]==0){
                    tu[jx][jy]=i+1;
                    return 1;
                }else if(dfs(jx-X[tu[jx][jy]-1],jy-Y[tu[jx][jy]-1])){
                    tu[jx][jy]=i+1;
                    return 1;
                }
            }           
        }
    }
    return 0;
}
void cs(){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            pd[i][j]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            tu[i][j]=0;
        }
    }
    for(int i=0;i<t;i++){
        int x,y;
        cin>>x>>y;
        tu[x][y]=-1;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(tu[i][j]!=-1&&(i+j)%2==0){
                cs();
                if(dfs(i,j)){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
4 1
1 1
4 4
*/


活动打卡代码 AcWing 257. 关押罪犯

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline") 
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre;
        bcj(int n){//初始化指向自己
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
            }
        }
        int size(){//返回大小
            return pre.size();
        }
        int find(T x){//查询根节点
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){//判断是否同集
            return find(x)==find(y);
        }
        bool join(T x,T y){//添加
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            }
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
            }else{
                if(pre[fx]==pre[fy]){
                    pre[fy]++;  
                }
                pre[fx]=fy;
            }
            return true;
        }   
};
bcj<long long> bc(40005);
class md{
    public:
        long long a,b,c;
};
bool px(md a,md b){
    return a.c>b.c;
}
md s[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>s[i].a>>s[i].b>>s[i].c;
    }
    sort(s,s+m,px);
    for(int i=0;i<m;i++){
        if(!bc.query(s[i].a,s[i].b)){
            bc.join(s[i].a,s[i].b+n);
            bc.join(s[i].b,s[i].a+n);
        }else{
            cout<<s[i].c<<endl;
            return 0;
        }
    }
    cout<<"0"<<endl;
    return 0;
}



2357
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=505,M=1e4+5;
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre;
        bcj(int n){//初始化指向自己
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
            }
        }
        int size(){//返回大小
            return pre.size();
        }
        int find(T x){//查询根节点
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){//判断是否同集
            return find(x)==find(y);
        }
        bool join(T x,T y){//添加
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            } 
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
            }else{
                if(pre[fx]==pre[fy]){
                    pre[fy]++;  
                }
                pre[fx]=fy;
            }
            return true;
        }   
};
int n,m;
class md{
    public:
        int a,b;
        long long w;
        bool pd;
};
class md2{
    public:
        int id;
        long long L;
};
vector<md> bian;
vector<vector<md2>> dian(N);
long long dist1[N][N],dist2[N][N];
bcj<int> bc(N);
bool px(md a,md b){
    return a.w<b.w;
}
long long kruskal(){
    sort(bian.begin(),bian.end(),px);
    long long res=0;
    for(int i=0;i<m;i++){
        int a=bc.find(bian[i].a);
        int b=bc.find(bian[i].b);
        long long w=bian[i].w;
        if(a!=b){
            bc.join(a,b);
            bian[i].pd=1;
            res+=w;
        }
    }
    return res;
}
void build(){
    for(int i=0;i<m;i++){
        if(bian[i].pd==1){
            dian[bian[i].a].push_back({bian[i].b,bian[i].w});
            dian[bian[i].b].push_back({bian[i].a,bian[i].w});
        }
    }
}
void dfs(int x,int y,int fa,long long ms1,long long ms2){
    dist1[x][y]=ms1;
    dist2[x][y]=ms2;
    for(int i=0;i<dian[y].size();i++){
        if(dian[y][i].id!=fa){
            int t1=ms1,t2=ms2;
            if(dian[y][i].L>ms1){
                t1=dian[y][i].L;
                t2=ms1;
            }else if(dian[y][i].L<ms1&&dian[y][i].L>ms2){
                t2=dian[y][i].L;
            }
            dfs(x,dian[y][i].id,y,t1,t2);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        long long c;
        cin>>a>>b>>c;
        bian.push_back({a,b,c,0});
    }
    long long sum=kruskal();
    build();
    long long res=1e18;
    for(int i=1;i<=n;i++){
        dfs(i,i,-1,0,0);
    }
    for(int i=0;i<m;i++){
        if(bian[i].pd==0){
            long long a,b,c;
            a=bian[i].a;
            b=bian[i].b;
            c=bian[i].w;
            if(c>dist1[a][b]){
                res=min(res,sum+c-dist1[a][b]);
            }else if(c>dist2[a][b]){
                res=min(res,sum+c-dist2[a][b]);
            }
        }
    }
    cout<<res<<endl;
    return 0;
} 


活动打卡代码 AcWing 346. 走廊泼水节

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre,siz;
        bcj(int n){
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
                siz.push_back(1);
            }
        }
        long long size(int i){
            return siz[find(i)];
        }
        int find(T x){
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){
            return find(x)==find(y);
        }
        bool join(T x,T y){
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            }
            return true;
        }   
        void bin(int x,int y){
            int fx=find(x),fy=find(y);
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
                siz[fx]=siz[fy]+siz[fx];
            }else{
                pre[fx]=fy;
                siz[fy]=siz[fy]+siz[fx];
            }           
        }
};
class qs{
    public:
        int l,r,s;
};
qs mds[6005];
bool px(qs a,qs b){
    return a.s<b.s;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        bcj<int> md(n+5);
        int m=0;
        for(int i=1;i<n;i++){
            int x,y,z;
            cin>>x>>y>>z;
            mds[m++]={x,y,z};
        }
        long long ams=0;
        sort(mds,mds+m,px);
        for(int i=0;i<m;i++){
            int x=mds[i].l,y=mds[i].r,s=mds[i].s;
            if(md.join(x,y)){
                ams+=(md.size(x)*md.size(y)-1)*(s+1);
                md.bin(x,y);
            }
        }
        cout<<ams<<endl;        
    } 
    return 0;
}


活动打卡代码 AcWing 1145. 北极通讯网络

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre;
        bcj(int n){
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
            }
        }
        int size(){
            return pre.size();
        }
        int find(T x){
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){
            return find(x)==find(y);
        }
        bool join(T x,T y){
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            }
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
            }else{
                if(pre[fx]==pre[fy]){
                    pre[fy]++;  
                }
                pre[fx]=fy;
            }
            return true;
        }   
};
class qs{
    public:
        int l,r;
        double s;
};
qs mds[505*505];
qs dian[505];
bool px(qs a,qs b){
    return a.s<b.s;
}
double quL(int x1,int y1,int x2,int y2){
    double s1=x1-x2,s2=y1-y2;
    return sqrt(s1*s1+s2*s2);
}
int main(){
    int n,k;
    cin>>n>>k;
    bcj<int> md(n+5);
    int m=0;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        dian[i]={x,y,0.0};
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                mds[m++]={i,j,quL(dian[i].l,dian[i].r,dian[j].l,dian[j].r)};
            }
        }
    }
    vector<int> ans;
    sort(mds,mds+m,px);
    for(int i=0;i<m;i++){
        int x=mds[i].l,y=mds[i].r,s=mds[i].s;
        if(md.join(x-1,y-1)){
            ans.push_back(i);
        }
    }
    double ms=0;
    for(int i=ans.size()-1;i>=0;i--){
        if(k>1){
            k--;
        }else{
            ms=max(ms,mds[ans[i]].s);
        }
    }
    printf("%.2lf\n",ms);
    return 0;
}


活动打卡代码 AcWing 1146. 新的开始

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre;
        bcj(int n){
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
            }
        }
        int size(){
            return pre.size();
        }
        int find(T x){
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){
            return find(x)==find(y);
        }
        bool join(T x,T y){
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            }
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
            }else{
                if(pre[fx]==pre[fy]){
                    pre[fy]++;  
                }
                pre[fx]=fy;
            }
            return true;
        }   
};
class qs{
    public:
        int l,r,s;
};
qs mds[305*305];
bool px(qs a,qs b){
    return a.s<b.s;
}
int main(){
    int n;
    cin>>n;
    bcj<int> md(n+5);
    int m=0;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        mds[m++]={n+1,i,v};
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int p;
            cin>>p;
            if(i!=j){
                mds[m++]={i,j,p};
            }
        }
    }
    long long ams=0;
    sort(mds,mds+m,px);
    for(int i=0;i<m;i++){
        int x=mds[i].l,y=mds[i].r,s=mds[i].s;
        if(md.join(x-1,y-1)){
            ams+=s;
        }
    }
    cout<<ams<<endl;
    return 0;
}


活动打卡代码 AcWing 1144. 连接格点

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline")
const int N=1005;
vector<int> pre(N*N);
int find(int x){
    if(pre[x]==x) return x;
    return pre[x]=find(pre[x]);
}
bool query(int x,int y){
    return find(x)==find(y);
}
bool join(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy){
        return false;
    }
    if(pre[fx]>pre[fy]){
        pre[fy]=fx;
    }else{
        if(pre[fx]==pre[fy]){
            pre[fy]++;  
        }
        pre[fx]=fy;
    }
    return true;
}   
int n,m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n*m;i++){
        pre[i]=i;
    }
    int x1,y1,x2,y2,ans=0;
    while(cin>>x1>>y1>>x2>>y2){
        int u=(x1-1)*m+y1,v=(x2-1)*m+y2;
        if(!query(u,v)){
            join(u,v);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<n;j++){
            int u=(j-1)*m+i,v=j*m+i;
            if(!query(u,v)){
                join(u,v);
                 ans++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<m;j++){
            int u=(i-1)*m+j,v=(i-1)*m+j+1;
            if(!query(u,v)){
                join(u,v);
                ans+=2;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1143. 联络员

2357
4个月前
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3,"Ofast","inline")
const int N=2005;
template<class T>
class bcj{
    public:
        int N;
        vector<T> pre;
        bcj(int n){
            N=n;
            for(int i=0;i<N;i++){
                pre.push_back(i);
            }
        }
        int size(){
            return pre.size();
        }
        int find(T x){
            if(pre[x]==x) return x;
            return pre[x]=find(pre[x]);
        }
        bool query(T x,T y){
            return find(x)==find(y);
        }
        bool join(T x,T y){
            int fx=find(x),fy=find(y);
            if(fx==fy){
                return false;
            }
            if(pre[fx]>pre[fy]){
                pre[fy]=fx;
            }else{
                if(pre[fx]==pre[fy]){
                    pre[fy]++;  
                }
                pre[fx]=fy;
            }
            return true;
        }   
};
class md{
    public:
        int x,y,l;
        friend bool operator < (md a,md b){  
            return a.l>b.l;
        }
};
vector<int> dis;
vector<md> tu;
bcj<int> bin(N);
void prim(){
    priority_queue<md> qu;
    for(int i=0;i<tu.size();i++){
        qu.push({tu[i].x,tu[i].y,tu[i].l});
    }
    while(!qu.empty()){
        md s=qu.top();
        qu.pop();
        if(!bin.query(s.x,s.y)){
            bin.join(s.x,s.y);
            dis.push_back(s.l);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int p,x,y,l;
        cin>>p>>x>>y>>l;
        if(p==1){
            bin.join(x,y);
            dis.push_back(l);
        }else{
            tu.push_back({x,y,l});
        }
    }
    prim();
    int ans=0;
    for(int i=0;i<dis.size();i++){
        ans+=dis[i];
    }
    cout<<ans<<endl;
    return 0;
}