天梯赛练习题L2（001-005）

L2-001 紧急救援

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=2002,M=520;
LL n,m,s,d,idx=0;
LL g[M][M],dist[N],st[N];
LL a[N],maxn[N],path[N],num[N],ans[N];
//a[i]表示第i个点所拥有的救援队的数量，maxn[i]表示不断更新的最短路下到达i这个点的最多的救援队的数量
//path[i]标记i的上一个点
//num[i]记录的是从s到i这个点的道路数量
//ans[i]表示经过最短的具体的路径
void dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=0;j<n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }
        st[t]=true;
        for(int j=0;j<n;j++)
        {
            if(dist[j]==dist[t]+g[t][j])//这条路和我之前走过的一样是最短的路欸
            {
                num[j]+=num[t];//道路数量更新:道路数量在原基础上直接增加
                if(maxn[j]<maxn[t]+a[j])//对比救援队数量
                {
                    maxn[j]=maxn[t]+a[j];
                    path[j]=t;
                }
            }
            else if(dist[j]>dist[t]+g[t][j])//这条路比我之前走过的更短欸
            {
                num[j]=num[t];//道路数量更新:道路数量更新为更短路径的道路数
                maxn[j]=maxn[t]+a[j];//救援队数量更新
                path[j]=t;
                dist[j]=dist[t]+g[t][j];//最短路更新:dist[j]=min(dist[j],dist[t]+g[t][j]);
            }
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m>>s>>d;//n个城市编号[0,n-1],m条道路，s出发地，d目的地
        memset(g,0x3f,sizeof g);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];//城市救援队的数量
            maxn[i]=a[i];
        }
        for(int i=1;i<=m;i++)
        {
            LL x,y,z;
            cin>>x>>y>>z;
            g[x][y]=g[y][x]=z;//邻接表
        }
        num[s]=1;//从出发点到自己就只有一条路可以走
        dij();

        //倒序存储通过的地点
        LL last=d;
        while(last!=s)
        {
            ans[idx++]=last;
            last=path[last];
        }
        ans[idx++]=last;//第一个点也要存储进去

        cout<<num[d]<<" "<<maxn[d]<<endl;
        for(int i=idx-1;i>=0;i--)
        {
            if(i==0) cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }
    return 0;
}

L2-002 链表去重

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL e[N],ne[N];//当前值，下一个地址
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL head,n;
        cin>>head>>n;
        for(int i=1;i<=n;i++)
        {
            LL address;
            cin>>address;
            cin>>e[address]>>ne[address];//当前地址的存储值，当前地址的下一个地址
        }
        vector<LL> v;
        for(int i=head;i!=-1;i=ne[i])
        {
            v.push_back(i);
        }
        //for(int i=0;i<a.size();i++)
        //    cout<<v[i]<<" ";
        //cout<<endl;
        vector<LL> a,b;
        map<LL,LL> mp;
        for(int i=0;i<v.size();i++)
        {
            LL flag=abs(e[v[i]]);
            mp[flag]++;
            if(mp[flag]>1) b.push_back(v[i]);
            else a.push_back(v[i]);
        }
        for(int i=0;i<a.size();i++)
        {
            printf("%05d %d ",a[i],e[a[i]]);//当前地址，当前地址值
            if(i==a.size()-1) printf("-1\n");
            else printf("%05d\n",a[i+1]);
        }
        for(int i=0;i<b.size();i++)
        {
            printf("%05d %d ",b[i],e[b[i]]);
            if(i==b.size()-1) printf("-1\n");
            else printf("%05d\n",b[i+1]);
        }
    }
    return 0;
}

L2-003 月饼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
struct node
{
    double rest;
    double sumprice;
    double danprice;
}a[N];
bool cmp(node l,node r)
{
    if(l.danprice!=r.danprice) return l.danprice>r.danprice;
    else return l.rest>r.rest;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].rest;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].sumprice;
            a[i].danprice=a[i].sumprice/a[i].rest;
        }
        sort(a+1,a+1+n,cmp);
       // for(int i=1;i<=n;i++)
        //{
       //     cout<<a[i].rest<<" "<<a[i].sumprice<<" "<<a[i].danprice<<endl;
       // }
        double sum=0;
        for(int i=1;i<=n;i++)
        {
            if(m>=a[i].rest)
            {
                sum+=a[i].sumprice;
                m-=a[i].rest;
            }
            else if(m<a[i].rest)
            {
                sum+=a[i].danprice*m;
                m=0;
            }
            //cout<<sum<<endl;
            if(m==0) break;
        }
        printf("%.2lf\n",sum);
    }
    return 0;
}

L2-004 这是二叉搜索树吗？

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL n,a[N],ans[N];
bool ismr=false;
void dfs(LL l,LL r)
{
    if(l>r) return ;
    LL i=l+1,j=r;//前序遍历的第一个节点就是根节点，所以直接跳过它往右一个
    if(ismr==false)//非镜像：左边小右边大
    {
        while(i<=r&&a[i]<a[l]) i++;
        while(j>l&&a[j]>=a[l]) j--;
    }
    else//镜像：左边大右边小
    {
        while(i<=r&&a[i]>=a[l]) i++;
        while(j>l&&a[j]<a[l]) j--;
    }
    //cout<<i<<" "<<j<<endl;
    if(i-j!=1) return ;
    dfs(l+1,j);
    dfs(i,r);
    ans[++ans[0]]=a[l];
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        dfs(1,n);
        //镜像
        if(ans[0]!=n)
        {
            ismr=true;
            ans[0]=0;
            dfs(1,n);
        }
        if(ans[0]==n)
        {
            cout<<"YES"<<endl<<ans[1];
            for(int i=2;i<=ans[0];i++)
            {
                cout<<" "<<ans[i];
            }
        }
        else cout<<"NO";
    }
    return 0;
}

L2-005 集合相似度

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
set<LL> st[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            LL x;
            cin>>x;
            while(x--)
            {
                LL num;
                cin>>num;
                st[i].insert(num);
            }
        }
        LL m;
        cin>>m;
        while(m--)
        {
            LL a,b;
            cin>>a>>b;
            LL sum=st[a].size()+st[b].size();
            LL ans=0;
            for(auto i:st[a]) //cout<<i<<" "; cout<<endl;
            {
                if(st[b].count(i)!=0) ans++;
            }
            sum-=ans;
            //for(auto j:st[b]) cout<<j<<" "; cout<<endl;
            printf("%.2lf%\n",ans*1.0/sum*100);
        }
    }
    return 0;
}