当前位置: 首页 > news >正文

noipd8t2 - Slayer

要理解这段代码,需结合题目要求和题解的逆变换 + 辗转相除思路,逐部分分析:

  1. 题目核心与题解思路

    回顾题目要求:给定两个线性变换 \(T1((x,y))=(x+y,y)\)\(T2((x,y))=(x,x+y)\),对于每个查询向量 \((x,y)\),统计有多少个给定的向量可通过若干次\(T1/T2\)变换(包括 0 次)得到。

    题解思路:正向变换可能无限多,逆变换分析更高效。
    观察到:若某一步向量的分量 \(x \leq 0\) 或 \(y \leq 0\),后续会一直保持,而查询的 \((x,y)\) 满足 \(x,y>0\),因此逆变换只有 “大数减小数的倍数” 这一种操作,类似欧几里得辗转相除。对每个给定向量,预处理其 “逆变换的所有中间状态”,存储后排序;查询时,对\((x,y)\)做同样的逆变换,通过二分查找统计符合条件的中间状态数量。

  2. 代码结构与关键逻辑解释

    (1)数据结构与输入处理
    tri 是 std::tuple<int,int,int>,用于存储逆变换过程中的三元组(记录当前分量、余数、原分量信息)。p[0] 和 p[1] 是两个数组,分别存储 “\(a \leq b\)” 和 “\(a > b\)” 两种情况下的三元组;m[0]、m[1] 是对应数组的元素计数。处理每个给定向量 \((a,b)\) 的循环:

    
    for(int a,b,f;n--;){a=read(),b=read(),f=0;while(a&&b)if(a<=b)p[0][++m[0]]={a,b%a,b-f},b%=a,f=1;else p[1][++m[1]]={b,a%b,a-f},a%=b,f=1;
    }

    这里模拟逆变换的辗转相除过程:若 \(a \leq b\),逆变换对应 “由 \((b, a)\) 变换到 \((a, b\%a)\)”,记录三元组 \((a, b\%a, b - f)\)(b - f 用于后续查询时判断原分量范围),然后更新 \(b = b\%a\),标记 \(f=1\)(表示已进行一次操作)。若 \(a > b\),类似处理,记录三元组 \((b, a\%b, a - f)\),更新 \(a = a\%b\),标记 \(f=1\)。循环直到 a 或 b 为 0,此时所有中间状态都被记录到 p[0] 或 p[1] 中。

    (2)排序预处理

    for(int o=2;o--;)std::sort(p[o]+1,p[o]+1+m[o]);
    

    对 p[0] 和 p[1] 分别排序,为后续二分查找做准备,确保能快速统计符合条件的三元组数量。

    (3)查询处理

    for(int a,b,ans;q--;){a=read(),b=read(),ans=0;ans+=std::upper_bound(p[0]+1,p[0]+1+m[0],tri{a,b%a,(int)1e18})-p[0];ans-=std::lower_bound(p[0]+1,p[0]+1+m[0],tri{a,b%a,b})-p[0];ans+=std::upper_bound(p[1]+1,p[1]+1+m[1],tri{b,a%b,(int)1e18})-p[1];ans-=std::lower_bound(p[1]+1,p[1]+1+m[1],tri{b,a%b,a})-p[1];printf("%lld\n",ans);
    }
    

    对每个查询 \((x,y)\)(代码中用a,b接收),模拟逆变换的辗转相除步骤,分两种情况统计:

    • 情况 1(对应p[0]):
      计算 \(y\%x\),在 p[0] 中查找三元组满足 “第一个元素是x、第二个元素是 \(y\%x\)、第三个元素在 \([y, 1e18)\) 范围内” 的数量(通过 upper_bound 和 lower_bound 的差实现)。

    • 情况 2(对应p[1]):
      计算 \(x\%y\),在 p[1] 中查找三元组满足 “第一个元素是y、第二个元素是\(x\%y\)、第三个元素在\([x, 1e18)\)范围内” 的数量。
      两者数量之和即为该查询的答案。

  3. 时间复杂度与效率预处理阶段:

    每个向量的辗转相除次数是 \(O(\log V)\)(V 是分量最大值),共 n 个向量,且排序的时间是 \(O(n \log V \log n)\)

    查询阶段:每个查询的辗转相除次数是 \(O(\log V)\),每次二分查找是 \(O(\log n)\),共 q 个查询,总时间是 \(O(q \log V \log n)\)

    整体复杂度 \(O((n + q) \log V \log n)\),能高效处理题目中的大规模数据。

综上,这段代码通过逆变换 + 辗转相除 + 二分查找的思路,将原问题转化为对 “变换中间状态” 的统计问题,实现了高效的查询。

http://www.hskmm.com/?act=detail&tid=37540

相关文章:

  • 【Go】go学习笔记
  • todolist
  • 利用排列组合法实现TOPN路径计算
  • 达梦数据库获取判断字段中的json数据中的值
  • 2025 废气处理/废气治理/环保/污水/分子筛/除臭设备推荐榜:上海深城以专利技术破局,3 家企业凭场景适配登榜,助力异味治理升级
  • Web3 行业 Solidity 高级后端开发工程师岗位要求
  • API 搜索的下一代形态-Apipost智能搜索:只需用业务语言描述需求,就能精准定位目标接口!
  • 2025包装机/全自动包装机/非标定制生产线厂家推荐昆仑智能装备,专业高效!
  • 2025拖鞋机/酒店拖鞋生产线厂家推荐昆仑智能,高效稳定自动化解决方案
  • 2025年口罩机厂家权威推荐榜单:全自动口罩机器,全自动KN95口罩机,高效智能生产线专业选购指南
  • 2025提升机/自动提升机厂家推荐垚林机械,高效稳定省心之选
  • 二分图
  • 2025不锈钢方形/消防/生活/保温水箱厂家推荐莞南节能,专业耐用品质保障
  • 2025-10-23 DeepSeek R1本地部署(ollama)
  • python 异步调用语法
  • KAPE 0.8.3.0发布:数字取证工具新版本详解
  • 第一!天翼云引领中国教育公有云市场
  • 哇哦杯题解民间版
  • 海上60公里,5G信号满格?这款神器让远航不再“失联”
  • 2025除尘设备/脉冲除尘器厂家推荐东莞市百谊环保科技,专业高效净化解决方案
  • 2025 年压滤机厂家最新推荐排行榜:隔膜 / 污泥 / 真空 / 板框 / 带式压滤机优质品牌权威指南
  • 2025发电机/发电机组/柴油发电机/甲醇发电机组租赁厂家推荐新疆泓浩机电,专业维修保养服务保障
  • 2025 年氮化硅陶瓷球生产厂家最新推荐榜:高精度高耐磨产品优选,国内优质企业全面剖析
  • 阿里云加持,《泡姆泡姆》让全球玩家畅享零延迟冒险
  • 基于粒子群优化(PSO)算法的PID控制器参数整定
  • VScodeC语言结构体成员提示不全
  • 2025滑石粉厂家推荐辽宁精华新材料,纳米级/工业级/化妆品级多品类覆盖
  • 上海结申管件制造有限公司:承插焊异径三通、承插焊Y型三通、高压承插管件、锻造承插三通源头厂家
  • 承插焊异径三通源头厂家推荐上海结申,专业制造高压承插管件
  • 【10.29 直播】IoTDB 图形化工具与编程框架集成实操