首页 > 其他分享 >天梯赛练习题L2（036-040）

天梯赛练习题L2（036-040）

时间：2023-01-25 10:47:04浏览次数：39  
标签：练习题 typedef const int LL cin long L2 036

L2-036 网红点打卡攻略

题目不难，但是需要仔细解读题目所给条件是什么意思

  1. 我们需要在所给的每个打卡点打卡只一次，说明每个网红店都只能经过一次

  2. 从家出发，顺着道路所给的网红打卡点一直走，说明一直就看这两者之间的道路值就行了，没有就是走不通的，走完最后一个打卡点直接回家

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=220;
#define endl '\n'
LL n,m,dist[M][M],a[M];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        LL minn=1e9,idx=-1,cnt=0;
        memset(dist,0x3f3f3f3f,sizeof dist);
        for(int i=1;i<=m;i++)
        {
            LL x,y,z;
            cin>>x>>y>>z;
            dist[x][y]=dist[y][x]=z;
        }
        //这里没有用floyed，因为纯纯是个模拟题
        LL k;
        cin>>k;
        map<LL,LL> mp;
        for(int i=1;i<=k;i++)
        {
            memset(a,0,sizeof a);
            mp.clear();
            bool flag=true;
            LL sum=0;
            LL t;
            cin>>t;
            for(int j=1;j<=t;j++)
            {
                cin>>a[j];
                mp[a[j]]++;
            }
            for(int j=1;j<=n;j++)//每个打卡点只能打卡一次
            {
                if(mp[j]!=1)//不可以多走，也不可以没走
                {
                    flag=false;
                    break;
                }
            }
            a[0]=a[t+1]=0;
            for(int j=1;j<=t+1;j++)//从家里出发，回到家里
            {
                if(dist[a[j-1]][a[j]]>=1e9)//不存在路径
                {
                    flag=false;
                    break;
                }
                else sum+=dist[a[j-1]][a[j]];
            }
            if(flag==false||sum>1e9) continue;
            else
            {
                cnt++;
                if(sum<minn) minn=sum,idx=i;
            }
        }
        cout<<cnt<<endl<<idx<<" "<<minn;
    }
    return 0;
}

L2-037 包装机

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=4002;
#define endl '\n'
LL n,m,k;
deque<char> dq[1010];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                char c;
                cin>>c;
                dq[i].push_back(c);
            }
        }
        stack<char> st;
        LL x;
        while(cin>>x)
        {
            if(x==-1) break;
            else if(x!=0)
            {
                if(dq[x].size()==0) continue; //注意不能少了这一句，否则wa5
                if(st.size()>=k)
                {
                    char tt=st.top();
                    cout<<tt;
                    st.pop();
                }
                if(dq[x].size()>0)
                {
                    st.push(dq[x].front());
                    dq[x].pop_front();
                }
            }
            else
            {
                if(st.size()>0)
                {
                    char tt=st.top();
                    cout<<tt;
                    st.pop();
                }
            }
        }
    }
    return 0;
}

L2-038 病毒溯源

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=4002;
#define endl '\n'
LL n,last[N],depth[N],maxn=0;
vector<LL> v[N];
void dfs(LL idx,LL fa,LL dep)
{
    depth[idx]=dep;
    maxn=max(maxn,depth[idx]);
    if(v[idx].size()==0) return ;
    for(int i=0;i<v[idx].size();i++)
    {
        if(v[idx][i]==fa) continue;
        dfs(v[idx][i],idx,dep+1);
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        memset(last,-1,sizeof last);
        cin>>n;
        for(int i=0;i<n;i++)
        {
            LL op;
            cin>>op;
            for(int j=1;j<=op;j++)
            {
                LL x;
                cin>>x;
                v[i].push_back(x);
                last[x]=i;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(last[i]==-1)
            {
                dfs(i,-1,1);
                break;
            }
        }
        //for(int i=0;i<n;i++) cout<<depth[i]<<" "; cout<<endl;
        vector<LL> ans,bf;
        for(int i=0;i<n;i++)
        {
            if(depth[i]==maxn)
            {
                bf.push_back(i);
                LL f=i;
                while(last[f]!=-1)
                {
                    bf.push_back(last[f]);
                    f=last[f];
                }
                //for(int j=0;j<bf.size();j++) cout<<bf[j]<<" "; cout<<endl;
                if(ans.size()==0)
                {
                    for(int k=0;k<bf.size();k++)
                        ans.push_back(bf[k]);
                }
                else
                {
                    bool flag=false;
                    for(int k=bf.size()-1;k>=0;k--)
                    {
                        if(bf[k]<ans[k])
                        {
                            flag=true;
                            break;
                        }
                        else if(bf[k]>ans[k]) break;
                    }
                    if(flag==true)
                    {
                        //for(int t=0;t<bf.size();t++) cout<<bf[t]<<" "; cout<<endl;
                        //for(int i=0;i<ans.size();i++) cout<<ans[i]<<" "; cout<<endl;
                        ans.clear();
                        for(int t=0;t<bf.size();t++)
                            ans.push_back(bf[t]);
                    }
                }
                bf.clear();
            }
        }
        cout<<ans.size()<<endl;
        reverse(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)
        {
            cout<<ans[i];
            if(i!=ans.size()-1) cout<<" ";
        }
    }
    return 0;
}

L2-039 清点代码库

这个用vector进行比较的方式比较nice

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=10100,M=4002;
#define endl '\n'
LL n,m;
vector<LL> v[N];
map<vector<LL>,LL> mp;
set<vector<LL>> st;
struct node
{
    LL id,num;
    vector<LL> bf;
}a[N];
bool cmp(node l,node r)
{
    if(l.num==r.num) return l.bf<r.bf;
    else return l.num>r.num;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                LL x;
                cin>>x;
                v[i].push_back(x);
            }
            mp[v[i]]++;
            st.insert(v[i]);
        }
        cout<<st.size()<<endl;
        LL idx=1;
        for(auto i:st)
        {
            a[idx].id=idx;
            a[idx].num=mp[i];
            a[idx].bf=i;
            idx++;
        }
        sort(a+1,a+idx,cmp);
        for(int i=1;i<idx;i++)
        {
            cout<<a[i].num;
            for(int j=0;j<a[i].bf.size();j++)
            {
                cout<<" "<<a[i].bf[j];
            }
            cout<<endl;
        }
    }
    return 0;
}

