- 博客(103)
- 收藏
- 关注
RSS订阅原创 GJOI 5.15 题解
一排喷泉有n个喷头，初始时全部处于“开启”状态。每次操作可以改变连续k个喷头的状态（开启变关闭，关闭变开启）。经过若干次操作后，最多能形成多少种不同的喷泉状态？由于答案可能很大，请对1097取模。1≤k≤n≤105。
2025-05-17 11:40:08
907
原创 （dp、二维树状数组）洛谷 P3287 SCOI2014 方伯伯的玉米田 题解
株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高。这个条件是天然合法的，还有两维“偏序”，但是这里没法用 cdq，因为这里的权值是可变的；问能最多剩多少株玉米，来构成一排美丽的玉米。方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。，我们对于两个维度的限制扔上二维树状数组，查询最大值就好了。的玉米高度，每次我们要改变怎样的一段区间？
2025-05-17 07:41:00
614
原创 （思维题）洛谷 P8059 POI2003 Monkeys 题解
一棵树上有n只猴子。他们从1∼n编号。编号为1的猴子用它的尾巴盘住了一个树枝，剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子。每只猴子都可以用两只手去钩其他的猴子，每只手最多只能钩一只。从0时刻开始，每一秒都有一只猴子松开它的一只手。这也许会造成一些猴子掉落到地上，我们想要知道每只掉落地上的时间（猴子掉落的速度都非常的快，可以忽略掉落的时间）。
2025-05-13 10:53:31
909
原创 （线段树、二分答案）洛谷 P2824 HEOI2016/TJOI2016 排序 题解
年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。这样的排序和二分答案，为什么是可行的？排序是改变数的位置，如果按照原序列排序，其它数相对于。的大小也还是原来那样，只是相对位置改变了。用 01 序列排序，我们有两种思考：怎么排序更快？，而且查询操作只有一次。次 01 排序操作，最后线段树查询第。大的，否则就是小的，相对位置不变。的排列，现在对这个排列序列进行。这个难题是这样子的：给出一个。我们发现瓶颈在于排序的。则答案偏小，否则偏大。
2025-05-08 14:54:32
581
1
原创 GJOI 4.29 题解
小明管理着一个n个节点的网络，网络中的每个节点上有一台设备，每台设备初始状态均为“运行中”。小明每次操作可以改变相邻两台设备的状态（运行中变停机，停机变运行中）。他的目标是确保不存在两台相邻的设备同时处于“运行中”状态。请你帮助小明计算达到这一目标所需的最小操作次数。1≤n≤105。
2025-05-05 08:43:22
787
原创 二项式反演 系列 题解
有时候做一些计数题，会遇到“恰好满足……”类似的条件，往往无法正面击破。但是有可能我们掌握的现有的排列组合 trick 们，可以解决“至少……满足……”的条件，即。而这个既定事实可以实现二者方案数的转化。
2025-05-05 07:40:42
861
原创 GJOI 4.19题解
给定一棵n个点的树，给第i个点染上颜色ci，其中，ci为1n的一个整数。现在，对于每一种颜色k∈1n，你要求出有多少条简单路径满足路径上至少有一个点的颜色为k。1≤n≤2×105。
2025-05-03 10:45:15
613
原创 （计数）洛谷 P8386 PA2021 Od deski do deski/P10375 AHOI2024 计数 题解
根据上面的性质，我们可以知道一个可以被全部删除的序列长什么样子（下文称为合法的）：可以是首尾数字相同的序列。种数的一个，使之变成合法的序列（在这里要搞清楚这个定义，后面有一个状态转移和这个强相关才能理解）。每一位填数字，我们发现填的数字是什么其实并不重要，因为我们要求的是序列数目而不是具体的序列种类。那我们考虑维护合法的和不合法的状态（不合法状态可以转移到合法的）。个不合法的转移过去，为了使这个长度为。的不合法序列的有效颜色有多少呢？的序列不合法，我们也要添加。个不合法的序列的有效数有。
2025-04-29 21:42:32
718
原创 （最短路）洛谷 P6880 JOI2020 奥运公交 题解
不在某种最短路上，那么它翻不翻转没有影响，按普通情况计算即可。如果它翻转会对某种最短路产生影响，我们不妨把它标记为关键边，跑到关键边再跑 dijkstra 就能节省很多时间了。的，并且去掉优先队列的伪 dijkstra，而且 dijkstra 次数会巨多。因此我们想要尽量少的跑 dijkstra，那就不能修改后跑全图 dijkstra。已知起点的路径很好处理，要求已知终点的那就跑反图吧。假如暴力翻转每一条边然后跑 dijkstra，我们发现。我们回到答案的式子，我们发现需要的只有。边的有向图，每条边从。
2025-04-27 18:49:11
678
原创 （树形 dp）洛谷 P3177 HAOI2015 树上染色 题解
将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。对答案的贡献，那么我们就要计算，在当前状态下，有多少黑点之间路径与白点之间路径经过。反正染黑染白都能反过来，就不用设当前节点的颜色了：设。个点，将其染成黑色，并将其他的。倒序枚举以防影响后面的答案。，你要在这棵树中选择。个黑点的路径，对数有。个白点的路径，对数有。
2025-04-27 10:40:31
614
原创 （树状数组）洛谷 P6119/P3657 Why Did the Cow Cross the Road II G/P 题解
个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为。虽然很典型，但是还是思维有点混乱，这种节点贡献的题目还是要多练。个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有。时，这两个品种的奶牛能友好相处，否则不能友好相处。一条长长的道路贯穿整个农场，道路的左侧有。作为配对的结尾的最大匹配数，然后更新。表示，当前，右侧的种类。，那么就可以在左侧的。
2025-04-24 16:07:39
787
原创 （区间 dp）洛谷 P6879 JOI2020 Collecting Stamps 3 题解
但是这一题还有一个时间限制，要在特定的时间点之前（包括这个时间点）收集到特定的雕塑，不一定能将区间。秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。发现可以顺时针或逆时针走，即可以停在区间的左或者右去收集雕塑。的雕塑，收集完之后要停在左或右端点，可以收集到最大雕塑数量。因为在起点也可以顺时针和逆时针走，所以我们设破环成链之后的。个，收集完之后停在左或右端点，花费的最小时间。米，顺时针或者逆时针的移动都是允许的。个雕塑时），就得先从起点走过去包含了。的圆，从一个点出发，有。
2025-04-22 22:12:15
917
原创 （树上启发式合并）CF208E Blood Cousins/洛谷 P5384 雪松果树 题解
家庭关系保证是一棵森林，树中的每个人都至多有一个父母，且自己不会是自己的祖先。注意到这是森林，所以要在每一颗树跑树上启发式合并，维护子树内的深度桶即可。的子树内，有多少深度（相对于根节点）为。（可以用倍增预处理），题目转化为 在。本题解将按照 CF208F 的数据。有一个家族关系森林，描述了。）人的家庭关系，成员编号为。考虑使用树上启发式合并。第二题敬请自行修改。
2025-04-19 09:33:09
854
原创 树上启发式合并 系列 题解
树上启发式合并（dsu on tree）是一种巧妙的暴力。bigu让高度小的树成为高度较大的树的子树，这个优化就是启发式合并算法。根据重链划分的思想，如同树剖那般，时间复杂度是Θnlog2n的，具体证明见。在树上处理u子树内的信息（各种子树内的数组、答案变量等），修改永久/不永久贡献，可以直接遍历子树u（跳过bigu），也可以用 dfs 序遍历子树（我习惯用前者）。前文说，重儿子的贡献保留，其余的要清空，那么给一个keep标记看是否保留：如果是重儿子就k。
2025-04-18 16:21:40
1017
原创 （区间 dp）洛谷P4766 CERC2014 Outer space invaders/P5851 Greedy Pie Eater/AT_arc168_d Maximize Update 题解
来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。外星人遵循已知的攻击模式。有N个外星人进攻，第i个进攻的外星人会在时间ai出现，距离你的距离为di，它必须在时间bi前被消灭，否则被消灭的会是你。你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率R，它会瞬间摧毁与你的距离在R以内的所有外星人（可以等于），同时它也会消耗R单位的燃料电池。
2025-04-16 14:49:47
841
原创 二维数点 系列 题解
区间内有不同的数，那么多次出现的只算做一个。这题还是查询区间，那么能不能用二维数点来做呢？用线段树常数比较大，在洛谷 TLE 最后一个点，还是用树状数组吧，反正也比较方便。这两道题是比较经典的线段树区间 trick，希望自己可以在以后的比赛中手切。，令人畏惧（在古早时期学莫队的时候卡常过了），那么分块也并非正解了。同样使用前缀和思想，枚举右端点。出现，扔上树状数组会出问题，所以记得加。考虑枚举条件端点，从而改变权值。如果出现第二次，那么必然。那么题目就转化成了，求区间。，如果一个数在下标区间。
2025-04-13 18:37:38
934
原创 （区间 dp）洛谷 P1220 关路灯/P2466 Sue 的小球 题解
某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。
2025-04-11 18:44:32
1030
原创 区间 dp 系列 题解
能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。其实就是原字符串中，找其中两个合并成特定的一个字母，问最后能否变成只有一个字母。四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。中任意两个字母代替，使得自己的名字能够扩充得很长。这个游戏的目标是尽快的消灭一行中所有的宝石。的字母来覆盖（这变量够直观吧）。
2025-04-09 22:11:36
1211
原创 （区间 dp）洛谷 P4342 IOI1998 Polygon 题解
对数据，每队输入两个数据分别代表边的运算符和节点内的数字。计算最高可能的分数，并输出在第一步删除那一条边，可以得到这个最大的分数。如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。的情况的——即两段最小值是都是负数，但绝对值比较大，相乘就会很大。还有合并操作，那么我们可以再链上区间 dp，然后找出长度为。这样操作，游戏结束时，只有一个顶点，没有多余的边。但是我们发现，这题的值域去到了负数，在乘法是存在。个顶点的多边形上的游戏，如图所示，其中。
2025-04-09 18:30:59
802
原创 （区间 dp）洛谷 P4805 CCC2016 合并饭团 题解
隔离合并：若两个相等的数中间只隔了一个数，可以将这三个数合并为一个数，这个数的值为这三个数之和。的最大答案，我们发现这比较难维护：我们不知道这个区间最优地合并后，是合并成。相邻合并：将两个相邻且相等的数合并为一个数，这个数的值为这两个数之和。的数组进行若干次合并操作，求合并后的最大值。先减少枚举次数，在“隔离合并”中要枚举两个断点，目的是找出。个还是剩下了若干个，在后面难以取出来作其它的合并。）且相等，就可以合并了，时间复杂度。是否可以合并成一个饭团，也就是。相邻合并只需要枚举一个断点，
2025-04-08 11:04:24
944
原创 （欧拉回路）洛谷 P11762 走亲访友 题解
那现在只要输出方案就好了，跑欧拉回路就要把走过的边（包括图中的重边）给 ban 掉，以后不再经过这条边（而不是标记已经经过了的点，因为欧拉回路可以经过一个点很多次）。可以把已经走过的边套到未走过边的 head 上边（链式前向星建图的 head 数组），可以用引用符。条，然后借助加边跑欧拉回路——显然在两个节点之间顶多两条边，最劣就是全部跑完。朴素地，我们在无向图生成一棵树出来，跑到每棵树节点删非树边。可以证明在本题的限制条件下，一定存在合法的方案。特别的，一组边在被删除前可以经过多次。
2025-04-07 21:59:17
1052
原创 （并查集）洛谷 P2024 NOI2001 食物链 题解
句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。这样就很方便判断条件真假了。中的一种，但是我们并不知道它到底是哪一种。个动物，用上述两种说法，一句接一句地说出。那这就是一道有趣的题目了。不妨大胆想象，因为只有三类，形成。是同类的还有一组特殊的。那么在一句真话中，一个。动物王国中有三类动物。
2025-04-06 18:27:36
752
原创 （回滚莫队）洛谷 P7261 COCI 2009/2010 PATULJCI 题解
个小矮人在挖矿时，白雪公主在玩电脑，翻看图片，挑选漂亮的图片。图片中每个小矮人都有一顶彩色的帽子，有。如果一张照片上有一半以上的帽子是同一种颜色，那就是漂亮的。换句话说，如果图片上有。其他题解还有随机化 + upper_bound 的，比较厉害。不过这一题我打算用来复习回滚莫队。这一题如果用普通莫队，就是维护区间桶之后，枚举所有颜色，看看哪个颜色大于。个小矮人有相同颜色的帽子，那就是漂亮的图片。张图是否漂亮，如果漂亮，以什么颜色为主。区间查询个数，维护桶，还是莫队。个小矮人在森林里，当。
2025-04-01 10:53:00
742
原创 （莫队、值域分块）洛谷 P4867 Gty的妹子序列/P3730 曼哈顿交易 题解
给出一个有n个数的序列，对该序列有m个询问，对于每次询问，输出区间lr内,权值在区间ab中的权值的种类数。
2025-03-31 15:14:45
660
原创 （记搜轮廓线 dp、哈希）洛谷 P4363 九省联考 2018 一双木棋 题解
现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何？或者说对于这种问题，典型的，我们可以使用“轮廓线 dp”，因为在这题有明显的轮廓线特征。看看下棋规则：“一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子”。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的。列的格子上的两个整数记作。
2025-03-29 08:13:30
786
原创 （二维数点、线段树）SMOJ 团队/CF377D Developing Game 题解
这个题一眼就看出端点排序、分段贡献，但是考场就是调不出来，又是 WA 又是 RE 的。非常粗心，还需沉淀。
2025-03-28 10:56:22
869
原创 （分块思想、最短路）洛谷 P3645 雅加达的摩天楼
如此跳跃，不妨看作直线上的“最短路”，一只 doge 跳到另外一只 doge 的摩天楼后，“换乘”另一只 doge 继续跳，那就是 bfs 了。注意不能再原来的“直线”上直接建，不然本来这个地方没有 doge 在这里你又让他“换乘”。的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为。如果我们记录其它的 doge 的具体信息再建边，那和。比较小的话，那就要建非常多的边，这显然不是我们想要的。的出口单向边，这样就可以实现 doge 的“换乘了”。的双向边，就不从起点开始枚举了。
2025-03-27 15:48:17
934
原创 （分块）洛谷 P4168 蒲公英 题解
你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。暴力就是离散化之后搞一个桶记录出现次数，查询最大的编号，时间复杂度。这种区间统计的题目，可能一大段区间要被一个一个地遍历很多次，所以可以考虑用。在乡下的小路旁种着许多蒲公英，我们把所有的蒲公英看成一个长度为。查询就是同块直接遍历加桶，不同块就统计两边，也就。内的数据（以离散化后的数据为准，上界为。，那么我们就想查询的时候，计算完。最终的询问区间为计算后的。为一个正整数，表示第。棵蒲公英的种类编号。
2025-03-21 10:37:15
1024
原创 （分块思维）洛谷 P4109 HEOI2015 定价 题解
组测试数据，如果荒谬度最低的价格不唯一，输出最小的那个。倍数，相同的还有末端的，以防还有荒谬度更小的。现在，你要出售一样闲置物品，你能接受的定价在。范围内，你想要给出一个荒谬度最低的价格。数量较少的数，也就是可以钦定一个数。中可以跳过很多数，从而计算是。，我们来个口胡的推导：里面只能。的倍数的数（跳过的肯定没有。因为外层还有个数据组数。是较优的，实测能过。
2025-03-20 15:16:46
621
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人