训练记录

发表于 2025-10-21 更新于 2025-10-30 分类于 2025

训练记录

25.10.7比赛总结

T1

20min写了个二分答案发现假了，又花20min写了个新的。

给你一个长度为的序列，问你所有长度为的子段的的最小值。

题解里面是的，但是我大暴力直接过了。

用树状数组维护数字是否存在，如果说滑动窗口里有这个数字就是，否则就是，这个每次是可以维护的。（这里要加上一个数因为无法被树状数组维护）

对于每一个滑动窗口二分如果说树状数组中前缀和是区间长度的话前前面就不可取，否则往前走就行了。

每次二分是的（为值域），总复杂度就是的，能过。

不足就是没有完全验证解法的正确性，以后还是要三思而后行。

T2

赛时5min打了全暴力，不懂为什么和别人的暴力得分不一样。

给你一个数，让你找出字典序最小的有序整数对，满足且。

咋是暴力啊。

根据区间长度进行大分讨。

长度为只能是原数。
长度为的话最小公倍数应该是。
长度为或更大的话直接预处理出来然后直接计算就做完了。

不足就是暴力没有优化，下次记得剪枝（流泪）

T3

根本不会，输出赛后测是三分。

让你选出一个图的子图，使得有一个点的度数小于，并最大化点的个数。

不会做了。

25.10.8比赛总结

T1

赛时想到了的做法，预计能得分，但是由于评测机问题值得了分，用时一小时。

题意是有个工人，一个工人在单位时间中能做个零件，最多招个工人，总时间是几个工人中的最大值，问你做个零件至少需要多少时间。

可以二分所需的时间，每个工人能做多少零件是确定的，我们挑最大的个加起来判断就行了。朴素找最大应该是的，不能过，但是这里有一个函数叫 nth_element，可以返回数组的第大，但是实际上它会将数组的前大都放在前面，时间复杂度单次，可以接受。

感觉没什么不足啊，已经尽力了，这种特殊功能真没有接触过，还是对 STL 的理解不过深入。

T2

赛时 AC，感觉比 T1 简单，用时一个半小时。

一棵树，点可以是黑色，白色，和无色，要求是黑点和白点不能在同一条边上，两个颜色都要有，而且涂色点的数量尽可能多。换句话说，能涂色的点一定要涂。

问你涂色方案数。

因为涂色点的数量尽可能多，显然是个点，一个点无色作为分隔，剩下的涂什么都可以。

对于每个点，假设它的度是，那么它是无色的方案数即为，最后累加就行了。

不足就是思考不够深入，没有从原题的条件进行进一步推导，然后很久才出结论。

T3

赛时用十分钟打了暴力得了三十分。

题意简单是有几段单调递增的序列形成一个环，问你长度为的子段最大和是多少。

取得的元素可以分为整段和零段，只考虑整段的话，零段往左取最好，因为左边递减，一定更优，也就是说，右端点一定是一个整段的结尾，然后可以二分左端点，二分出来直接计算就做完了。

思考不够深入，要是瞪不出来结论直接猜也有可能是对的，所以以后像这种结论题一定好好猜一猜才行。

T4

完全不会。

题意读不懂，暴力也没打。

T5

赛时打了个暴力算错复杂度结果炸了没得分。

题意是一棵树删掉一条边两边的颜色数量之和。

赛后有了一种与题解不同的做法。

考虑将颜色段维护到 DFS 序上，因为删掉一条边之后树变成了一个子树和剩下的，在 DFS 序上就是一个连续的区间和和左边一段和右面一段，开两倍空间就是一个连续段。这样只需要维护区间颜色树就行了，这里有几种可能的方法：

ODT
树状数组（离线）
莫队（离线）
主席树
分块

这里我挑了最好写而且时间复杂度低的树状数组，因为只有次询问，所以离线下来是可行的。

这里失误了，没有估算时间复杂度（但是我赛后算的是可以的，不得不说评测机真慢）。

25.10.12比赛总结

T1

赛时

因为读错题浪费了十几分钟。然后重新看发现读错题了很好想，五分钟写了一下就交了。

预估：

实际：

题意

给你一个数，两个人轮流将这个数变成这个数除本身和之外的一个因数，最后无法操作的人获胜。

思路

获胜的方式显然是拿到了或者质数。根据定义，只可能先手第一个拿到，所以说可以考虑除以外质因数因数的个数（相同的质因数按个数统计）。

因数为时是质数，先手必胜。
因数为时先手必须拿走一个，后手只剩一个，后手必胜。
因数比大的时候先手可以一次拿到只剩两个质因数，这时后手的情况和上一种先手的情况是一样的，翻转过来就是先手必胜。、