L2-040 哲哲打游戏

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=4002;
#define endl '\n'
vector<LL> v[N];
map<LL,LL> mp;
LL n,m;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            LL k;
            cin>>k;
            while(k--)
            {
                LL x;
                cin>>x;
                v[i].push_back(x);
            }
        }
        LL flag=1;//初始的时候剧情点就在1的位置
        for(int i=1;i<=m;i++)
        {
            LL x,y;
            cin>>x>>y;
            if(x==0) flag=v[flag][y-1];//选择,因为vector是从0开始的，所以y会比下标大一个
            else if(x==1)//x==1就表示是储存操作
            {
                mp[y]=flag;//把当前剧情点放入数组之中，再输出当前剧情点 map？？
                cout<<flag<<endl;
            }
            else if(x==2) flag=mp[y];//读取了放在第y个位置上的存档
        }
        cout<<flag<<endl;//输出最后一个位置上的剧情点
    }
    return 0;
}

标签：练习题,typedef,const,int,LL,cin,long,L2,036
From： https://www.cnblogs.com/Vivian-0918/p/17064593.html

相关文章

  • Day11练习题
    text文件内容fileiseitheratextorbytestringgivingthenameandthepathifthefileisn'tinthecurrentworkingdirectoryofthefiletobeopenedora......
  • 洛谷P2036 PERKET题解
     先来审题，主要有以下几个条件：酸度求乘积，苦度求和，两者相减的值最小（当然是绝对值）。下面附上AC代码：#include<bits/stdc++.h>//万能头文件usingnamespacestd;//......
  • 天梯赛练习题L2（031-035）
    L2-031深入虎穴这个题目我疑惑了好久，因为它说只有一个入口，但是却没有告诉我们哪个是入口，并且需要我们找出距离入口最远的那扇门所以我们在做题时要一一判断哪个是入口，......
  • SQL260 牛客每个人最近的登录日期(一)
    题目描述请你统计一下牛客每个用户最近登录是哪一天。有一个登录(login)记录表,请你写出一个sql语句查询每个用户最近一天登录的日子，并且按照user_id升序排序思路每个......
  • wsl2 参考的对象类型不支持尝试的操作
    原因使用代理软件，或游戏加速服务，winsock出现问题。可以通过注册表的方式，从winsock中排除wsl即可新增注册表信息新建.reg后缀的文本文件,内容为WindowsRegistryE......
  • 通过WSL2在Windows11环境下运行Xilinx ISE 14.7
    引言最近我开始学习FPGA，但是软件配置上就折腾了好久，所以通过这篇文章记录一下Win11下ISE的安装流程。开始我按照入门教程安好了Vivado打算开始愉快的学习，结果发现...我买......
  • 网络流24题（wll24）
    Howtobuildamap?byCiaxin大体概括网络流和线性规划24题中23道的模型与建图思路，以下所有的题目的思路均会向图论方向靠近。目录目录Howtobuildamap?目录#......
  • LibreOJ L2056 「TJOI / HEOI2016」序列
    https://loj.ac/p/2056CDQ优化DP模板？首先定义对于第\(x\)个数其可以变为的最小值为\(Min_x\)，最大值为\(Max_x\)，初始为\(M_x\)。因为最多只会变一次数，不难想到......
  • SQL258 找到每个人的任务
    题目描述有一个person表，主键是id，有一个任务(task)表如下，主键也是id请你找到每个人的任务情况，并且输出出来，没有任务的也要输出，而且输出结果按照person的id升序排序思路......
  • SQL256 出现三次以上相同积分的情况
    题目描述积分(grade)表,id为用户主键id，number代表积分情况，让你写一个sql查询，积分表里面出现三次以及三次以上的积分，查询结果注意：若有多个符合条件的number，则按number升......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99