2.27模拟赛

pdf版题面

水题赛无题解

sol：可以用权值并查集搞，但感觉还是建图跑bfs比较容易

定义S[i]表示前缀和

读入a，b，c；就是S[a-1] + c=S[b]，那就从a-1向b连一条c，b向a-1连一条-c

但这样有可能这张图并不联通，于是每次bfs时给节点染色，颜色不同显然to hard

询问随便处理下就可以了

/*
    S[3]-S[0]=10
    S[3]-S[2]=5
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
inline ll read()
{
    ll S=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
    }
    return (f)?(-S):(S);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005,M=200005;
int n,m,Q,Cnt=0;
namespace Dijkstra
{
    int tot=0,Next[M],to[M],val[M],head[N];
    int Cor[N];
    inline void add(int x,int y,int z)
    {
        Next[++tot]=head[x];
        to[tot]=y;
        val[tot]=z;
        head[x]=tot;
        return;
    }
    struct Record
    {
        int Weiz,Val;
    };
    inline bool operator<(Record p,Record q)
    {
        return p.Val>q.Val;
    }
    priority_queue<Record>Queue;
    bool Arr[N];
    int Dis[N];
    inline void Run(int S,int Co)
    {
        Cor[S]=Co;
        Queue.push((Record){S,Dis[S]=0});
        int i;
        while(!Queue.empty())
        {
            Record tmp=Queue.top();
            Cor[tmp.Weiz]=Co;
            Queue.pop();
            if(Arr[tmp.Weiz]) continue;
            Arr[tmp.Weiz]=1;
            for(i=head[tmp.Weiz];i;i=Next[i])
            {
                if(Dis[to[i]]>tmp.Val+val[i])
                {
                    Dis[to[i]]=tmp.Val+val[i];
                    if(!Arr[to[i]]) Queue.push((Record){to[i],Dis[to[i]]});
                }
            }
        }
    }
    inline void Solve(int x,int y)
    {
        y++;
        if(Cor[x]!=Cor[y])
        {
            puts("Too Hard");
        }
        else
        {
            Wl(Dis[y]-Dis[x]);    
        }
    }
    inline void Init()
    {
        memset(head,0,sizeof head);
        memset(Arr,0,sizeof Arr);
        memset(Dis,63,sizeof Dis);
        memset(Cor,0,sizeof Cor);
        return;
    }
}
signed main()
{
    freopen("sing.in","r",stdin);
    freopen("sing.out","w",stdout);
    R(n); R(m);
    int i;
    Dijkstra::Init();
    for(i=1;i<=m;i++)
    {
        int x=read(),y=read()+1,z=read();
        Dijkstra::add(x,y,z);
        Dijkstra::add(y,x,-z);
    }
    for(i=1;i<=n;i++) if(!Dijkstra::Arr[i])
    {
        Dijkstra::Run(i,++Cnt);
    }
    R(Q);
    for(i=1;i<=Q;i++)
    {
        int x=read(),y=read();
        Dijkstra::Solve(x,y);
    }
    return 0;
}
/*
input
4 2
1 3 10
3 3 5
2
1 2
1 4
output
5
Too Hard
*/
View Code

sol：容易发现这个n非常大，肯定不能直接上最短路

于是发现跑最短路时，真正有用的是那些中间有墙倒掉的点，对于这2*m个点

首先在有墙倒的地方建一条权值1的双向边

在对2*m个点排序，p[i]向p[i+1]连一条权值为(p[i+1]-p[i])的边

要离散。。。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
inline ll read()
{
    ll S=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
    }
    return (f)?(-S):(S);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=500005,M=1000005;
int n,m;
int X[N],Y[N];
int P[N<<1];
int Pos[N<<1];
map<int,int>Map;
namespace Dijkstra
{
    int tot=0,Next[M],to[M],val[M],head[N];
    inline void add(int x,int y,int z)
    {
        Next[++tot]=head[x];
        to[tot]=y;
        val[tot]=z;
        head[x]=tot;
        return;
    }
    struct Record
    {
        int Weiz,Val;
    };
    inline bool operator<(Record p,Record q)
    {
        return p.Val>q.Val;
    }
    priority_queue<Record>Queue;
    bool Arr[N];
    int Dis[N];
    inline void Run(int S)
    {
        Queue.push((Record){S,Dis[S]=0});
        int i;
        while(!Queue.empty())
        {
            Record tmp=Queue.top();
            Queue.pop();
            if(Arr[tmp.Weiz]) continue;
            Arr[tmp.Weiz]=1;
            for(i=head[tmp.Weiz];i;i=Next[i])
            {
                if(Dis[to[i]]>tmp.Val+val[i])
                {
                    Dis[to[i]]=tmp.Val+val[i];
                    if(!Arr[to[i]]) Queue.push((Record){to[i],Dis[to[i]]});
                }
            }
        }
    }
    inline void Init()
    {
        memset(head,0,sizeof head);
        memset(Arr,0,sizeof Arr);
        memset(Dis,63,sizeof Dis);
        return;
    }
}
#define Dj Dijkstra
signed main()
{
    freopen("lh.in","r",stdin);
    freopen("lh.out","w",stdout);
    R(n); R(m);
    int i;
    Dj::Init();
    for(i=1;i<=m;i++)
    {
        X[i]=read();
        Y[i]=read();
        if(!Map[X[i]])
        {
            P[Map[X[i]]=++*P]=X[i];
        }
        if(!Map[Y[i]])
        {
            P[Map[Y[i]]=++*P]=Y[i];
        }
        Dj::add(Map[X[i]],Map[Y[i]],1);
        Dj::add(Map[Y[i]],Map[X[i]],1);
    }
    if(!Map[1])
    {
        P[Map[1]=++*P]=1;
    }
    if(!Map[n])
    {
        P[Map[n]=++*P]=n;
    }
    sort(P+1,P+*P+1);
    for(i=1;i<*P;i++)
    {
        Dj::add(Map[P[i]],Map[P[i+1]],P[i+1]-P[i]);
        Dj::add(Map[P[i+1]],Map[P[i]],P[i+1]-P[i]);
    }
    Dj::Run(Map[1]);
    Wl(Dj::Dis[Map[n]]);
    return 0;
}
/*
input
31
9
4 15
10 25
13 30
1 6
2 9
6 19
9 24
10 27
1 4
output
6
Too Hard
*/
View Code