T2

赛时

观察到了很经典的结论，发现复杂度是对的，花十几分钟写了一下就做完了。

预估：

实际：

题意

构造一个数列，长度为 ,满足，并且至少存在个，使得。

问的是方案数对取模。

思路

题目中很大完全是诈骗，因为最多只会存在个满足条件。而且根据这个数列的大小约束，从一个余数变到另一个余数有且仅有一种方案。

所以可以枚举的数量，剩下的都填，所以说答案就是：

T3

赛时

看了一眼想到了暴力，但是发现不好写，而且复杂度拿不到分，所以说就想输出无解试一下。

预估：

实际：

~~考虑到上次梦熊比赛没有无解的数据我就没敢多估。~~

题意

给一个无向连通图，要求从到的最短路不能超过，从到的最短路不能超过，并最大化删边的数量。

思路

赛时以为有权值被吓哭了，没有权值好简单。

首先用 BFS 跑出全源最短路来，然后就可以判无解。因为要删掉的边最多，所以两个路径一定有公共部分，枚举中间的公共部分，然后答案直接算。

有两个小细节，一个就是提前考虑不公共直接减去，还有就是两条路径的方向可能是相反的。

T4

赛时

想到了时间复杂度分析中一个很常见的式子，发现在这里能用，写了一百多行的屎山，调了二十多分钟就交了。

预估：

实际：

题意

数列初始全为，是到的一个排列，实现两种操作：

1 l r 将全部加。
2 l r 查询的值。

思路

首先有一个非常常见的结论：

也就是说我们的答案最多执行这些次加一。

我们用线段树维护出一个区间最多还要加几次才能让区间和加上，对于每次加一，如果说这个值等于就直接递归下去修改，否则直接存在懒标记里面，查询和普通的线段树一样做就行了。

根据上面的结论，复杂度最多是的，能过。

T5

赛时

打暴力挺简单的，花了我十五分钟。

预估：

实际：

题意

一个图有一些边，每条边有一个概率出现，求最小生成树的期望。

思路

我不会。讲一下暴力。

就是枚举哪些边会被加进去然后计算最小生成树统计就行了。

25.10.19比赛总结

T1

赛时

写了个暴力找了找规律，找到规律之后写了个带的做法，后面发现可以优化，很好改，耗时两个小时。

估分：

实际：

题意

一个数列，让你求出所有长度为的子段中最大值中的最小值。

思路

一个数是这个区间的最大值当且仅当左右都没有比他大的。

对于每个数，单调栈维护出左右比他大的第一个数，就得到了这个东西对答案做出的贡献。

我们只考虑最大长度下他的答案。

因为答案一定是单调不降的，最后取后缀最小值就行了。

代码很好写。

T2

赛时

想到了一个 Trie 的做法发现假完了，所以写了个暴力，耗时半小时。

估分：

实际：

题意

一个图，能到仅当有连边或，问你从开始的单源最短路径。

思路

首先要知道按位与这种东西是可以传递的。

可以考虑建第二个图，将一个权值能到达的另一个权值都连上权值为的边，因为这个东西具有传递性，所以连边可以只连二进制下只有一位只差的权值，以减少连边的数量。

然后将点的编号与权值连上权为的边，反向连的是权值为的边。

考虑到权值只有和可以双向 BFS 求最短路。

T3

赛时

发现暴力都不会打，很难写，所以不可以总司令。

预估：

实际：

题意

一个数列，其中出现次，问你有哪些排列方式满足可以划分为不超过个单调递增的子段，对于每一个分别求解。

思路

~~先口胡一下。~~

补完了，不是口胡了。

令表示前小个数构成至少个段的方案数，显然一组数放在段后是不会增加段数的，可以去枚举增加的段数去计算这样的排列方式。

正难则反，可以用总方案数减去不能行的方案数。

可以用插板法来解决。

第一维可以被压掉。

T4

赛时

看一眼题发现暴力很好打，打了个暴力花了二十分钟。

预估：

实际：

题意

给你一个数，令表示的因子中与另外一个因子互质的数的个数，求。

思路

题解做麻烦了。

题意可以简化为找整数对使得并且的数量。

令，因为平方根一定不满足条件，所以算出来直接将答案乘二就行了。

可以枚举，计算它的贡献，具体方法是进行质因数分解，特判掉，然后看看有多少个数和它互质，因为质因数个数很小只有所以可以直接容斥。

25.10.20做题记录

策略游戏

题意

