THOUGHTS ON A TOPIC
# solution.
在这个话题下，收集了 78 篇记录。
CF1666K Kingdom Partition 题解
一个极度对称优美的做法。 首先观察 ABC，发现 A 和 B 同构，所以尝试把 C 放在中间去考虑。令 xu 表示 u 的选择，列出对于 u xleftrightarrow{w} v 一条边，所有 x…
P7156 [USACO20DEC] Cowmistry P 题解
给一个代码好写的做法。 首先假设建了完整的 Trie 树，那么三个不同的点 u,v,w 在 Trie 树上的虚树一定是 5 个点（包含叶子节点和 LCA）。我们钦定 v,w 的 LCA 是 x，x 和…
P3590 [POI 2015 R2] 三座塔 Three towers 题解
感觉区间两个端点都很不靠边的时候很不优，打个表看看是否有满足 l,r 合法，并且 l,r 周围都有还有 3 个没选的字符，并且没有比 l,r 更大的合法区间： 只输出了 0 0 1 也就是单字符，不会…
AT_agc020_d [AGC020D] Min Max Repetition 题解
记 S^k 表示把字符串 S 重复 k 次。 首先通过贪心填找一下限制，设 X 为出现次数最多的元素，那么一定是按照 (X^{k-1}Y)^?(X^kY)^?X^k 这样填，那么 k 就是答案，容易发…
P14311 【MX-S8-T4】平衡三元组 题解
出题人题解，欢迎观看视频题解，打不开的把链接 首先转化条件为 2Byleq Bx+Bz。 那么就是在区间 l,r 内找三个下标 lleq x<y<zleq r,2Ayleq Ax+Az，最大化 Ax+…
P14310 【MX-S8-T3】图排列 题解
出题人题解，欢迎观看视频题解，打不开的把链接 提示1：W{i,3}=3,W{i,4}=4,W{i,5}=5 怎么做？也就是相当于排列长度为 2。 发现可以生成的集合要么是 {[1,2]} 要么是 {[…
P14309 【MX-S8-T2】配对 题解
出题人题解，欢迎观看视频题解，打不开的把链接 先把树变成有根树之后，考虑从下往上考虑，容易发现对于一个节点 u，其子树最多剩余一个点会继续向上匹配，因为如果有多点没匹配，都会在 u 尽量匹配。 那么 …
AT_agc034_f [AGC034F] RNG and XOR 题解
约定下文中： - P,F,G,H 均表示集合幂级数。 - P 集合是每一项是概率。 - 集合幂级数乘法是异或卷积。 - S1oplus S2 表示集合对称差，也就是异或。 如果 P^{prime}{e…
P8499 [NOI2022] 挑战 NPC Ⅱ 题解
我们令 f(u,v) 表示，G 的 u 子树是否能和 H 的 v 子树匹配上。求解 f(u,v) 相当于一个二分图匹配的过程，对于 xin sonu,yin sonv，如果 f(x,y)=1，则有一条…
SCCPC2025 E - Competition Graph 竞赛图 单log题解
题目传送门 0x00 引理 引理 1 对竞赛图缩点后形成的 DAG 形如一条链。 证明：归纳法证明。 - 基例：对于 n = 1 或 2 阶竞赛图，结论显然成立（缩点后为单点或一条有向边）。 - 归纳…
CF2101D Mani and Segments 题解
这是一篇 mathcal{O}(n) 题解，代码巨简洁。 首先考虑这个限制条件意味着什么，发现当且仅当，区间 LIS 序列和 LDS 序列并为整个区间，交为一个点，形如一个叉叉的样子。枚举交的这个点 …
P6597 烯烃计数 题解
0x00 有机物 不会化学？没关系你只需要知道： 1. 键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。 2. 碳原…
P6598 烷烃计数 题解
0x00 有机物 不会化学？没关系哦你只需要知道： 1. 键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。 2. 碳…
AT_abc390_f [ABC390F] Double Sum 3 点边容斥做法 题解
首先我们了解一下点边容斥，目标是数一个树上的联通块个数，我们知道一棵树有 n 个点，那么就有 n-1 条边，所以只需要数所有的点个数减去所有的边个数就行。 那么这道题实际上是一条链数联通块，那么同样这…
P5108 仰望半月的夜空 使用 Lyndon 分解做到严格 O(n)
本做法参考了 5ksynccloser 的文章 如何用 Lyndon 薄纱 SA 首先有使用 SA 的做法，但是基于比较的排序的复杂度下限就是 mathcal{O}(nlog n)，但是 SA 无论怎…
P4727 [HNOI2009] 图的同构计数 和 P4128 [SHOI2006] 有色图 题解
0x00 Burnside's lemma 这里需要一点群论的知识，设 G 是一个置换群群，将作用在集合 X 上，有以下结论： - 其中 X/G 表示集合 X 在群 G 作用下的本质不同元素集合，那么…
P5282 【模板】快速阶乘算法 题解
改了一下第一篇题解的做法，不知道能不能在投一次题解。 发现首先根据 Wilson 定理： 于是可以选择 n 和 p-n-1 中较小者来算，这样已经卡掉一半常数了。 然后第一篇题解实际上跑了三秒多，于是…
AT_nikkei2019_qual_f Jewels 题解
设 Ax 表示容量 x 时的答案，分类讨论一下可以发现，从 Ax 转移到 A{x+1}，最多会增加 4 个，减少 3 个。所以合并两个背包 A,B 到 B，若 Ci 的最优转移点是 Aj+B{i-j}…
CF1396C Monster Invaders 题解
首先需要正确理解题面： 1. 手枪、激光枪、AWP 分别有 r1,r2,r3 的冷却时间，但是这个冷却实际上是蓄力前摇，不能同时冷却。 2. 这些枪都不不能打其他关卡的怪。 首先分析下三个武器： 1.…
CF850F Rainbow Balls 题解
题意 有一袋 n 个颜色球，第 i 个颜色的球有 ai 个。 当袋子里至少有两个不同颜色的球时，执行以下步骤： 1. 一个接一个的按照顺序随机取出两个的球，这些球的颜色可能是一样的。 2. 把第二个球…
CF838C Future Failure 题解
题意 两人轮流操作一个长度为 n 的由字母表中前 k 个字符组成的字符串。每次将字符串重新排列或删去一个字符，并不能和之前的字符串相同。不能操作者失败。 问有多少种字符串可以使得先手必胜，对质数 p …
P4727 [HNOI2009] 图的同构计数 和 P4128 [SHOI2006] 有色图 题解
0x00 Burnside's lemma 这里需要一点群论的知识，设 G 是一个置换群群，将作用在集合 X 上，有以下结论： - 其中 X/G 表示集合 X 在群 G 作用下的本质不同元素集合，那么…
P7862 [COCI2015-2016#2] DRŽAVA 题解
题意 给定一个 n 个点的平面图，每个点有个权值，现在选出一个点集使得其某一个非空子集的权值之和是 K 的倍数，最小化使点集联通所需的最长边。 nleq 5times 10^4,Kleq 30 题解 …
AT_arc072_c [ARC072E] Alice in linear land 题解
题意 有一个数轴，终点为原点。一个机器人位于 D，有 n 条指令，对第 i 条指令机器人会向终点移动 di 距离，若移动后距离变大则不移动，意思是可能冲过，但是若距离变小就可以过去。 给出 m 个询问…
CF645G Armistice Area Apportionment 题解
题意 给定平面上 n 个点和 a。设 P(a,0),Q(-a,0)。要求找出一条直线 l 过至少两个给定点，最小化 max{ PX-QX},Xin l。 nle10^5,ale 10^4。 题解 计算…
AT_abc313_g [ABC313G] Redistribution of Piles 题解
题意 你有从 1 到 N 编号的 N 盘石子，第 i 盘石子的个数为 ai，同时你还有一个空背包。 你可以进行以下操作任意次： 1. 从有一个以上石头的盘子里各拿一个石头。取下的石头移动到背包里。 2…
CF273E Dima and Game 题解
大家都是打表做的，但是没人说怎么打表。 首先肯定是要算出 sg 值的，然后发现 sg 值只和 r-l 有关，令 x=r-l 则两种操作分别是把 x 变成 lfloorfrac{x}{3}rfloor,…
CF113D Museum 题解
题意 给一个无向图，两个人从两个点出发，对于每个人，每个时刻若在 i 点，则有 pi 的概率留在这个点；否则随机等概率选出边到下一个点。若两人相遇则停止，问在每个点相遇概率 nleq 22 题解 根据…
P5940 [POI1997] 跳 题解
前言 挺有意思的题，记录一下。 正文 分析题目 简化一下题意，有一个无限长的的数组，从负无穷到正无穷，然后初始这个数组上一些点有一些数，现在可以使用两种操作让这个数组任意两个相邻的数的和不超过一，首选…
AT_abc299_h [ABC299Ex] Dice Sum Infinity 题解
题意 高桥有一个小于 10^9 的正整数 R 和一个初始是 0 的数 X，每次等概率加 1 到 6。直到当前 X-R 为 10^9 的倍数时停止，求期望次数。 题解 分析 题意就是从 0 开始随机游走…
AT_agc050_d [AGC050D] Shopping 题解
题意 有 n 个人，m 个物品，初始在一个队列里面排好，然后玩一个游戏： 1. 取出对头的人，这一回合这个人玩。 2. 这个人从自己在之前的回合中没选到过的物品中等概率选择一个物品。 1. 若这个物品…
AT_abc242_h [ABC242Ex] Random Painting 题解
发现对于某一种情况的操作，操作次数取决于最后一个被染色的方块，根据套路考虑 min-max 容斥，记随机变量 ti 表示抽到第 i 张卡的时间。 然后考虑如何计算 minleft(Sright)，那么…
CF1761D Carry Bit 题解
首先很显然有一个 mathcal{O}left(nkright) 的朴素 DP 做法，具体地设 dp{i,j,0/1} 表示当前考虑了前 i 位，进位了 j 次，并且 i 位上是否向 i+1 进位的方…
P5493 质数前缀统计 题解
前言 借此篇题解记录一下 Min25 筛中的预处理所有 Sleft(leftlfloor frac{n}{i}rightrfloorright) 方法。 记号与约定 在本文中若无特殊说明，记号均采用以…
CF1918E 有个人交互题输出不换行
前言 有个人交互题输出不换行，到比赛结束都没调过。 正文 0x00 分析题目 根据这个题奇怪的交互方式，可以发现我们并没有办法直接获得每个数的具体数值，但是可以获得某个数和其他数的偏序关系。由于要找出…
AT_abc337_f ABC337F] Usual Color Ball Problems
前言 F 居然比 G 难，考场上做完 F 就没时间了，亏大了。但是这场 0 伤通过 A 到 F 还是挺开心的。 正文 0x00 分析题目 一个基础的观察是，一个盒子里面只有一种颜色的球。继续观察发现这…
CF1925D Good Trip 题解
前言 估值要掉没了，快来写题解。 正文 0x00 分析题目 发现这题需要计算期望，不妨先把期望转化为求所有情况的贡献和，最后除一个情况数即可。首先可以发现贡献相对独立，不同的两对朋友之间的贡献互不影响…
P5295 [北京省选集训2019] 图的难题 题解
前言 退火过的，要学正解的请跳过这篇。UOJ 上面的数据本做法还没卡过去，UOJ 数据太强了。 正文 0x00 分析题目 首先需要一个结论，对于一个图能成功染色的充分必要条件是，对于其每个诱导子图 l…
P9982 [USACO23DEC] Haybale Distribution G 题解
题意： 给定一条数轴上面有 n 个点，分别在 xi 的位置。定义数轴上两个点 x,y（这里是坐标，不是下标）之间运输成本 W{x,y} 为。 其中 a,b 为给定常数。现在有 q 次询问每次询问给定一…
P9981 [USACO23DEC] Minimum Longest Trip G 题解
题意： 给定 n 个点 m 条边的的带边权 DAG，问原图从每个点出发的最长路径上，由边权依次组成的字符串字典序最小的路径，求出这个路径长度和边权和。注意路径长度是不带权路径，即只计算路径条数。 nl…
P9980 [USACO23DEC] Flight Routes G 题解
题意： 给定一个 n 个点的 DAG，并且有向边一定从编号小的点连向编号大的点，现在给出了两两间路径条数的奇偶性，问原图有多少条连边，可以证明答案唯一确定。 nleq 750 首先你需要知道如何求解这…
P9979 [USACO23DEC] Target Practice S 题解
题意： 给一个数轴，上面有 n 个目标分别在 posi 的位置，然后有一个人首先站在原点，会依次执行 m 个操作，每个操作可能是 1. 向左移动 1 单位。 2. 向右移动 1 单位。 3. 开火，若…
P9978 [USACO23DEC] Cycle Correspondence S 题解
题意： 给定一个有且仅有一个 k 元环 n 个点的无向图，然后给这个图每个点标了两次号，分别是 ai,bi 保证 ai,bi 各自形成一个排列。然后依次按照某个顺序（顺时针或者逆时针）给出了这个环上没…
P9977 [USACO23DEC] Bovine Acrobatics S 题解
题意： 给你 n 种牛，每种牛有 ai 个，同种牛的重量都相同为 wi，现在牛要叠牛塔，每座牛塔都是由若干个牛叠成，并且要求相邻两头牛在上面和下面的重量分别为 a,b，要求满足 aleq b+k 其中…
P9976 [USACO23DEC] Farmer John Actually Farms B 题解
题意： 有 n 株植物，初始高度为 hi，并且每天长 ai。现在给了一些限制，问存不存在一天使得满足每个限制，给出最小解，其中每个限制是要第 i 株植物比其他 ti 株植物高。 n,mleq 2cdo…
USACODEC B&S&G Translation & Solutions
Bronze Problem 1. Candy Cane Feast 题意： 给定 n 头和 m 个糖果，每头牛有个身高 hi，每个糖果有个长度 ci。这 m 个糖果依次被吃，吃第 i 个糖果时，这个…
P8264 [Ynoi Easy Round 2020] TEST_100 题解
前言 来个无脑分块做法，不需要并查集。 正文 首先有一个结论，观察到绝对值函数 faleft(xright)=leftx-aright 关于 x=a 这条直线对称，并且题目要求对这样的函数进行复合得到…
CF1902F Trees and XOR Queries Again 题解
前言 本题是简单的、一眼的、普通的、显然的。 正文 0x00 分析题目 给定一颗带点权无根树，每次询问给定两个点 u,v 和参数 k，回答是否有一个 uleftarrow v 简单路径的点权子集其异或…
P9466 [EGOI2023] Bikes vs Cars / 骑车与汽车 题解
前言 今天模拟赛 C 题题解啊，但是这个题确实惊艳到我了。 正文 0x00 题目分析 简化题面： 给定一个 nleq 500 个点的完全图，每条边有两个权值 B,C 满足 B+C=W，请你求出一个与其…
P9755 [CSP-S 2023] 种树 卡常题解
前言 赛时没过，赛后乱糊！这个做法本来过了洛谷数据的，但是 CCF 数据太强了，竟然只有 40pts？？？ 而且这个做法有点卡常，需要修改一下，还是能跑过。 正文 0x00 分析题目 第一眼看着这个题…
CF1009E Intercity Travelling 题解
前言 这种推式子的题只给结论？有没有素质 正文 题目分析 由于一号点出发相当于一号点必须休息，那么只剩下了 n-1 个点，总的选择方案是 2{n-1}，而题目要求答案乘上 2{n-1} 相当于消掉了，…
AT_abc321_g [ABC321G] Electric Circuit 题解
前言 没怎么写过概率、期望的题，做不了一点。并且感觉其他题解写的有点简略了，有点看不懂，结合自己的理解记录一下。 正文 0x00 题目分析 简述一下题意：给定一个 2m+n 个点的无向图，其中有 m …
[ABC322G] Two Kinds of Base 题解
前言 没人写题解，研究了好久，来总结一下。正巧还没做过这种套路。 正文 0x00 题目分析 转化一下题目变成，给定了 N,x 两个正整数，定义一个函数 Fleft(a,b,Sright)，有： 其中 …
[ABC321F] #(subset sum = K) with Add and Erase 题解
前言 现场发明了个“可撤销背包”记录一下。 正文 0x00 题目分析 实现一个维护一个可重集，每次可能加入或删除一个元素，求当前有多少子集元素和为 k，无非就是一个 01 背包带了一个删除嘛。这里需要…
CF1852C Ina of the Mountain 题解
前言 一个有意思的贪心，但是很少有题解证明了正确性，至少我看着有点迷迷糊糊的，总结一下。 正文 0x00 题目分析 转化一下题目就是给定一个序列 a，可以进行若干次操作每次操作选择一个区间使得这个区间…
P7913 [CSP-S 2021] 廊桥分配 题解
前言 喵喵题+1 正文 0x00 题目分析 发现题目难点在于需要分出两个不同的区域，而且有数量限制固定，十分恼火。那么考虑简化问题变成：只有一类飞机飞来，靠在廊桥的机位有 k 个，求出靠在廊桥的飞机数…
P7077 [CSP-S2020] 函数调用 题解
前言 感觉挺妙喵喵的，写个题解总结一下。 正文 0x00 题目分析 看见这个题可以发现主要难点在于：加法操作和乘法操作混杂进行。那么这种情况混杂的难题一般想先分解这个题，变成几个简单的小部分。根据这个…
[ABC320F] Fuel Round Trip 题解
前言 纪念一下第一次做出 AT 评分 2000 的题，还有名字水色。 正文 0x00 题目分析 题意很简单就是要在从 0 位置走到 XN 位置，然后倒回来回到 0 位置。并且每走一格需要 1 的油，油…
CF1819B The Butcher 题解
前言 感觉大家写麻烦了，提供一种更为简单的方法。 正文 0x00 题目分析 正向思考，去拼凑出一个矩形显然很困难麻烦，不好做。不妨考虑反向思考，观察这个过程，若第一刀竖着切，那么舍去那一片必然是有最长…
AT_abc318_e [ABC318E] Sandwiches 提供一种神经病做法 - 竞赛图三元环技术
前言 我去，以为多难呢，搞了个三元环出来，结果根本不用。但是这样优势就是代码好写。 正文 0x00 分析题目 看到三元组的条件，首先想到可以建图跑一个三元环计数。那么考虑怎么建立图论模型。 由于 Ai…
CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
前言 感觉大家分类讨论了好多无用的东西，其实可以更简化。 正文 0x00 分析题目 首先可以发现 kleq3，那么自然想到去看看每一个 k 对应的情况： 1. k=1 自然每次答案为 1，期望为 1。…
P9584 城市 题解
前言 感觉一些题解写的太麻烦了，这里提供一种更加简洁的做法。并且阅读本文请准备好草稿纸，树画出来一面大脑内存不够。 一些约定： 1. 本文拟定 1 号节点为根。 2. sizeu 表示以 u 节点为子…
CF1208F Bits And Pieces 题解
前言 如果你还不会 SOSDP，其实也没关系，这道题可以使用更简单的方法完成。 正文 0x00 题目分析 首先肯定考虑从高位开始贪心，而且这样的贪心是显然正确的。并且这样的操作具有二进制集合性质，可以…
CF1270I Xor on Figures 题解
前言 第一次做这种重定义矩阵+求逆题记录一下，感觉这个题好多人类智慧。 正文 0x00 题目分析 观察题目中的操作可得几个性质。 1. 首先一对 left(p,qright) 至多操作一次，否则操作次…
AT_abc315_d [ABC315D] Magical Cookies 题解
前言 这个题是我第一次在比赛上切这么高评分的题，感觉不难但是似乎很多人现场没切出来。 正文 0x00 题目分析 下文默认行和列为 n m,并且同阶。 这道题简洁明了啊，假如直接按照题意模拟。分析时间复…
P3349 [ZJOI2016] 小星星 题解 - 容斥学习
前言 之前从来没学习过容斥模型，这次这个题作为我的第一个容斥例题学习。 正文 0x00 问题分析 这个问题可以抽象为：给定一个图 G 和一棵树 Tree 要求对于树重新编号，编号是一个 n 的排列，假…
Baekjoon-8049 The Labyrinth of Wells 题解
前言 这个题好冷门，不知道某某 OI 知名教练怎么找出来的。 正文 0x00 题目分析 题面有点绕(没某某 OI 知名教练，出的模拟赛改版题面绕)。但是分析一下就是，抽象为：一个 DAG 每个点有一个…
CF449B Jzzhu and Cities 题解
前言 为什么大家写的这么麻烦。。。 正文 0x00 问题分析 要删去尽量多的边就要保留最少的边，那么要尽量少使用特殊边去松弛最短路。这里分类讨论一下： 1. 当前用于尝试松弛的边是特殊边 - disu…
CF677D Vanya and Treasure题解
前言 题解区有一些题解做法大体上每问题但是具体细节处理不到位，实际上时间复杂度并不能保证，所以这里提供一个更为清晰的题解。 正文 0x00 分析问题 由于题目的约束，在这个最短路中肯定经过了 1,2,…
CW集训0717题解
T1 LOJ 6039. 「雅礼集训 2017 Day5」珠宝 首先可知本题是一个背包问题，正常情况下是 NP 的。但是任然有依赖值域的做法 mathcal{O}left(nWright) 这样的时间…
SP4195 MSE08H - GCD Determinant
已知 Smith Determinants 结论有： 此结论参见此处论文。更加详细的讲解推荐 FFjet 博客 GCD 矩阵知多少 AC CODE
CF226E Noble Knight's Path 题解
前言 这道题思维难度其实不难，难度在代码实现的方式。而我在这提供一个需要费点脑子但是好写一些的实现方式。这样做可以节约很多比赛时间，毕竟比赛做题用时越少越好。 正文 0x01 问题分析 根据题面，得出…
P8964 梦幻 | Reopening of Dream 题解
我的理解就是：对于每一个人有一个“//freopen( 开头，以 ); 结尾”就是见祖宗人；每一个都完全一样就是正常的；剩下的都是乐子人。代码很好写 cpp include<cstdio includ…
P8965 坠梦 | Falling into Dream 题解
0x00 mathcal{O}(n^3) 预处理 mathcal{O}(n) 查询 这种大量查询的题目很容易想到的是预处理出来每一对 operatorname{dis}(x, y) 。这样在查询的时候…
P8894 「UOI-R1」求和 题解
sumlimits{s1={p1}}^{q1}sumlimits{s2={p2}}^{q2}sumlimits{s3={p3}}^{q3} cdotssumlimits{sn={pn}}^{qn}ma…
P4247 [清华集训2012]序列操作 题解
P4247 [清华集训2012]序列操作 题解 首先这道题从各个方面都知道是线段树。 0x00 记号与约定 所有的运算符号如 + 、 =+ 、 == 等，与c++意义相同。 oplus 表示异或运算。…