2020ICPC上海 D - Walker M - Gitignore

D:

首先显然要二分,判断当前二分的mid时间下是否能满足走满0~n

枚举所有情况,这里按照左,右起点p1,p2分别讨论

p1向左 p2向左(以下向左和向右都代表向左或者向右到墙,而不代表初速度方向),只需要计算p1或者p2反弹之后还能走距离n就是合法

p1向左 p2向右,这里有四种情况

四种只需要判断上半部分相加是否大于等于n即可

p1向右 p2向左

只需要判断上下一个分支拐弯之后只要有一个可以多走>=n 或者上下两个分支都能走到墙,也就是拐弯之后可以多走的距离>=0即可

p1向右 p2向右:同第一种情况

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
double n,p1,p2,v1,v2;
double eps=1e-10;
bool deal(double a)
{double t1l=p1/v1;double t1r=(n-p1)/v1;double t2l=p2/v2;double t2r=(n-p2)/v2;//左左		double s1=-1,s2=-1;if(t1l<=a){double t1=a-t1l;s1=t1*v1;}if(t2l<=a){double t2=a-t2l;s2=t2*v2;}if(s1>=n||s2>=n)return true;//左右s1=-1,s2=-1;if(t1l<=a){double t1=a-t1l;s1=max(t1*v1,t1*v1/2+p1);}if(t2r<=a){double t2=a-t2r;s2=max(t2*v2,t2*v2/2+(n-p2));}if(s1+s2>=n)return true;//右左s1=-1,s2=-1;if(t1r<=a){double t1=a-t1r;s1=t1*v1;}if(t2l<=a){double t2=a-t2l;s2=t2*v2;}if(s1>=n||s2>=n||(s1>0&&s2>0))return true;//右右s1=-1,s2=-1;if(t1r<=a){double t1=a-t1r;s1=t1*v1;}if(t2r<=a){double t2=a-t2r;s2=t2*v2;}if(s1>=n||s2>=n)return true;return false;
}
bool check(double a)
{return deal(a);
}
void solve()
{
//    cin>>n;scanf("%Lf",&n);scanf("%Lf",&p1);scanf("%Lf",&v1);scanf("%Lf",&p2);scanf("%Lf",&v2);double l=0,r=1e9;if(p1>p2){swap(p1,p2);swap(v1,v2);}while(r-l>eps){double mid=(r+l)/2;check(mid)?r=mid:l=mid;}printf("%.10Lf\n",l);return ;
}
signed main()
{int T=1;sf(T);while(T--)solve();return 0;
}

M:

一个类似树形的思想,把所有的可删/不可删的文件映射为下标,然后按照文件路径建树,注意,不同文件夹下的子文件夹名字可能相同,例如

a/b/c和b/b/d并不冲突

所以不是a->b->c这么建树而是a->a/b->a/b/c这样建树

把所有的可以删除的文件,在建树之后就是对应的叶子结点赋权值为0,不可删除的文件对应的叶子节点赋权值为1(这里注意要建立一个虚拟源点并且权值为1,这样假如所有的文件都可以删除的话递归到虚拟源点的时候就会删除,后面会提到)

样例如下

假设某个点的子树(包括自己)权值为0,则向上递归

否则再次找到这个点u的所有儿子,如果儿子的权值为0则res++

此时就能体会出虚拟源点权值为1的好处,假设输入样例为

3 0

a

b

c