sol：看上去很厉害其实只是MST的板子罢了，一堆描述只是在故弄玄虚，就是说没有环。

Prim随便水

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll S=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
    }
    return (f)?(-S):(S);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=5005;
int n;
struct Point
{
    int x,y;
}P[N];
double DD[N];
int Father[N];
bool Vis[N];
inline double Calc(int i,int j)
{
    double ix=P[i].x,iy=P[i].y,jx=P[j].x,jy=P[j].y;
    return sqrt((ix-jx)*(ix-jx)+(iy-jy)*(iy-jy));
}
int main()
{
    freopen("torture.in","r",stdin);
    freopen("torture.out","w",stdout);
    int i,j;
    R(n);
    for(i=1;i<=n;i++)
    {
        Father[i]=i;
        R(P[i].x);
        R(P[i].y);
    }
    int step;
    double ans=0;
    for(i=2;i<=n;i++) DD[i]=1e15;
    DD[1]=0;
    for(step=1;step<n;step++)
    {
        int u=-1;
        for(i=1;i<=n;i++) if((!Vis[i])&&(u==-1||DD[i]<DD[u])) u=i;
        Vis[u]=1;
        for(i=1;i<=n;i++) if((!Vis[i])&&(DD[i]>Calc(u,i)))
        {
            DD[i]=Calc(u,i);
        }
    }
    for(i=1;i<=n;i++) ans+=DD[i];
    printf("%.2lf
",ans);
    return 0;
}
/*
input
4
0 0
1 2
-1 2
0 4
output
6.47
*/
View Code

updata：首先对于题面有一处修正，两个点之间的距离是min（|Xa-Xb|,|Ya-Yb|,|Za-Zb|）,题面中少了个min，而且也不是曼哈顿距离

sol：对三维分别排序，得到3*（n-1）条边，Kruskal直接上

Xjb证明：只有一维时，显然排好序后第i个向i+1连边最优，

当有三维时，Kruskal保证当前边权是没选过的中最小的，相当于已经在3维中去过min了，于是可以直接做了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll S=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
    }
    return (f)?(-S):(S);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005;
int n;
int Father[N];
struct Point
{
    int Weiz,Id;
}X[N],Y[N],Z[N];
inline bool Point_cmp(Point a,Point b)
{
    return a.Weiz<b.Weiz;
}
int cnt=0;
struct Edge
{
    int U,V,Bianquan;
}E[N*3];
inline bool Edge_cmp(Edge a,Edge b)
{
    return a.Bianquan<b.Bianquan;
}
inline int Get_Father(int x)
{
    return (Father[x]==x)?(x):(Father[x]=Get_Father(Father[x]));
}
int main()
{
    freopen("time.in","r",stdin);
    freopen("time.out","w",stdout);
    int i;
    R(n);
    for(i=1;i<=n;i++)
    {
        X[i]=(Point){read(),i};
        Y[i]=(Point){read(),i};
        Z[i]=(Point){read(),i};
    }
    sort(X+1,X+n+1,Point_cmp);
    for(i=1;i<n;i++)
    {
        E[++cnt]=(Edge){X[i].Id,X[i+1].Id,X[i+1].Weiz-X[i].Weiz};
    }
    sort(Y+1,Y+n+1,Point_cmp);
    for(i=1;i<n;i++)
    {
        E[++cnt]=(Edge){Y[i].Id,Y[i+1].Id,Y[i+1].Weiz-Y[i].Weiz};
    }
    sort(Z+1,Z+n+1,Point_cmp);
    for(i=1;i<n;i++)
    {
        E[++cnt]=(Edge){Z[i].Id,Z[i+1].Id,Z[i+1].Weiz-Z[i].Weiz};
    }
    sort(E+1,E+cnt+1,Edge_cmp);
    for(i=1;i<=n;i++)
    {
        Father[i]=i;
    }
    ll ans=0;
    int Bians=0;
    for(i=1;i<=cnt;i++)
    {
        int u=E[i].U,v=E[i].V;
        int uu=Get_Father(u),vv=Get_Father(v);
        if(uu==vv) continue;
        ans+=1ll*E[i].Bianquan;
        Father[uu]=vv;
        if(++Bians==n-1) break;
    }
    Wl(ans);
    return 0;
}
/*
input
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
output
4
*/
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/gaojunonly1/p/10453070.html