Toyota Programming Contest 2024#4(AtCoder Beginner Contest 348)(A~D)

A - Penalty Kick

i,1~N。如果 i 是 3 的倍数输出x,否则输出o

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
//#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int n;
    cin>>n;
    
    per(i,1,n){
        if(i%3==0){
            cout<<"x";
        }else cout<<"o";
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

B - Farthest Point

给你 N 个点,问你 1~N 每个点,各自的最远点是哪个,两点距离计算公式如下图所示

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
//#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int n;
    cin>>n;
    
    int x[n+1],y[n+1];
    per(i,1,n){
        cin>>x[i]>>y[i];
    }
    
    per(i,1,n){
        int ansidx;
        bool flag=true;
        double dis;
        per(j,1,n){
            if(j!=i){
                if(flag){
                    flag=false;
                    ansidx=j;
                }else{
                    double res=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
                    if(res>sqrt(pow(x[i]-x[ansidx],2)+pow(y[i]-y[ansidx],2))){
                        ansidx=j;
                    }
                }
            }
        }
        cout<<ansidx<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

C - Colorful Beans

输入 N 种豆子,每种豆子 美味度Ai,颜色Ci。

问:每个颜色的最小值x1,x2,x3,x4。max{x1,x2,x3,x4}是多少

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
//#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int n;
    cin>>n;
    
    int ans=0;
    
    map<int,int>f;
    
    int a[n+1],c[n+1];
    per(i,1,n){
        cin>>a[i]>>c[i];
        if(!f[c[i]])f[c[i]]=a[i];
        else if(a[i]<f[c[i]])f[c[i]]=a[i];//同颜色里面取最小值
    }
    
    for(auto [color,val]:f){
        ans=max(ans,val);
    }
    cout<<ans;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

D - Medicines on Grid

从S点出发,是否能走到T点,每走一步花费 1 点能量,如果能量为 0 则不能走。(刚开始能量为0)

样例前面的 4*4 给的是网格图。

后面的 4 行是网格上的能量点:1,1,3就是 点{1,1}上有能量 3。

当你在能量点上面的时候,你可以将目前有的能量 变成 当前能量点的数量。(注意不是增多也不是减少,是变成那个值)并且只能使用一次。

如果说暴力搜索我们考虑一种情况。

P是图上的能量点,必须要拿到这个能量点,才能到达终点T。

所以暴力搜索不行,如果历史点只访问一次,不会超时,但是答案错了。

如果每个点都走,那时间复杂度肯定爆了。

通过上面的分析可以发现,终点一定来自于能量点

这样我们可以去找,能量点之间是否可以相互到达,以及能量点是否可以到达终点。

如果某个能量点可以被走到,并且这个能量点可以到达终点。那么就有解。

然后就是惊天大模拟:

起点是能量点的话,进队列,然后遍历剩下没被走过的能量点,看是否能被走到,能就加入队列,顺便判断一下是否能到终点即可。

BFS一次的复杂度是H*W=4e4(BFS求能量点到其他点的最短路)

而且题目中能量点最多只有300个

从每个能量点出发BFS一次,一共3e2*4e4≈1e7(刚好通过题目)

代码仅供参考,本蒟蒻写的太多了,可读性很差

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
//#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int h,w;
    cin>>h>>w;
    
    string s[h+1];
    per(i,1,h){
        cin>>s[i];
        s[i]="0"+s[i];
    }
    
    struct Node{
        int x,y,val;
    }S,T;
    
    per(i,1,h){
        per(j,1,w){
            if(s[i][j]=='S'){
                S={i,j,0};
            }
            if(s[i][j]=='T'){
                T={i,j,0};
            }
        }
    }
    
    int n;
    cin>>n;
    

    //. 代表格子为空
    //# 代表障碍
    //S 起点
    //T 目标点
    //消耗 1 点能量水平或者垂直移动到相邻的空的格子
    //能量为0不能移动
    
    //(Ri,Ci)上有药,可以将能量设置成Ei,只能使用一次
    
    //BFS一次复杂度4e4   //最多300个补给点
    
    int r[n+1],c[n+1],e[n+1],toT[n+1],toS[n+1];
    map<array<int,2>,int>f;
    map<pair<int,int>,int>g;
    map<int,pair<int,int>>p;
    per(i,1,n){
        cin>>r[i]>>c[i]>>e[i];
        f[{r[i],c[i]}]=e[i];
        g[{r[i],c[i]}]=i;//补给点标号
    }
    
    int dis[305][305];//补给点到补给点的距离
    per(i,1,300){
        per(j,1,300){
            dis[i][j]=INT_MAX>>1;
        }
    }
    per(i,1,n)toS[i]=toT[i]=INT_MAX>>1;
    
    per(i,1,n){//toS,补给点去S的距离,toS去T的距离
        
        Node now={r[i],c[i],0};
        
        queue<Node>q;
        q.push(now);
        
        bool vis[h+1][w+1];
        per(i,1,h){
            per(j,1,w){
                vis[i][j]=false;
            }
        }
        
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        
        while(q.size()){//BFS
            Node now=q.front();
            q.pop();
            if(vis[now.x][now.y])continue;
            if(f[{now.x,now.y}]){
                dis[i][g[{now.x,now.y}]]=min(dis[i][g[{now.x,now.y}]],now.val);
                dis[g[{now.x,now.y}]][i]=min(dis[g[{now.x,now.y}]][i],now.val);
            }
            if(now.x==S.x and now.y==S.y){
                toS[i]=min(toS[i],now.val);
            }
            if(now.x==T.x and now.y==T.y){
                toT[i]=min(toT[i],now.val);
            }
            vis[now.x][now.y]=true;
            
            per(i,0,3){
                Node nxt={now.x+dx[i],now.y+dy[i],now.val+1};
                if(nxt.x>=1 and nxt.x<=h and nxt.y>=1 and nxt.y<=w){
                    if(s[nxt.x][nxt.y]!='#'){
                        q.push(nxt);
                    }
                }
            }
        }
    }
    
    if(!f[{S.x,S.y}]){//起始点没有能量
        cout<<"No";
    }else{
        
        //从补给点S开始能到达哪些点
        
        queue<int>q;
        
        bool vis[n+1];
        per(i,1,n)vis[i]=false;
        
        per(i,1,n){
            if(r[i]==S.x and c[i]==S.y){//起点,能量为e[i]
                q.push(i);
                vis[i]=true;
            }
        }
        
        while(q.size()){
            int now=q.front();
            q.pop();
            
            per(i,1,n){
                if(!vis[i]){
                    if(e[now]>=dis[now][i]){
                        vis[i]=true;
                        q.push(i);
                    }
                }
            }
        }
        
        per(i,1,n){
            if(vis[i] and e[i]>=toT[i]){
                cout<<"Yes";
                return;
            }
        }
        cout<<"No";
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521071.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

HTTP详解及代码实现

HTTP详解及代码实现 HTTP超文本传输协议 URL简述状态码常见的状态码 请求方法请求报文响应报文HTTP常见的HeaderHTTP服务器代码 HTTP HTTP的也称为超文本传输协议。解释HTTP我们可以将其分为三个部分来解释&#xff1a;超文本&#xff0c;传输&#xff0c;协议。 超文本 加粗样…

开源 _ 新一代Android 性能监控框架Rabbit

最终扫描结果会展示如下: 点击右上角导出按钮可以把扫描结果以json的形式导出到SD卡中。 网络日志监控 rabbit可以记录网络请求日志并方便的查看返回的json数据: 卡顿日志监控 rabbit通过Choreographer来检测主线程的运行情况,并异步采集主线程堆栈来还原卡顿现场。 对于下…

总包不足80w的高龄Android程序员,被面试官diss混得太差,网友狂吐槽……

有网友直言&#xff1a;90%的人一辈子一年也拿不到80万 有网友分析到&#xff1a;看面试情况&#xff0c;没什么希望就直接其实我觉得30岁年薪低于1000万的都是loser&#xff0c;你我都是 有网友说&#xff1a;这几年互联网行业极大发展&#xff0c;让互联网行业成为了明星行…

2_6.Linux高级存储管理

##1.逻辑卷## pv ##物理卷 被处理过的物理分区 pe ##物理扩展 设定存储最小单元 vg ##物理卷组 捆绑pv到一个组中 lv ##逻辑卷 分配最终的使用设备 监控建立过程&#xff1a; watch -n 1 "pvs;echo ;vgs;echo ;lvs;echo ;df -h /weixindata" &#xff08;1&#xf…

合理早餐选择,稳定糖尿病血糖。

对于糖尿病患者来说&#xff0c;饮食管理是治疗的重要一环。不合理的早餐选择会导致血糖的波动。很多糖尿病朋友按时吃药&#xff0c;但是血糖就是稳定不住&#xff0c;之前看过一个例子&#xff0c;北京崇文门医院朱学敏主任接诊过一个患者&#xff0c;那个患者按时吃药&#…

C++设计模式:装饰器模式(四)

1、定义与动机 装饰器模式定义&#xff1a;动态&#xff08;组合&#xff09;地给一个对象增加一些额外的职责。就增加功能而言&#xff0c;Decorator模式比生成子类&#xff08;继承&#xff09;更为灵活&#xff08;消除重复代码 & 减少子类个数&#xff09;。 在某些情…

ARM体系结构

阅读引言&#xff1a; arm架构处理器的基本知识已在上一篇文章中描述过了&#xff0c; 本文将会从arm的存储模型、异常机制、工作模式、指令集、流水线、arm的寄存器组织方面去描述。 目录 一、ARM处理器概论 1.指令集概述 2.指令分类 3.编译流程 二、ARM的存储模型 1.AR…

电商技术揭秘七:搜索引擎中的SEO关键词策略与内容优化技术

文章目录 引言一、关键词策略1.1 关键词研究与选择1. 确定目标受众2. 使用关键词研究工具3. 分析搜索量和竞争程度4. 考虑长尾关键词5. 关键词的商业意图6. 创建关键词列表7. 持续监控和调整 1.2 关键词布局与密度1. 关键词自然分布2. 标题标签的使用3. 首次段落的重要性4. 关键…

C# 分布式自增ID算法snowflake(雪花算法)

文章目录 1. 概述2. 结构3. 代码3.1 IdWorker.cs3.2 IdWorkerTest.cs (测试) 1. 概述 分布式系统中&#xff0c;有一些需要使用全局唯一ID的场景&#xff0c;这种时候为了防止ID冲突可以使用36位的UUID&#xff0c;但是UUID有一些缺点&#xff0c;首先他相对比较长&#xff0c…

pyside6怎么使用Qt Designer设计自定义组件

第一步&#xff0c;新建一个自定义组件的python文件 from PySide6.QtWidgets import QPlainTextEdit from PySide6.QtCore import Signal,Qtclass CustomPlainTextEdit(QPlainTextEdit):enterPressed Signal(str)def __init__(self, parentNone):super().__init__(parent)def…

Vue+node.js蔬菜水果农产品网上商城管理系统

用户能够及时掌握最新的数据&#xff0c;并能有效地提升用户的服务水平。本制度的优势在于&#xff1a; &#xff08;1&#xff09;该系统将蔬菜信息及时地提供给使用者。使用者可以在任何时候登陆该网站查询相关资讯&#xff0c;所有资讯均真实可信&#xff0c;并严肃处理各项…

161 Linux C++ 通讯架构实战15,线程池代码分析

线程池应该使用的地方 和 epoll 技术结合 线程池代码处理数据的地方。 线程池分析&#xff1a; 线程池代码1 threadpool_create //Tencent8888 start threadpool_create函数的目的初始化线程池&#xff0c;对应的struct是 threadpool_t /* 1.先malloc整个线程池的大小 2.这里…

牛客 2024春招冲刺题单 ONT98 牛牛猜节点【中等 斐波那契数列 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/6a3dfb5be4544381908529dc678ca6dd 思路 斐波那契数列参考答案Java import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规…

Unity与CocosCreator对比学习二

一、锚点与适配 1.在Creator中 适配通过锚点、位置和Widget达到适配目的&#xff1b;锚点是节点在其父节点坐标系中坐标对其点&#xff0c;其x,y范围在[0, 1]之间&#xff1b; 锚点为(0, 0)时在节点自身的左下角&#xff0c;节点坐标指其左下角在父节点中的坐标&#xff1b;锚…

贪心算法|53.最大子序和

力扣题目链接 class Solution { public:int maxSubArray(vector<int>& nums) {int result INT32_MIN;int count 0;for (int i 0; i < nums.size(); i) {count nums[i];if (count > result) {result count;}if (count < 0) count 0;}return result;} …

[AIGC] Spring Filter 过滤器详解

什么是Spring Filter 在Web应用中&#xff0c;Filter&#xff08;过滤器&#xff09;是在Java Servlet规范中的一种组件&#xff0c;它的主要目的是对HTTP请求或者响应进行处理。Spring Filter则是Spring框架对Java原生Filter的封装版本和扩展。 简单来说&#xff0c;Spring …

物联网实战--驱动篇之(二)Modbus协议

目录 一、modbus简介 二、功能码01、02 三、modbus解析 四、功能码03、04 五、功能码05 六、功能码06 七、功能码16 一、modbus简介 我们在网上查阅modbus的资料发现很多很杂&#xff0c;modbus-RTU ASCII TCP等等&#xff0c;还有跟PLC结合的&#xff0c;地址还分1开…

如果在 Ubuntu 系统中两个设备出现两个相同的端口号解决方案

问题描述&#xff1a; 自己的移动机器人在为激光雷达和IMU配置动态指定的端口时&#xff0c;发现激光雷达和深度相机配置的 idVendor 和 idProduct 相同&#xff0c;但是两个设备都具有不同的ttyUSB号&#xff0c;如下图所示 idVendor&#xff1a;代表着设备的生产商ID,由USB设…

并查集学习(836. 合并集合 + 837. 连通块中点的数量)

//得先加集合个数再合并&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 核心代码&#xff1a; int find(int x){//返回父节点if(x ! p[x]) {p[x] find(p[x]);//路径压缩 } //孩子不等于爸爸&#xff0c;就…

springboot+vue学生宿舍物品存放系统tnozt

需求包括&#xff1a; 三个角色&#xff1a;学生&#xff0c;公寓管理员&#xff08;宿舍管理人员&#xff09;&#xff0c;系统管理员。 本系统基于java语言&#xff0c;结合数据库技术&#xff0c;通过面向对象的设计方法&#xff0c;实现学生信息管理、公寓信息管理、物品存…