能力提升综合题单Part10 杂项

题单介绍

## Part 10 杂项 > 这里的专题,有很多都难以纳入前面的类别中,故将他们单独列入了杂项。 ### Part 10.1 模拟退火 > 模拟退火是一种随机化算法。当一个问题的方案数量极大(甚至是无穷的)而且不是一个单峰函数时,我们常使用模拟退火求解。 - [P1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337) - [P2503 [HAOI2006]均分数据](https://www.luogu.com.cn/problem/P2503) - [P3878 [TJOI2010]分金币](https://www.luogu.com.cn/problem/P3878) ### Part 10.2 0/1 分数规划 > 0/1 分数规划用来求一个分式的极值。 - [P4377 [USACO18OPEN]Talent Show](https://www.luogu.com.cn/problem/P4377) - [P3199 [HNOI2009]最小圈](https://www.luogu.com.cn/problem/P3199) - [P3288 [SCOI2014]方伯伯运椰子](https://www.luogu.com.cn/problem/P3288) - [P3705 [SDOI2017]新生舞会](https://www.luogu.com.cn/problem/P3705) - [P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322) ### Part 10.3 离线算法 > 当题目不要求强制在线时,我们可以一次性读入所有询问来处理。 #### Part 10.3.1 CDQ 分治 > CDQ 分治是一个基于分治思想的离线算法。 - [P3810 【模板】三维偏序(陌上花开)](https://www.luogu.com.cn/problem/P3810) - [P3157 [CQOI2011]动态逆序对](https://www.luogu.com.cn/problem/P3157) - [P2487 [SDOI2011]拦截导弹](https://www.luogu.com.cn/problem/P2487) - [P4690 [Ynoi2016]镜中的昆虫](https://www.luogu.com.cn/problem/P4690) - [P3206 [HNOI2010]城市建设](https://www.luogu.com.cn/problem/P3206) #### Part 10.3.2 整体二分 > 整体二分,顾名思义就是把多个查询一起二分解决。 - [P1527 [国家集训队]矩阵乘法](https://www.luogu.com.cn/problem/P1527) - [P2617 Dynamic Rankings](https://www.luogu.com.cn/problem/P2617) - [P3527 [POI2011]MET-Meteors](https://www.luogu.com.cn/problem/P3527) - [P4602 [CTSC2018]混合果汁](https://www.luogu.com.cn/problem/P4602) #### Part 10.3.3 莫队 > 莫队算法可以解决不少离线区间询问问题。 - [P1494 [国家集训队]小Z的袜子 /【模板】莫队](https://www.luogu.com.cn/problem/P1494) - [P1903 [国家集训队]数颜色 / 维护队列 /【模板】带修莫队](https://www.luogu.com.cn/problem/P1903) - [P5906 【模板】回滚莫队](https://www.luogu.com.cn/problem/P5906) - [P4887 【模板】莫队二次离线(第十四分块(前体))](https://www.luogu.com.cn/problem/P4887) - [P2709 小B的询问](https://www.luogu.com.cn/problem/P2709) - [P3674 小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674) - [P3709 大爷的字符串题](https://www.luogu.com.cn/problem/P3709) - [P4074 [WC2013]糖果公园](https://www.luogu.com.cn/problem/P4074) - [P5501 [LnOI2019]来者不拒,去者不追](https://www.luogu.com.cn/problem/P5501) ### Part 10.4 奇怪的题目 > OI 界中有一些非常规套路的题目,这里放出来分享。 - [P4920 [WC2015]未来程序](https://www.luogu.com.cn/problem/P4920) - [P5042 [国家集训队]丢失的题面(ydc的题面)](https://www.luogu.com.cn/problem/P5042) - [P5285 [十二省联考2019]骗分过样例](https://www.luogu.com.cn/problem/P5285) - [P5246 [集训队互测2016]消失的源代码](https://www.luogu.com.cn/problem/P5246) ### Part 10.5 非传统题 > 在 NOI 等比赛中,非传统题正越来越频繁出现。 > > 非传统题主要包括以下几类:提交答案题,交互题,通信题。 #### Part 10.5.1 提交答案题 > 给你一些输入,你只需要提交这些输入对应的答案,即为提交答案题。 - [P1335 [NOI2013]小Q的修炼](https://www.luogu.com.cn/problem/P1335) - [P1737 [NOI2016]旷野大计算](https://www.luogu.com.cn/problem/P1737) - [P3614 yyy棋 II](https://www.luogu.com.cn/problem/P3614) - [P3640 [APIO2013]出题人](https://www.luogu.com.cn/problem/P3640) - [P3782 [WC2017]排序](https://www.luogu.com.cn/problem/P3782) - [P3836 Nowruz](https://www.luogu.com.cn/problem/P3836) - [P4920 [WC2015]未来程序](https://www.luogu.com.cn/problem/P4920) - [P5402 [CTS2019]无处安放](https://www.luogu.com.cn/problem/P5402) - [P5418 [CTSC2016]NOIP十合一](https://www.luogu.com.cn/problem/P5418) - [P5600 【XR-4】尺规作图](https://www.luogu.com.cn/problem/P5600) #### Part 10.5.2 交互题 > 在交互题中,选手程序需要通过与测评程序交互来完成任务。 - [P1733 猜数(IO交互版)](https://www.luogu.com.cn/problem/P1733) - [P1947 猜数](https://www.luogu.com.cn/problem/P1947) - [P5208 [WC2019]I 君的商店](https://www.luogu.com.cn/problem/P5208) - [P5473 [NOI2019]I 君的探险](https://www.luogu.com.cn/problem/P5473) - [P6541 [WC2018]即时战略](https://www.luogu.com.cn/problem/P6541) - [P3777 [APIO2017]考拉的游戏](https://www.luogu.com.cn/problem/P3777)