两个数列，前者在一个序列的区间中选数，后者在另外一个序列的区间中选数，得分为乘积。前者希望得分尽可能大，后者希望得分尽可能小，求得分。

思路

很恶心的大分讨。

用分钟去想贪心发现有负数不可做，考虑了一下分类讨论的去贪心，一共有中情况，代码难度偏高，花了将近一个小时。

这里列一个表格来枚举两种人的情况。

	先手没有负数	先手没有正数	先手都有
后手没有负数	先手最大后手最小	先手最大后手最小	先手最大后手最小
后手没有正数	先手最小后手最大	先手最小后手最大	先手最小后手最大
后手都有	先手最小后手最小	先手最大后手最大	如果先手有一定取，否则就是对同号的情况取最大值

可以用 ST 表或者线段树维护这些内容。

动物园

题意

有一些动物，其中二进制编号决定的需要的饲料，问你最多增加多少动物使得饲料数量是不变的。

思路

看完题马上会了，但是因为细节问题硬控半个多小时。

因为决定的饲料一定不相同，所以说可以直接把可以要的位数计算下来，最后减去已经有的方案数，也就是种方案。

需要 __int128。

星战

题意

一个 DAG，进行几种操作：

删除一条原来有的边
删除一个点（删除所有连向这个点的边）
恢复原来的一条边
恢复原来的一个点（恢复所有连向这个点的边）

问每次操作后，能否满足所有点的出度为，并且从任意一个点出发可以走到一个环中。

思路

看完题解和 aa 的代码会的，感觉代码不是非常难，写了写会了，三十分钟左右。

不可以，总司令。——沃·兹基

其实根本不用判断环，只需要判断度数。因为有 Wiki 上的结论：

如果一个有向图每个点的出度都为，称它是一个 基环内向森林。

顾名思义，从每个点出发都可以走到一个环上。

问题就变成的维护点的度数。

可以对于每个点随机一个权值，令表示当前所有连向的点的权值和，这个东西是可以来维护的。因为每次只会修改一个值，所以，也是可以维护的。

因为是随机权值，所以我们的目标状态可以看作是：

做完了。

消消乐

题意

一个字符串，如果相邻的字符相同可以删除，问你有多少子段满足能够全部删完。

思路

想到了括号匹配，后面不大会了。看的题解，代码很短。一个小时左右。

这个题完全可以看作括号匹配。

设表示以为结尾的合法串的方案数，我们找到上一个使它成为合法子串的下标（字符一定相同），这样就在原来的基础上多了一种方案数。

去维护下标减一，这样就会形成链，所以每次查询是的。

最后答案是。

染色

题意

一个数列染成蓝色和红色，每个点有权值。

如果说一个颜色前面第一个同颜色的值和它的相同，就将答案加上这个值。

求最后的答案最大值。

思路

看了题解，听了同学讲，再去理解一下，耗时一个小时多。

贪心显然不行，考虑 DP。

令为考虑到第位的答案最大。

显然可以转化为。

要想答案最大，一定要进行匹配。那就是上一个出现的下标往前加上中间匹配的成果再加上这两个的值。

要是中间匹配可以前缀和维护。

做完了。

25.10.21比赛总结

T1

赛时

想了个思路，写出来之后发现假完了。然后发现正确的思路和原来差不多，然后改了改就对了，用时一个小时。

估分：

实际：

~~话说多测不清空不应该只挂这么点的。~~

题意

一棵树，一个图。图中的连边在树上必须没有，权值为两点在树上的距离。

求这个图的最小生成树。

思路

由 Kruskal 可知，我们可以先连权值为的边，然后再连。

可以将深度相同的连，然后再将深度差的点连起来。

最后将两个连通块连一条长度为的边。

注意到菊花图是无解的。

所以答案就是。

需要特判。

T2

赛时

读错题了，本来想着可以二分，但是写着发现不对，正解不好想，想到了 DP 转移，又考虑了如何优化，代码细节很多，耗时两个半小时。

估分：

实际：

题意

一个序列分成几个子序列，求所有子序列的的的最大值。

思路

考虑答案的最大值，计算得出只有，考虑状压 DP。

令表示前个数，子序列的状态为的方案能否到达。

对于每一个状态，可以往后找个区间，然后暴力更新。

这样的做法时间复杂度是不可以接受的。

我们发现，当一些左端点相同的区间的相同的时候，只需要取右端点最靠左的区间就行了，因为去前面的不会让更劣。

因为很小可以去求，维护一下上面这个东西就做完了。

25.10.21做题记录

格雷码

题意

