- 博客(1789)
- 收藏
- 关注
RSS订阅
原创 ICPC2023深圳部分题解（A,D,E,F,G,K,L）
好像还没上gym所以放不了题目链接，深圳这场的题目我觉得都很好所以写个题解。会做的都写上来了，场上很多题是队友写的，只是有参与讨论所以知道做法的题。
2023-11-19 13:25:47
498
原创 2022-2023 ICPC Brazil Subregional Programming Contest(B,D,F,I,L,N)
暴力枚举那个不确定的字母，然后压缩成long long用map存一下，遍历一遍就可以得到答案了。个点的一棵树，每个点有个颜色，求经过每一条边的，且首尾是相同颜色的路径数量。直接暴力枚举头选多少张尾选多少张，然后用线段树维护一下反面的数字，每次取前。，然后每次除以2再给最高位配一个数，所以求每个。张牌排成一排，有正面反面的数值，选择首尾加起来。一下更新答案，否则就暴力给每个点对的链加值。的小写字母字符串，其中都有一个字母不确定。张取反面的数值，求最大数值和。三个堆的取石子游戏，第。，求先手必胜的概率。
2023-07-04 02:04:10
630
1
原创 SEERC2022(E,F,H,K)
考虑一种类似插入排序的方法，我们每次把塔顶前面按顺序的全丢到第三个塔，然后把第一个塔剩下的第一个丢到第二个塔，然后再把第三个塔的一个一个丢回第一个塔，第二个塔上的在合适的顺序插入这个过程。因为这样原本的配对是不合法的，所以新的配对肯定是合法的，然后这种隔空配对是可以几个连一起互换的，贡献相同。排序然后相邻的配对，如果有的配对不符合限制我们就需要置换一下，找到相邻的一个进行如下配对。然后给出初始时第一个塔上盘的顺序，要求构造一种在最终第三个塔排好序的方案，次数不超过。，是否有往后拉的线。
2023-06-25 20:32:50
834
原创 CF1773J-King‘s Puzzle【构造】
我们尝试手玩一下，因为要联通我们直接先拉一条链，此时的度数是。的点，然后让第二个点对其他所有点连边，那么此时链上的度数就为。的情况，理论上如果这种情况可行，且存在度数为。个点，把剩下的点连在度数最大的点上。的点，那么我们可以考虑先构造。的子问题，重复上述过程就好了。的点，也就是变成了一个。非常好构造，爱来自复建人。然后我们保留一个度数为。
2023-06-23 21:09:03
426
原创 hdu7207-Find different【burnside引理】
引理，我们要找所有置换的不动点数量和。个环，对于每个环来说总共加了。，求有多少个不同的序列。种，假设一种为循环位移了。来说合法的条件当且仅当。步，且所有数字加上了。，从一个数开始一直加。，最终又走回了起点。...
2022-08-14 10:41:09
208
原创 uoj#751-[UNR #6]神隐【交互】
个点的树，你每次可以选择一个边集，交互库会返回你所有联通块，要求这棵树。次询问中是一个单独的连通块，然后我们每次暴力找出叶子删掉即可。至于一个叶子的父节点是谁，我们在一个连通块删除的只剩下一个点。的子树中，此时取出还没有父节点的点，它们的父节点设为。的儿子，那么在过这个连通块的节点肯定都在。，我们可以给所有边一个独特的编号。这样对于一个叶子来说它就恰好在。一个神奇的做法，设操作次数为。位二进制数且其中恰好有。...
2022-08-12 13:36:53
225
原创 CF1710B-Rain【堆】
所以我们可以把这些函数分开来，然后按照截距从大到小用堆维护，每次取出最上面会不合法的就行了。我们把分段点提出来离散，这样每一段之间都是一个一次函数了，最值肯定在分段点上。一个操作可以相当于一个分成五段的分段函数，每一段是一个一次函数。然后我们记录一下目前正在产生贡献的一次函数，斜率只有。对于每个操作，求删除这个操作后能否使得最终所有的。一个数轴，每个位置上开始时都有一个。...
2022-08-12 13:24:50
230
原创 CF1710C-XOR Triangle【dp】
所以我们考虑减去不合法的状态，也就是。作为边长时能构成一个非退化三角形。，我们对于每一位来说，每次暴力枚举。，那么一个合法的状态有。也就是对于每一位来说。
2022-08-12 12:47:55
197
原创 Loj#3320-「CCO 2020」旅行商问题
说是找一条路径，实际上我们是能够找到一个颜色交替只有一次的环的，然后交替位置就在。求从这个点出发的一条尽量短的经过所有点的路径。，并且两条路径上颜色都相同，一条红色一条蓝色。，每一条边是红色或者蓝色，对于每个点。我们构造一下，此时有两条不相交的路径。的路径是红色，此时对于一个未加入的点。之间的路径颜色，假设是红色，那么如图。显然地猜测一下最短的长度肯定是。是蓝色那么直接加长路径即可。如果是蓝色同理弹另一边。......
2022-08-11 18:52:21
276
原创 loj#2788-「CEOI2015 Day1」管道【树上差分】
但是我们不能离线建生成树，因为我们存不下所有的边，考虑一下别的方向的优化。我们会发现对于非树边来说，如果这一条非树边能被其他非树边完全覆盖，那么说明这条边就没有用，所以我们对于非树边来说也只需要保留一棵最小生成树即可。一个朴素的想法是我们搞出一棵生成树来，然后对于非树边。路径上的边都标记成非割边，然后剩下的就是割边了。然后至于标记方面用树上差分来处理就好了。条边的一张图，求它的所有割边。我们存不下所有的边，但是。...
2022-08-11 18:38:53
213
原创 CF1427F-Boring Card Game【贪心】
我们考虑一下能不能求出哪些牌是在一次中取走的，这个取法很像一个括号匹配，也就是一次取走的东西中不会产生交叉，而如果不会产生交叉，那么我们按照括号匹配的找法去找也是对的。所以我们可以用一个栈存按顺序存牌，当栈顶三个颜色相同时就弹出这三个，表示这三个是在同一次中取走的。的根并且存在一个当前要取的颜色的叶子。我们找一下这个森林的性质，会发现每个节点的颜色都和父节点的不同，还有。的序列，两个人轮流操作，每次取走连续的三个数字。，那么此时取走随便一个不是最后一个根的。多，所以显然不合法，假设不成立。...
2022-08-10 21:04:08
231
原创 CF1286E-Fedya the Potter Strikes Back【KMP,RMQ】
我们在每次加入字符后考虑所有后缀的贡献，然后考虑加入一个字符后后缀产生贡献的变化。也就是一次操作最多增加一个会产生后缀的贡献，我们取考虑怎么维护其他以前的后缀。现在第二个问题是我们怎么知道每次要删除的后缀是哪些。除了这些以外还有如果。的都修改掉即可，这样势能分析一下就知道是对的。，然后我们就可以一直往上走找到要删除的后缀了。序列加入一个数字，然后求这个串的贡献。的后缀有多少个，然后每次暴力把大于。树，那么原本产生贡献的后缀肯定都在。点到根节点的路径上，我们维护一个。维护一下后缀的贡献即可。...
2022-08-10 20:37:34
266
原创 CF1534F2-Falling Sand (Hard Version)
手动刷新的肯定都是每一列位置最高的沙子，然后刷新关系可以表示成一张有向图，而且是平面图，那么就说明一个沙子被刷新的条件是手动刷新了某个区间中位置最高的沙子。条边，然后对于每个沙子要求区间的左端点我们从左往右从最高的沙子开始跑，然后每次走到的点标记删除，右区间就变成从右往左跑。个网格，有的网格上有沙子，一个沙子被刷新后会下落到底并且刷新沿途中四周四连通的沙子，你可以选择一些沙子手动刷新。个沙子下落，求至少手动刷新多少个沙子。我们考虑求出这些区间，先建边，这样最多。得到这些区间后我们转换成若干个形如区间。...
2022-08-10 20:01:42
175
原创 uoj#750-[UNR #6]小火车【二分,折半,鸽笼原理】
但是我们知道一定有解，这个条件肯定是有用的，我们考虑二分一下这个和。每次分割成左右两个区间。如果左边或者右边有重复的就直接结束先，这样我们就能保证左右没有重复了，此时我们需要找到。然后考虑怎么求这个解，看到这个范围我们考虑一下折半，我们搜出左右两边数字和的集合。有不超过这么多个数，所以肯定有重复的一个位置，所以肯定有解。即可，如果有一边是空的也行，这样另一边直接合法。，因为两个集合的都很大，这个看起来很不可做。那么答案肯定在左区间，否则在右区间。的和也相等，此时我们一边选。中找两个数字和相同的集合。...
2022-08-10 19:50:24
213
原创 UOJ#749-[UNR #6]稳健型选手【贪心,分治,主席树】
题目链接:https://uoj.ac/problem/749如果有序列aaa，你每次取走一个数字后然后这个序列最前面的数字会被别人取走，直到序列为空。此时f(a)f(a)f(a)表示你最大能取走的权值和。给出一个长度为nnn的序列aaa，qqq次询问区间[l,r][l,r][l,r]，求f(al∼r)f(a_{l\sim r})f(al∼r)。1≤n,q≤2×105,1≤ai≤1091\leq n,q\leq 2\times 10^5,1\leq a_i\leq 10^91≤n,q≤2×105,1≤ai
2022-08-08 21:56:28
194
原创 UOJ#748-[UNR #6]机器人表演【dp】
串是否合法，而且我们最好能搞出一种记录信息最少且唯一的方法。这种匹配方法一定是最优的，因为往前跳一到的位置一定是一个。时，如果恰好能和下一个匹配，我们就匹配。前面，求最终能得到多少种本质不同的串。表示当前匹配到的位置，当我们加入一个。如果没有我们就一直让匹配位置。往前走，直到出现一个未匹配的。时前面填的方案数转移即可。表示目前有多少个未匹配的。，我们可以先预处理出一个。往前跳到出现第一个未匹配。，而之后我们拿未匹配的。，如果前面有未匹配的。...
2022-08-08 11:07:35
236
原创 AT2382-[AGC015D]A or...or B Problem
中选取一个或多个数，将它们按位或后能得到多少种不同的结果。都删除，因为它们之间的数都有这些。中，而且它们怎么或都不能超过。的最高位就不同了，我们找到。，所以这部分的答案就是。，此时我们就有两个部分。然后让这部分的数或上。...
2022-08-06 15:32:04
161
原创 P8352-[SDOI/SXOI2022]小N的独立集【dp套dp】
也没有用，因为我们可以显然父节点不选择更优。这个范围，这样我们的状态数就只剩下。种状态，不能拿来dp套dp维护。求令这棵树的最大独立集权值为。选/不选时的子树最大权值和。给出一棵树，每个点的权值是。考虑我们求最大独立集时的。继续挖掘一下性质，若。...
2022-08-06 15:08:47
181
原创 AT2366-[AGC012F]Prefix Median【dp】
不过这第二个条件依旧不好处理，我们考虑倒着做，那当我们确定一个。此时还没有加入，我们只需要限制往内跨的情况出现就好了。中的前驱，如果都大于则取后继，如果一大一小则不动。加入数字之后的排名只能变动一位，这是充要的。，那么我们将其视为同一个，右边同理。中所有数字都不同，我们去考虑一下。基于这个限制我们得到的条件是每次。，你可以将其重新排列，定义。之间的数字就都不能选择了。询问有多少种不同的可能的。考虑去形式化这个条件，将。这样我们其实并不需要考虑。一次向外跨过了很多个。，那么我们可以视这些。...
2022-08-04 19:50:53
132
原创 pjudge#21651-[PR #4]猜猜看【交互】
首先我们发现在询问中位数的情况下我们是完全不能够区分。我们能得到两次，如果有一个只得到了一次，那么说明。那么我们假设我们现在已经得到了两个数字。此时如果我们在询问中得到了两个。次，每次会重新处理一个数字，也就是。肯定是用于区分这两个东西上的。，也就是在边界附近的两格。被得到了两次），那么我们令。，此时我们通过询问中位数。再进一步，如果我们不知道。而如果我们已经确定了一个。的排列，每次你可以询问。操作内得到这个排列。，此时肯定也有前一个。，然后再重新处理一次。不难发现这样最多扩展。...
2022-08-03 11:35:50
149
原创 AT2377-[AGC014E]Blue and Red Tree【启发式合并】
所以这个时候我们直接选择这条路径补上这条边一定是对的，因为如果被其他的补上了就不合法，而它也只会补上这条边。合并，我们用set来记录每个点连出去的边，合并的时候就启发式合并就好了。此时我们的方案就唯一了，实现的时候我们可以每次找到一条两棵树上都有的边。树上的边开始时都是蓝色的，我们每次选择一条蓝色边路径。要求最后所有都是红色边的情况下能不能变成。，然后删掉路径上一条边，连接一条。的路径上只剩下一条边没有补上。考虑反过来，所以开始时视。开始考虑，对于每一条。它合法的时机当且仅当。...
2022-08-03 11:10:40
125
原创 pjudge#21652-[PR #4]到底有没有九【数位dp】
首先是从高位到低位逐步确定答案，但是直接暴力算乘法肯定很麻烦，我们考虑反过来做。那么现在问题就是给定一些确定的位，求剩下的位有多少种不含。段数不会太多，我们可以暴力枚举。位分割一次提出来求和，如果是。的倍数，然后数位dp求解。的倍数的条件就是将它每。...
2022-07-15 19:16:06
234
原创 AT5147-[AGC036D]Negative Cycle【dp,模型转换】
这个容易负环让人一头雾水不知道怎么维护，我们知道差分约束有解的条件就是没有负环，所以我们可以考虑转成差分约束模型。，要求代价最小的情况下使得图中不存在负环。的限制，我们考虑维护差分数组（反过来的）然后仔细观察这个限制会发现其实只有相邻的。，那么条件就是区间和不能大于/小于。，也就是整个序列单调不升。那么对于不能删除的边。...
2022-07-15 19:04:03
190
原创 Loj#2324-「清华集训 2017」小 Y 和二叉树
的右子树，所以我们优先比对两个连接的部分作为子树时字典序最小的第一个数是啥。个（每条边的两个方向），我们可以先预处理出每个子树字典序最小时第一个是啥。你要求它的一个二叉树结构（根任意选择）使得其中序遍历的字典序最小。的左子树肯定没有节点，然后考虑它连接的点安排到右子树或者父节点。至于被丢到子树里面的，我们上面的预处理可以确定子树里面的顺序。直接找根感觉比较麻烦，我们考虑先确定中序遍历中的第一个点。，整张图可能出现的子树（不同的根）数量为。个点的一棵树，每个点的度数不超过。的时候，记它连接的节点是。...
2022-07-15 18:48:45
230
原创 Loj#510-「LibreOJ NOI Round #1」北校门外的回忆【线段树】
题目链接:https://loj.ac/p/510给出一个代码其中lowbit(x)\text{lowbit(x)}lowbit(x)表示xxx在KKK进制下最低非零位的值。现在给出n,q,Kn,q,Kn,q,K，qqq次调用add(x,v)add(x,v)add(x,v)或者query(x)query(x)query(x)。要求输出每次query(x)query(x)query(x)调用的值。1≤n≤109,2≤q,K≤2×1051\leq n\leq 10^9,2\leq q,K\leq 2\time
2022-07-14 11:50:47
195
原创 Loj#576-「LibreOJ NOI Round #2」签到游戏【线段树】
题目链接:https://loj.ac/p/576给出一个长度为nnn的序列aaa，还有一个未知序列bbb，你每次可以花费gcdi=lrai\gcd_{i=l}^r a_igcdi=lrai的代价得到∑i=lrbi\sum_{i=l}^rb_i∑i=lrbi的值。每次修改aaa中的一个数，求得到bbb中所有数字需要花费的最小权值。1≤n,q≤105,1≤ai≤1091\leq n,q\leq 10^5,1\leq a_i\leq 10^91≤n,q≤105,1≤ai≤109因为有一个信息上的问题
2022-07-14 11:23:39
641
原创 CF516D-Drazil and Morning Exercise【树上差分,倍增】
题目链接:https://www.luogu.com.cn/problem/CF516D给出一棵nnn个点的树，定义f(x)f(x)f(x)表示距离点xxx最远的点的距离，qqq次询问给出一个kkk，要求一个最大的连通块满足连通块中所有点的f(x)f(x)f(x)最大最小差值不能超过kkk。1≤n≤105,1≤q≤501\leq n\leq 10^5,1\leq q\leq 501≤n≤105,1≤q≤50我们找到f(x)f(x)f(x)最小的点作为根，那么肯定有每一个点的f(x)f(x)f(x)都不小于其
2022-07-12 12:15:56
137
原创 CF1140G-Double Tree【最短路,矩阵乘法,树上倍增】
题目链接:https://www.luogu.com.cn/problem/CF1140G给出一个nnn个点的树TTT，然后复制一份T′T'T′，每个TTT中的点iii向T′T'T′中的点iii都有连边构成一张图。图上所有权值各不相同，现在qqq次询问图上两点的最短路。1≤n≤3×105,1≤q≤6×1051\leq n\leq 3\times 10^5,1\leq q\leq 6\times 10^51≤n≤3×105,1≤q≤6×105因为树上两点简单路径唯一，所以xxx到yyy之间的最短路肯定是包括两
2022-07-12 11:56:27
158
原创 P5208-[WC2019] I 君的商店【交互,二分】
题目链接:https://www.luogu.com.cn/problem/P5208有一个长度为nnn的010101序列aaa，你知道里面有奇数个111还是偶数个111。你每次可以选择两个下标集合S/TS/TS/T询问集合SSS和集合TTT位置的数字和哪个更大。交互库只会告诉你S≤TS\leq TS≤T或者S≥TS\geq TS≥T。要求在所有询问集合大小之和不超过 500100500100500100 的情况下得到整个aaa序列。1≤n≤1051\leq n\leq 10^51≤n≤105注意到数据中有
2022-07-11 20:13:33
142
原创 P7740-[NOI2021]机器人游戏【dp,bitset】
题目链接:https://www.luogu.com.cn/problem/P7740题目大意摸了小 R 有 mmm（1≤m≤10001 \le m \le 10001≤m≤1000）个机器人和 mmm 张纸带，第 iii（1≤i≤m1 \le i \le m1≤i≤m）个机器人负责对第 iii 张纸带进行操作。对于每张纸带，它们都被从左到右分成了 nnn（1≤n≤321 \le n \le 321≤n≤32）个格子，依次编号为 0,1,…,n−10, 1, \ldots , n - 10,1,…,n−1。
2022-07-11 18:39:44
327
原创 P4769-[NOI2018]冒泡排序【组合数学,树状数组】
题目链接:https://www.luogu.com.cn/problem/P4769有一个冒泡排序的算法然后给出一个排列aaa，求在所有字典序大于aaa的排列ppp中冒泡排序交换次数恰好为∑i=1n∣i−pi∣\sum_{i=1}^n|i-p_i|∑i=1n∣i−pi∣的排列数。1≤n≤6×105,∑n≤2×1061\leq n\leq 6\times 10^5,\sum n\leq 2\times 10^61≤n≤6×105,∑n≤2×106打一下表发现合法的排列条件是最长下降子序列不超过222。
2022-06-28 17:13:33
159
原创 P6776-[NOI2020]超现实树
题目链接:https://www.luogu.com.cn/problem/P6776定义一次操作为将一棵树的叶子换成另一棵树。定义一棵树TTT的grow(T)grow(T)grow(T)表示所有树TTT能够通过操作变成的树的集合。现在给出mmm棵树TiT_iTi，定义SSS为所有grow(Ti)grow(T_i)grow(Ti)的交集。求SSS是否几乎完备（指仅有有限棵树不在集合SSS内）。1≤∑n,∑m≤2×106,T≤1001\leq \sum n,\sum m\leq 2\times 10^6
2022-06-28 16:43:35
202
原创 P2483-[模板]k短路/[SDOI2010]魔法猪学院【主席树,堆】
题目链接:https://www.luogu.com.cn/problem/P2483给出一个nnn个点mmm条边的一张带权有向图，求一个最大的kkk使得1∼n1\sim n1∼n的前kkk短路径长度和不超过EEE。2≤n≤5000,1≤m≤2×105,1≤E≤1072\leq n\leq 5000,1\leq m\leq 2\times 10^5,1\leq E\leq 10^72≤n≤5000,1≤m≤2×105,1≤E≤107我们先把从nnn出发的一棵反向最短路树跑出来，注意这里的最短路树是真的一棵树
2022-06-25 21:16:45
201
原创 CF566E-Restoring Map【bitset】
题目链接:https://www.luogu.com.cn/problem/CF566E有一棵树，但是你不知道它的形态。你现在只知道距离每个点距离不超过222的点集，但是你不知道每个点集是对应哪个点的。现在要你求这棵树。2≤n≤10002\leq n\leq 10002≤n≤1000考虑这样一种情况那么???和?′?'?′的交集恰好是xxx和yyy，也就是所有非叶子的连边我们都可以用以上方式确定。然后考虑怎么确定叶子的连边，对于叶子xxx来说，包含它的集合中最小的那个肯定是它自己的集合。这样我们就可以确
2022-06-23 11:11:10
138
原创 P6698-[BalticOI 2020 Day2]病毒【AC自动机,dp,SPFA】
题目链接:https://www.luogu.com.cn/problem/P6698有一个包含0∼G−10\sim G-10∼G−1的字符集，其中有nnn种变换，能够将一个字符ai(ai>1)a_i(a_i>1)ai(ai>1)变为一串字符bib_ibi，当一个字符串中只剩下000和111时变换就结束了。然后给出mmm个匹配串cic_ici。现在对于每个字符i∈[2,G−1]i\in[2,G-1]i∈[2,G−1]，是否字符iii无论变化结束时都含有至少一个匹配串，如果不是，求一个最短的不包含任何
2022-06-23 09:22:26
186
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人