题目列表

  • [JSOI2004] 平衡点 / 吊打XXX
  • [HAOI2006] 均分数据
  • [TJOI2010] 分金币
  • [USACO18OPEN] Talent Show G
  • [HNOI2009] 最小圈
  • [SCOI2014] 方伯伯运椰子
  • [SDOI2017] 新生舞会
  • [JSOI2016] 最佳团体
  • 【模板】三维偏序(陌上花开)
  • [CQOI2011] 动态逆序对
  • [SDOI2011] 拦截导弹
  • [Ynoi2016] 镜中的昆虫
  • [HNOI2010] 城市建设
  • [国家集训队] 矩阵乘法
  • Dynamic Rankings
  • [POI2011] MET-Meteors
  • [CTSC2018] 混合果汁
  • [国家集训队] 小 Z 的袜子
  • [国家集训队] 数颜色 / 维护队列
  • 【模板】回滚莫队&不删除莫队
  • 【模板】莫队二次离线(第十四分块(前体))
  • 小B的询问
  • 小清新人渣的本愿
  • 大爷的字符串题
  • [WC2013] 糖果公园
  • [LnOI2019] 来者不拒,去者不追
  • [WC2015] 未来程序
  • [国家集训队] 丢失的题面(ydc的题面)
  • [十二省联考 2019] 骗分过样例
  • [集训队互测 2016] 消失的源代码
  • [NOI2013] 小 Q 的修炼
  • [NOI2016] 旷野大计算
  • yyy棋 II
  • [APIO2013] 出题人
  • [WC2017] 排序
  • [IOI2017] Nowruz
  • [CTS2019] 无处安放
  • [CTSC2016] NOIP十合一(数据疑似有误)
  • 【XR-4】尺规作图
  • 猜数(IO交互版)
  • 猜数
  • [WC2019] I 君的商店
  • [NOI2019] I 君的探险
  • [WC2018] 即时战略
  • [APIO2017] 考拉的游戏