6.1 ~ 6.30 做题总结
stripe_python · · 个人记录
有题解的题挂链接,没题解的题简要说明思路。过水的题不记录。
难度评价系统来自 https://www.luogu.com.cn/article/u98dxgp0。贺个图:
【2-】P14012 [POCamp 2023] 枫树 / Maple Tree
题解:https://www.luogu.com.cn/article/e200mkjv。
【1+】P3488 [POI 2009] LYZ-Ice Skates
题解:https://www.luogu.com.cn/article/ijtsm6q9。
【1+】ARC163C Harmonic Mean
题解:https://www.luogu.com.cn/article/6t2xyx39。
【2】P7840 「C.E.L.U-03」重构
题解:https://www.luogu.com.cn/article/sp98gzmn。
【3】CF1091E New Year and the Acquaintance Estimation
题解:https://www.luogu.com.cn/article/szfu472f 里面有。
【0】AGC006A Prefix and Suffix
找后缀 = 前缀的最长字符串即可。
【1】AGC006B Median Pyramid Easy
考虑令
【2】AGC006C Rabbit Exercise
对于一个点
写成期望递推的形式,记
整理一下就是
记
【2】AGC006D Median Pyramid Hard
考虑二分答案
形如 00 或 11 且离中心线最近的块就是第一行的元素,根据这个就可以 check 了。
【3】P2148 [SDOI2009] E&D
记两堆石子
【2】CF138D World of Darkraft
坐标系旋转
【1】CF317D Game with Powers
每个集合独立,且集合大小
【3】CF1442F Differentiating Games
考虑 DAG 上的情形,必须 SG 两两不同才能区分,则构造完全 DAG 转化为 nim 游戏。
在完全 DAG 下挂若干点,结合策略窃取论证,可以用三种结果区分目标点在 DAG 下节点所挂集合的所属情况。
贪心找点然后调整即可,可以说明次数是对的。
【2】P13356 [GDCPC 2024] 图
题解:https://www.luogu.com.cn/article/q8p78mga。
【2】AT_utpc2020_j Merge and Decrement
题解:https://www.luogu.com.cn/article/rgl351av。
【2】P12703 [KOI 2022 Round 2] 外环路
三度化后点 / 边分治更新最短路。
【4】AT_utpc2022_e Parallel Swapping
【1+】CF1217D Coloring Edges
使用拓扑排序判环,显然无环时
如果有环,我们断言
【1】CF1438D Powerful Ksenia
注意到操作一定不会改变整体异或和。于是求出
我们尝试给出奇数情况的构造。注意到若
考虑增量维护前缀异或和。令
对于
操作次数
【1+】P9820 [ICPC 2020 Shanghai R] Mine Sweeper II
注意到将地图取反后空地价值和不变。证明考虑每一对八连通格子,取反以后贡献不变。
考虑将
【3】QOJ1429 Hit
首先将区间端点离散化,将值域映射到
考虑二分答案
这是一个差分约束的形式。考虑如下建图:
建超级源点
考察这个差分约束图的形态,以第一组样例为例:
我们注意到,负环只可能由向左的
我们使用朴素贪心,在每个线段都至少包含一个点的约束下最小化点数,并求出一条线段所包含点数的最大值
设贪心得到的点为
根据负环的定义,得到
至于之后咋做,我还不会。
【2】LOJ6267 生成随机数
题解:https://www.luogu.com.cn/article/xg2oodr3。
【4】QOJ7977 彩虹航线
【3】QOJ18404 Dangerous Data
题解:https://www.luogu.com.cn/article/i8embwqy。
【3】QOJ17760 Telepathy
题解:https://www.luogu.com.cn/article/r6ln11nt。
【1】AT_wtf22_day1_a Save the Monsters
题解:https://www.luogu.com.cn/article/52ank0ac。
【2】QOJ141 8 染色
A 和 B 先不断删去度数
记
如果每个颜色占 3bit,总的 bit 数就是
我们注意到
可以证明,每一组在
注意精细实现,否则会被卡常卡空间。submission。
【2】P13011 【MX-X13-T6】「KDOI-12」能做到的也只不过是静等缘分耗尽的那一天。
题解:https://www.luogu.com.cn/article/yumpahmx。
【2】P8394 [BalticOI 2022] Boarding Passes (Day2)
【4】P8124 [BalticOI 2021] From Hacks to Snitches (Day1)
【2】CF1292E Rin and The Unknown Flower
【1+】P16536 [THUPC 2026 决赛] 流光解密
题解:https://www.luogu.com.cn/article/23lwa3rh。
【2】ARC148D mod M Game
站在 B 的角度思考问题。考虑将数两两配对为
另一种情况时,当
这是 B 获胜的充分条件,我们猜测这是必要的。
问题转化为判定是否存在合法匹配。做法就是统计
【3】P10004 [集训队互测 2023] Permutation Counting 2
题解:https://www.luogu.com.cn/article/44ak4e9i。
【3】LOJ566 「LibreOJ Round #10」yanQval 的生成树
【4】P10611 故事结局
【2】CF1311E Construct the Binary Tree
【0】ARC222A Colorful Intervals
幽默题,卡了我 10min。
答案有一个显然的下界,即所有区间长度的
断言下界可以取到。构造式证明是
【1+】ARC222B Circular RPS
枚举三种手势赢了
这是一个线性规划,直接解或者放到三维空间中都是容易的。一车 corner case。
【1】ARC222C 2 Directions vs 4 Directions
最优解一定形如:一条从上到下的路径,两行之间
前后缀 DP 合并即可。
【2】P12204 [COI 2022] 委员选举 / Povierenstvo
题解:https://www.luogu.com.cn/article/enhtc5t4。
【2】CF1061F Lost Root
题解:https://www.luogu.com.cn/article/9swhotpl。
【2】CF618F Double Knapsack
题解:https://www.luogu.com.cn/article/6yo7njlc。
【1】CF1498E Two Houses
幽默交互题 0 次询问。
给了入度,求出所有 SCC,然后随便做。
【1】CF1779E Anya's Simultaneous Exhibition
首先,要找的点集即为竞赛图缩点后链头 SCC 的点集。
直接问到每个点的出度,然后就能得到入度,用入度就能求所有 SCC。
【3】P3561 [POI 2017] Turysta
题解:https://www.luogu.com.cn/article/akorqiuf。
【3】P11164 [BalkanOI 2023] Permutations
题解:https://www.luogu.com.cn/article/somcbl4c。
【3】P14002 [eJOI 2025] Navigation
题解:https://www.luogu.com.cn/article/kauev85l。
【4】P14463 【MX-S10-T4】『FeOI-4』呼吸之野
【1+】P9000 [CEOI 2022] Measures
题解:https://www.luogu.com.cn/article/ezxm938f。
【4】ABC249Ex Dye Color
【3】P12636 [UOI 2020] Array Reduction
【2】ABC267G Increasing K Times
题解:https://www.luogu.com.cn/article/2kc5wkre。
【3】QOJ17160 Multiset Variance
题解:https://www.luogu.com.cn/article/mjw9rzg8。
【2】P7962 [NOIP2021] 方差
题解:https://www.luogu.com.cn/article/d670r3be。
【1】QOJ12212 Best Subsequence
题解:https://www.luogu.com.cn/article/urnr9tmc。
【1+】P14068 [PO Final 2022] 搭塔 / Legobyggartävlingen
题解:https://www.luogu.com.cn/article/5y6jl6xd。
【1+】P13649 [NOISG 2016] Panda Ski
题解:https://www.luogu.com.cn/article/dqptl5be。
【3】P12508 [ROI 2025 Day2] 程序员的日常
【4】QOJ6509 Not Another Range Query Problem
【2】P11647 【MX-X8-T6】「TAOI-3」俄罗斯蓝猫
题解:https://www.luogu.com.cn/article/2evhhjtz。
【3】QOJ11544 Colored Blocks
题解:https://www.luogu.com.cn/article/jspdsxil。
【2】ARC076F Exhausted?
题解:https://www.luogu.com.cn/article/ls0gn0br。
【4】CF1408H Rainbow Triples
【1+】CF1437E Make It Increasing
题解:https://www.luogu.com.cn/article/trgnp8hb。
【1+】P14394 [JOISC 2016] 俄罗斯套娃 / Matryoshka
首先用 Dilworth 定理对偶成最长反链,发现是最长非严格下降子序列长度。
按
【3】P1861 星之器
题解:https://www.luogu.com.cn/article/dgzqyy7m。
【1】CF1110E Magic Stones
题解:https://www.luogu.com.cn/article/2i28wba9。
【1】P6976 [NEERC 2015] Distance on Triangulation
平面图,多次询问最短路,允许离线,套路地考虑分治。做法是每次找到分治中心,从分治中心向两侧跑最短路,更新跨过中线的所有询问,并将中线同侧的询问递归处理。网格图分治、Halin 图分治。
对于本题,由于边权均为
类似边分治,我们枚举当前连通块的所有边,并计算删去这条边后,形成的最大连通块的大小,然后取最大连通块最小的边为中心。
视
【2】P8392 [BalticOI 2022] Uplifting Excursion (Day1)
题解:https://www.luogu.com.cn/article/z7xcvlwl。
【3】P15653 [省选联考 2026] 星图 / starmap
题解:https://www.luogu.com.cn/article/l5o0n321。
【1+】ABC304Ex Constrained Topological Sort
题解:https://www.luogu.com.cn/article/ik9jkjta。
【1+】ARC145D Non Arithmetic Progression Set
题解:https://www.luogu.com.cn/article/k32za18a。
【2】P9499 「RiOI-2」change
题解:https://www.luogu.com.cn/article/paa60yzi。
【2】P8494 [IOI 2022] 最罕见的昆虫
题解:https://www.luogu.com.cn/article/vpl09tti。