那么递归到虚拟源点的时候碰到子树a,b,c就res++三次,答案就为3

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
map<string,int>mp;
int idxx;
int e[N],ne[N],h[N],w[N],idx;
int sz[N];
map<PII,bool>pan;
void add(int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
string s;
void deal(string s,int c)
{string now="";int pre=1;_rep(i,0,(int)s.size()-1){if(s[i]=='/'){if(!mp.count(now))mp[now]=++idxx;int t=mp[now];if(!pan.count({pre,t}))add(pre,t);pan[{pre,t}]=true;pre=t;
//			now="";}now+=s[i];}if(!mp.count(now))mp[now]=++idxx;int t=mp[now];w[t]=c;add(pre,t);pre=t;
//	now="";return;
}
int res;
int dfs(int u,int fa)
{sz[u]=w[u];for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa)continue;sz[u]+=dfs(j,u);}if(sz[u]){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa)continue;if(!sz[j])res++;
//			cout<<"j="<<j<<endl;}}return sz[u];
}
void solve()
{res=0;idxx=1;idx=0;cin>>n>>m;_rep(i,1,n){cin>>s;deal(s,0);}_rep(i,1,m){cin>>s;deal(s,1);}w[1]=1;dfs(1,0);_rep(i,0,idxx)h[i]=-1,w[i]=0;mp.clear();pan.clear();cout<<res<<'\n';return ;
}
signed main()
{IOS;memset(h,-1,sizeof(h));int T=1;cin>>T;while(T--)solve();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PHP智慧家政同城服务家政系统小程序源码

智慧家政&#xff0c;同城服务新篇章 —— 探索家政系统的无限可能 开篇&#xff1a;走进智慧家政时代 在这个快节奏的生活中&#xff0c;每一分每一秒都显得尤为珍贵。当忙碌成为常态&#xff0c;如何让家成为真正的避风港&#xff1f;答案或许就藏在“智慧家政同城服务家政…

155K Star,Python 入门到进阶最佳学习资源

Hi&#xff0c;骚年&#xff0c;我是大 G&#xff0c;公众号「GitHub 指北」会推荐 GitHub 上有趣有用的项目&#xff0c;一分钟 get 一个优秀的开源项目&#xff0c;挖掘开源的价值&#xff0c;欢迎关注。 导语 如果你正在寻找一个全面、系统、深入的 Python 学习项目&#…

合资油车断崖式崩盘,买车的千万慎重了

文 | AUTO芯球 作者 | 雷慢 合资车&#xff0c;燃油车全体大逃亡的时候来了&#xff0c; 你敢信吗&#xff0c;8月份&#xff0c;国内新能源汽车零售渗透率达到54%&#xff0c; 我给大家讲个冷笑话&#xff0c; 几个月前还有车企老总说什么&#xff0c; “只要传统车企一发…

pyflink 安装和测试

FPY Warning! 安装 apache-Flink # pip install apache-Flink -i https://pypi.tuna.tsinghua.edu.cn/simple/ Looking in indexes: https://pypi.tuna.tsinghua.edu.cn/simple/ Collecting apache-FlinkDownloading https://pypi.tuna.tsinghua.edu.cn/packages/7f/a3/ad502…

软件测试学习笔记丨Docker 安装、管理、搭建服务

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/32192 容器&#xff08;Docker&#xff09;技术的价值 保证环境一致性&#xff0c;只要使用相同镜像部署就可以保证一致性。轻量级虚拟化访问&#xff0c;运行更快&#xff0c;资源更小。同时…

微信小程序使用 ==== 粘性布局

目录 Chrome杀了个回马枪 position:sticky简介 你可能不知道的position:sticky 深入理解粘性定位的计算规则 粘性定位其他特征 代码实现 微信小程序在scroll-view中使用sticky Chrome杀了个回马枪 position:sticky早有耳闻也有所了解&#xff0c;后来&#xff0c;Chro…

长业务事务的离线并发问题

事务指代一组操作同时成功或同时失败&#xff0c;事务可分为两类&#xff1a; 系统事务&#xff1a;即关系数据库事务&#xff0c;一次数据库连接中由start transaction或begin开启&#xff0c;commit表示提交&#xff0c;rollback表示回滚&#xff1b;业务事务&#xff1a;完…

力扣题解2848

大家好&#xff0c;欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述&#xff08;简单&#xff09;&#xff1a; 与车相交的点 给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i&#xff0c;nums[i] [starti, endi] &…

html+css+js网页设计 旅游 厦门旅游网10个页面

htmlcssjs网页设计 旅游 厦门旅游网10个页面 网页作品代码简单&#xff0c;可使用任意HTML辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码 1&am…

SpringBoot权限认证-Sa-Token的使用与详解

本文详细介绍了Sa-Token在Java项目中的使用方法&#xff0c;包括Sa-Token的基本概念、与其他权限框架的比较、基本语法和高级用法&#xff0c;并通过实例讲解了如何在项目中集成和使用Sa-Token。作为一款轻量级Java权限认证框架&#xff0c;Sa-Token在简化权限管理、提高开发效…

『功能项目』切换职业技能面板【49】

我们打开上一篇48切换职业面板的项目&#xff0c; 本章要做的事情是制作第二职业法师技能面板、第三职业面板并且完成切换 双击打开Canvas进入预制体空间 复制三个技能栏面板 重命名 设置第一技能栏 设置第二职业技能栏 设置第三职业技能栏 修改脚本&#xff1a;ChangeProfess…

FreeRTOS—任务通知

一&#xff0c;概念介绍 队列、信号量、事件组等IPC技术都需要创建一个中间对象进程之间通过这些中间对象进行通讯或同步。创建对象就需要分配内存&#xff0c;占用一定内存。 二&#xff0c;任务通知的特点&#xff1a; 一个任务或ISR向另外一个指定的任务发送通知&#xff0c…

PhpStudy下载安装使用学习

一、官网下载 官网地址&#xff1a;Windows版phpstudy下载 - 小皮面板(phpstudy)https://old.xp.cn/download.html 【首页】选择Windows版&#xff0c;进行下载 下载完成是一个压缩包的形式&#xff0c;解压得到一个.exe的执行文件&#xff0c;点击执行安装程序&#xff08;注…

Spring Boot环境下的学生读书笔记共享

第4章 系统设计 4.1系统结构设计 读书笔记共享平台的设计主要是为了满足用户的实际需求。 因此&#xff0c;它需要通过Internet实现&#xff0c;因此它必须具备硬件和软件基础。该平台最终可以通过科学技术和各种方式达到支持智能化的信息管理的目的。因此&#xff0c;它必须具…

数据结构——(java版)Map与Set

文章目录 二叉搜索树&#xff08;1&#xff09; 二叉搜索树的概念&#xff1a;&#xff08;2&#xff09;二叉搜索树的意义&#xff1a;&#xff08;3&#xff09;二叉搜索树的实现&#xff1a;实现的方法与属性实现二叉搜索树的查询&#xff1a;实现二叉搜索树的插入&#xff…

【Kubernetes笔记】为什么DNS解析会超时?

【Kubernetes笔记】为什么DNS解析会超时&#xff1f; 目录 1 问题背景2 产生后续的问题3 DNS 负缓存工作原理&#xff1a;4 如何解决和缓解 DNS 负缓存 4.1 减小负缓存 TTL4.2 重试机制4.3 减少 Pod 的频繁重启或调度4.4 使用 Headless Service4.5 手动刷新 DNS 缓存 5 总结 …

【Unity】 HTFramework框架(五十六)MarkdownText:支持运行时解析并显示Markdown文本

更新日期&#xff1a;2024年9月15日。 Github源码&#xff1a;[点我获取源码] Gitee源码&#xff1a;[点我获取源码] 索引 MarkdownText支持的Markdown语法标题强调文本表格嵌入图像超链接 使用MarkdownText设置项运行时属性解析使用ID模式嵌入图像 MarkdownText MarkdownText…

【Python机器学习】循环神经网络(RNN)——对RNN进行预测

目录 有状态性 双向RNN 编码向量 如果有一个经过训练的模型&#xff0c;接下来就可以对其进行预测&#xff1a; sample_1""" I hate that the dismal weather had me down for so long,when will it break! Ugh,when does happiness return? The sun is bl…

Neo4j图数据库

文章目录 一、Neo4J相关介绍1.为什么需要图数据库方案1&#xff1a;Google方案2&#xff1a;Facebook 2.特定和优势3.什么是Neo4j4.Neo4j数据模型图论基础属性图模型Neo4j的构建元素 5.软件安装 二、CQL语句1.CQL简介2.CREATE 命令3.MATCH 命令4.RETURN 子句5.MATCH和RETURN6.C…

Qt_显示类控件

目录 一、QLabel 1、QLabel属性介绍 2、textFormat文本格式 3、pixmap标签图片 3.1 resizeEvent 4、QFrame边框 5、alignment文本对齐 6、wordWrap自动换行 7、indent设置缩进 8、margin设置边距 9、buddy设置伙伴 二、QLCDNumber 1、QLCDNumber属性介绍 2、实…