顾名思义，输出一个数的格雷码。

思路

去百度上研究了定义，然后找了找规律，然后做完了，十分钟。

通过打表可知，答案是的二进制反过来做完了。

廊桥分配

题意

一个机场，分给国内和国际廊桥，一个飞机在廊桥的停靠有时间段，问你在廊桥停靠的飞机的数量最大值。

思路

思考未果，看了眼题解，没想到是 T1 ，代码也不好写，一个小时。

分配廊桥的过程可以用优先队列来模拟，可以维护出哪些廊桥可用。枚举分给某个区的廊桥数，在预处理的时候做前缀和优化就做完了。

25.10.22做题记录

假期计划

题意

一个无向图，确定一条路线，要求每两点之间最短路的点数不超过，问你这四个点的权值和的最大值。

思路

听了 Gyf 讲，马上就会了，写代码用了不到一个小时。

给 Gyf 大神磕头了 /bx

边权都是，可以 BFS 预处理最短路，然后暴力枚举。显然会 TLE。

我们发现，当确定，是可以近似算出的。在 BFS 中预处理出这个点可以到达的点，并且这个点能到达，显然点权取最大最好。但考虑到会有重复，所以维护前大。这就是的做法。

将路径反过来，会发现原来的变成了。也就是说，的维护可以和相同，所以说可以做到。

括号树

题意

一棵树，树上有左右括号，求出从到某个点的合法括号子串的数量。

思路

搬了一道相似题的代码的思路，但是被细节问题卡了半个多小时。

我的精神状态：)( 是合法括号串。

一眼看和那道消消乐很类似，所以可以照搬消消乐的 DP 思路。

但是有两个细节：

每次搜完要进行回溯
只有 ) 可以进行 DP 转移

可以统计每次的答案，但是因为我太唐写了个树状数组。

~~我偷偷加一个应该没人看见吧。~~

括号序列

题意

一个字符串，有些地方可以选填左/右括号或者空，对空的数量有限制，问你整个字符串合法的方案数。

思路

听了 Gyf 讲，一个小时左右。

因为括号序列一定是一些括号和空拼起来的，所以可以根据左右两边的字符去设置状态，因为左右两边的字符影响到了它的拼接。

然后确定了 () 之后可以直接进行 DP。

回文

题意

一个序列，每次移除开头或者末尾放入另一个，问你最后能否达成回文，如果可以，输出字典序最小的方案（优先移除开头的方案）。

思路

和 aa，Gyf 共享了思路和代码，但是出了点细节小问题，而且后面去听唐彬峪的课了，用时一个半小时。

考虑到字典序最小直接贪心去解决，开两个双端队列来存储下来当前的状态，如果能够到达的状态就直接弹出，然后开两个 vector 来存储答案，注意到最后要按照题目顺序输出。

25.10.23比赛总结

T1

赛时

想了个思路，写了写过了样例，因为没有大样例直接交了。然后被同学的 Hack 给干掉了，又整理了思路重新写了写，码量不是很大，耗时一个小时左右。

估分：

实际：

题意

一个数初始为，每次可以加中的整数（），问你是否能经过次操作后恰好到达。

思路

T1 放大分讨出题人我爱你。

是的一个倍数，因为这样操作数最小，所以说判断是否合法就行了。
不是的倍数且，这样最小操作数是次操作，直接判断。
否则全放一定不满足条件，所以说只能选和，就变成了经典的鸡兔同笼问题，判断是否合法即可。

T2

赛时

思考将近一个小时无果，果断去打暴力，总耗时一个半小时。

估分：

实际：

题意

有一些机器人，若脚下的点不被染色，给脚下的点染色，控制这些机器人同时向左或向右，求最后每个机器人染色的点数。

思路

手玩几组样例，会发现两个机器人之间的段只能是左边和右边的机器人染色，其实这个通过相对静止也能看出来。

可以维护前几次操作，想左偏移的最大值和向右偏移的最大值。对于每个间隔，可以二分出最后一个互不侵犯的位置，最后根据下一次操作的正负性来判断空着的一段给谁。

时间复杂度，能过。

T3

赛时

没打。

估分：

实际：

赛后去补，因为写法问题常数慢了好几倍，所以直接交的 std。

题意

有一个图，左上全黑，剩下三块按这种方法涂。特别地，只有一个就是白色。

问你两个这样的图平移重叠之后，问你最后都是白色的数量。

思路

发现当最高位分别为时，它才会被涂为黑色。然后对于 DP 的每一位，枚举当前的位数和它的进位，平凡转移。

25.10.24做题记录

