CCF刷题计划——坐标变换(其二)(前缀和)
坐标变换(其二)
首先我按照一般的逻辑写出来,居然超时了???
之后想了想,还是觉得大有可为的,对拉伸前缀积,对旋转前缀和成功解决问题。
80分:超时
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e5;struct Operate
{int op;double k;
};int n,m;
vector<Operate>inst(N);void stretch(double&x,double&y,double&k)
{x=k*x;y=k*y;
}void rotate(double&x,double&y,double&k)
{//巨大坑点!!!计算旋转结果时要避免纵坐标受到横坐标已经计算从而变化的影响 double tempx=x; x=x*cos(k)-y*sin(k);y=tempx*sin(k)+y*cos(k);
}int main()
{cin>>n>>m; //操作和查询次数Operate t;for(int i=1;i<=n;i++){cin>>t.op>>t.k;inst[i]=t;}double x,y,l,r;while(m--){cin>>l>>r>>x>>y;for(int i=l;i<=r;i++){ if(inst[i].op==1)stretch(x,y,inst[i].k);else if(inst[i].op==2)rotate(x,y,inst[i].k);}printf("%.3lf %.3lf\n",x,y);} return 0;}
改进策略,我觉得伸缩是线性的变换,可能通过类似前缀和的方式进行规整。比如说,执行12345这五条指令,其中135都是伸缩指令,按理说,我们一共需要执行五次。如果使用类似前缀和的想法,我们只需要知道1、5这两次的前缀积,然后将k[5]/k[1-1],就可以得到这部分总共需要处理的伸缩值了。
但是我发现这样还是有问题,因为为了判断旋转这种,还是会遍历一遍。那么,旋转,能类似前面的方式进行优化吗?如果不看公式,看角度的话,旋转其实也是一种线性的变化,无非是在前面的基础上进行加减罢了。我们可以累计这几步总共旋转了多少角度,最后再统一计算。
100昏:(一个坐标变换居然用上前缀和我是没想到的)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e5;int n,m;
//这里使用前缀和进行优化
int inst[N]={0};
double mul_k[N]={1};
double angle[N]={0};void stretch(double&x,double&y,double k)
{x=k*x;y=k*y;
}void rotate(double&x,double&y,double k)
{//巨大坑点!!!计算旋转结果时要避免纵坐标受到横坐标已经计算从而变化的影响 double tempx=x; x=x*cos(k)-y*sin(k);y=tempx*sin(k)+y*cos(k);
}int main()
{cin>>n>>m; //操作和查询次数int op;double k;for(int i=1;i<=n;i++){cin>>op>>k;if(op==1) //在不同处理的同时需要对无关参数顺移 {mul_k[i]=mul_k[i-1]*k;angle[i]=angle[i-1];}else{mul_k[i]=mul_k[i-1];angle[i]=angle[i-1]+k;}}double x,y;int l,r;while(m--){cin>>l>>r>>x>>y;stretch(x,y,mul_k[r]/mul_k[l-1]);rotate(x,y,angle[r]-angle[l-1]);printf("%.3lf %.3lf\n",x,y);} return 0;}
相关文章:
CCF刷题计划——坐标变换(其二)(前缀和)
坐标变换(其二) 首先我按照一般的逻辑写出来,居然超时了??? 之后想了想,还是觉得大有可为的,对拉伸前缀积,对旋转前缀和成功解决问题。 80分:超时 #inclu…...
游戏开发简述
《黑神话:悟空》爆红后,游戏开发一时成为热点。作为个人或小公司,能否进入游戏开发领域。从纯技术角度而言,并不是可望不可即: 另:学会了,哪怕自己干不成,招游戏开发的岗位也不少&am…...

最新前端开发VSCode高效实用插件推荐清单
在此进行总结归类工作中用到的比较实用的、有助于提升开发效率的VSCode插件。大家有其他的好插件推荐的也欢迎留言评论区哦😄 基础增强 Chinese (Simplified) Language Pack: 提供中文界面。 Code Spell Checker: 检查代码中的拼写错误。 ESLint: 集成 ESLint&…...

分布式调度方案:Elastic-Job
文章目录 一、什么是分布式调度二、Elastic-Job 介绍三、Elastic-Job 实战3.1 环境搭建3.1.1 本地部署3.1.2 服务器部署3.1.3 Zookeeper 管控台界面 3.2 入门案例3.3 SpringBoot 集成 Elastic-Job3.4 任务分片(★)3.5 Dataflow 类型调度任务 一、什么是分…...

网络安全工程师(白帽子)企业级学习路线
第一阶段:安全基础(入门) 第二阶段:Web渗透(初级网安工程师) 第三阶段:进阶部分(中级网络安全工程师)...
数据结构详细解释
数据结构 1. 线性数据结构 数组(Array) 定义:数组是一种固定大小的、元素类型相同的线性数据结构。元素在内存中是连续存储的,可以通过索引直接访问。 特点: 支持常数时间的随机访问(O(1))。…...

7.1图像平移
目录 实验原理 示例代码1 运行结果1 示例代码2 运行结果2 实验原理 OpenCV中,图像平移是一种基本的几何变换,指的是将图像中的每一个像素点沿着水平方向或垂直方向移动一定的距离。图像平移不改变图像…...

海外云手机是否适合运营TikTok?
随着科技的迅猛发展,海外云手机逐渐成为改变工作模式的重要工具。这种基于云端技术的虚拟手机,不仅提供了更加便捷、安全的使用体验,还在电商引流和海外社媒管理等领域展示了其巨大潜力。那么,海外云手机究竟能否有效用于运营TikT…...
IT 行业中常见的专业名称及其含义
API(Application Programming Interface) API 是应用程序编程接口,定义了不同软件系统之间如何互相通信的规则和方式。开发人员使用 API 将应用程序与外部服务集成,进行数据交换或调用外部功能。 IDE(Integrated Deve…...

全球开店,Shopee东南亚入驻指南|用友BIP电商通引领电商出海新潮流
在全球化的浪潮中,东南亚市场以其蓬勃的发展态势成为中国企业出海的首选之地。得益于其语言、物流、仓储、距离及政策的友好性,东南亚市场已成为企业海外拓展的必争之地。作为东南亚领先的电商平台,Shopee以其庞大的用户基础和高度的用户活跃…...
java当中什么是NIO
Java中的NIO(Non-blocking I/O)即非阻塞I/O,是Java 1.4中引入的一种新的I/O API,用于替代传统的I/O(即BIO, Blocking I/O)。与传统的阻塞式I/O相比,NIO提供了更高效的I/O操作,特别是…...

【基础】Three.js 自定义几何体和复制几何体
通过自定义顶点数据,可以创建任意的几何体。像threejs的长方体BoxGeometry、球体SphereGeometry等几何体都是基于BufferGeometry类构建的,它表示一个没有任何形状的空几何体。 1. 自定义点模型 通过javascript 类型化数组 Float32Array创建一组xyz坐标…...
如何使用ChatGPT进行高效的对话生成与优化
目录 一、对话生成的基础原理 二、如何优化对话生成的流畅性与上下文关联性 1. 提示词优化:明确上下文和期望目标 示例:提示词优化 2. 调整生成参数:控制生成长度与内容多样性 示例:调整生成参数 3. 上下文管理:…...

MySQL系列—8.存储结构
目录 1.系统表空间 ibdata 2.通用表空间 .ibd 3.独立表空间 4.Undo 表空间 5.临时表空间 6.Redo Log File 1.系统表空间 ibdata 系统表空间由参数innodb_data_file_path定义路径、初始化大小、自动扩展策略 如: innodb_data_file_path/dayta/mysql/ibdata1:…...

vue2、vue3生成二维码
Vue2版: 工具:使用 qrcodejs插件来生成二维码 安装:npm install qrcodejs2 qrcodejs官网地址: https://davidshimjs.github.io/qrcodejs/https://davidshimjs.github.io/qrcodejs/ 代码示例: <template><…...
Spring Cloud全解析:熔断之Hystrix线程隔离导致的问题
Hystrix线程隔离 在微服务框架中,可能一个服务需要调用多个微服务,在tomcat中运行时,tomcat只是分配了100个线程,由于多个服务之间调用的时间消耗过长,可能会导致线程耗尽,而在Hystrix中存在线程隔离&…...

网络编程项目(云词典项目)
目录 一、功能要求 服务器 用户客户端 二、演示效果 1.登录、注册功能 2. 查单词功能 3.查看历史纪录功能 三、项目代码 1.头文件 2.服务器 3.用户端 一、功能要求 仿照云词典的原理,实现云词典功能,用户可以查询输入的单词的英文解释&…...
Java Spring Boot 项目中的密码加密与验证开发案例手册
本手册主要针对Java项目中的账号密码加密与验证进行详细的步骤讲解和代码示例。适用于开发登录认证、用户管理等功能的场景。文档包含工具类的创建、数据库配置、服务层和控制器层的集成等常见操作。 1. 常用加密操作 在实现安全的登录功能时,密码加密与验证是不可…...

VueSax-解决Vue3报错问题,并支持typescript
以下为坑点 根据官方提示,本人在vue3typescript的项目中添加了vuesax的组件依赖 根据正常的导入依赖思路编写代码,发现typescript一直报 查询vuesax的目录文件发现存在ts文件,于是乎觉得是自己的问题,就查阅gpt与网上资料&#x…...

回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测+交叉验证
回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证 目录 回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现基于贝叶…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...

Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...

【Qt】控件 QWidget
控件 QWidget 一. 控件概述二. QWidget 的核心属性可用状态:enabled几何:geometrywindows frame 窗口框架的影响 窗口标题:windowTitle窗口图标:windowIconqrc 机制 窗口不透明度:windowOpacity光标:cursor…...

智警杯备赛--excel模块
数据透视与图表制作 创建步骤 创建 1.在Excel的插入或者数据标签页下找到数据透视表的按钮 2.将数据放进“请选择单元格区域“中,点击确定 这是最终结果,但是由于环境启不了,这里用的是自己的excel,真实的环境中的excel根据实训…...