头像

只要是你呀


访客:5832

离线:6小时前


活动打卡代码 AcWing 90. 64位整数乘法

#include<iostream>

using namespace std;

typedef long long int ll;

ll a,b,p;

int main()
{
    cin>>a>>b>>p;

    ll res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b=b>>1;
    }

   cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 89. a^b

#include<iostream>

using namespace std;

int a,b,p;

int main()
{
    cin>>a>>b>>p;

    int res=1%p;
    while(b)
    {
        if(b&1) res=res*1ll*a%p;
        a=a*1ll*a%p;
        b=b>>1;
    }

    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 845. 八数码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    string end = "12345678x";
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];

        int distance = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    string state;
    for (int i = 0; i < 9; i ++ )
    {
        char s;
        cin >> s;
        state += s;
    }

    cout << bfs(state) << endl;

    return 0;
} 



#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=100010;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=true;
            if(match[j]==0||find(match[j]))
            {
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n1>>n2>>m;

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    int res=0;
    for(int i=1;i<=n1;i++)
    {
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }

    printf("%d\n",res);

    return 0;
}



#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010,M=200010;

int n,m;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool dfs(int u,int c)
{
    color[u]=c;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c)) return false;
        }
        else if(color[j]==c) return false;
    }
    return true;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }

    if(flag) puts("Yes");
    else puts("No");

    return 0;
}




#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010,M=200010,INF=0x3f3f3f3f;

int n,m;
int p[N];

struct Edge
{
    int a,b,w;
    bool operator< (const Edge &W)const
    {
        return w<W.w;
    }
}edges[M];

int find(int u)
{
    if(p[u]!=u) p[u]=find(p[u]);
    return p[u];
}

int Kruskal()
{
    sort(edges,edges+m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            cnt++;
            res+=w;
        }
    }
    if(cnt<n-1) return INF;
    else return res;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    int t=Kruskal();

    if(t==INF) puts("impossible");
    else printf("%d\n",t);

    return 0;
}



#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(g[a][b],w);
    }

    int t=prim();

    if(t==INF) puts("impossible");
    else printf("%d\n",t);

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=210,INF=1e9;

int n,m,Q;
int g[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}

int main()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    floyd();
    for(int i=0;i<Q;i++)
    {
        int x,y;
        cin>>x>>y;
        int t=g[x][y];
        if(t>INF/2) puts("impossible");
        else printf("%d\n",t);
    }
    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=2010,M=10010;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool spfa()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int spfa()
{
    queue<int> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }   
        }
    }
    return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else cout<<t<<endl;

    return 0; 
}