「DTOI-5」进行一个排的重 (Minimum Version)

题意

和是排列，让你重排。求这个东西的最小值：

思路

式子一眼不会看，反复思考无果，看的题解，发现很简单，半个小时左右。

首先是，可以将两个放在前面，答案是，剩下的随便放，方案是。

否则必须将一个放在前面因为后面的会对它产生贡献，答案是，方案是。

Color Rows and Columns

题意

有一些矩阵，涂完一行或一列获得分，问你获得至少一定分数的最小的代价。

思路

和 Gyf 共享了思路，在 Gyf 的指导下完成了代码，二十分钟。

stO Gyf117 Orz

考虑 DP。设表示考虑到第个，当前分数为的最小代价。对于每个矩阵，预处理用一定代价获得的最大收益，可以平凡的转移，时间复杂度可行。

League of Leesins

题意

有一个排列，以为滑动窗口大小，形成个窗口。将每个窗口打乱，给你打乱的这几个三元组，让你还原其中一个排列。

思路

很简单，口胡了一个思路和别人对了一下发现是对的。发现是很对的，代码不好写，半个小时左右。

首先一个边界元素的出现次数显然是。

然后确定一个，找到和它在一个三元组里，出现次数为的数就是第二个数。

然后根据两个可以在三元组中推断出下一个。

Word Cut

题意

一个字符串，进行次操作：

将字符串分成两半，交换两个部分。

问你次操作后从到的方案数。

思路

和 Gyf 共享了思路和代码，耗时一个小时左右。

原来的操作可以看成左移位。（）

设表示进行前次操作，当前串是否等于目标串的方案数。

首先次操作就是判断是否是目标串。

~~转移是平凡的。~~

对于一个状态，会从上一个状态的两种情况考虑。

可以预处理出原串经过一次操作到目标串的方案数为。

如果当前状态和以前的状态不相同，那么答案要加上上一个状态乘上方案数。

否则乘上的数就减，因为不进行操作是不合法的。

25.10.26比赛总结

T1

赛时

看了眼题，发现很好做，打了个代码，发现被 Hack 掉了，重新写了一下，耗时一个小时左右。

估分：

实际：

没有滚动数组加捆绑测试挂掉一百分（流泪

题意

一堆东西有重量和价值，可以选一些将重量乘，从中选出一些，要求重量相同，最大化价值和。

思路

因为一个东西只能选一次，考虑背包。

设表示选了前个数，用了次魔法，两边差值为的最大价值。

我们考虑选一个数价值为，转移过去可能是四种情况，直接暴力转移。

注意到空间限制很小，所以用滚动数组压一下。

T2

赛时

听到旁边同学的结论了，然后想了想就写过了，耗时半个小时。

估分：

实际：

题意

给出加密一个字符串的方法（省流：RSA 加密）：

给定不相等的质数，令。
令，找出一对整数使得且。
字符加密为。

给你和加密的字符串，求出原来的字符串。

思路

根据欧拉定理，当时，有。

但是时这个东西不一定成立。

由于，可以设，所以：

所以说。

所以说。

因为都是质数所以，用 exgcd 求逆元得到就做完了。

25.10.27做题记录

Balanced Playlist

题意

让你求出以为开头的最长区间，满足。

思路

发现是数据结构裸题，花二十分钟写了写，又用二十分钟去处理细节。

考虑双指针，每次左端点向右，右端点不会向左，用 set 去维护即可。

25.10.30比赛总结

T1

赛时

看到题之后一点头猪都没有，去开 T2 无果，果断打暴力，特殊性质骗满。

估分：

实际：

题意

每个物品有两个权值和，一个人会取当前最大的，问另一个人怎么取能使取到的最大，求这个最大值。

思路

第一题放蓝色的反悔贪心，畏惧了。

取前个元素，最多能拿到个物品，考虑贪心，每次把加进去，如果说元素太多了就弹出最小的那个。

可以用优先队列维护，时间复杂度，对于这种数据是能过的。

T2

赛时

想了很长时间，有了一点思路，马上去打，写到了最后发现不太对，最后去打了暴力。

估分：

实际：

题意

给你问你是否满足：

思路

观察数据范围，会发现，可以考虑从质因数的角度去考虑。

用线性筛去预处理质数，对于每一个质因数，如果在中的出现次数大于在中的出现次数，那就说明不会被整除。

考虑一下区间质因数出现次数如何去计算。

一段区间里的倍数是很好做的。

对于它的第一个倍数和最后一个倍数，继续递归这个区间进行递归，就可以算出所有的出现次数。