银当taki

分类

题解(31)

/ 注册

全部文章（共29篇）

25暑期第八场

B 逆序对循环移位给一个排列，问每次循环移位一个区间后，序列逆序对奇偶性交经典结论，换两个相邻元素，保证元素不同，逆序对奇偶反转。循环移位这个区间，相当于把移动到左边，其他不变，也就是交换次。根据的奇偶，即可知道操作完，整个序列逆序对的奇偶。 F 状压枚举二分不大，保留灯管的所有情况最...

2025-08-30

0 13

25暑期第七场

C 贪心每次可以选一个子序列，全部减一。问最少多少次操作可以变成不减。只能减不能加，那么贪心的想，最后一个元素一定不能减，否则它变小了，可能需要前面的元素减更多次才能保证序列不减。所以处理完一个后缀之后,一定比后缀里的所有都要小，也就是比小。如果初始，需要减小到，如果本来就比小则不用操作。最...

2025-08-30

0 13

25暑期第十场

F 双指针扫描线线段树确定两个指针把数组分成三段，求一个方案使得三个集合的交集最大有两个指针的位置需要确定，显然考虑枚举，然后对每个确定三个集合交集最大的的位置对于每种元素，想要这个元素出现在交集里，也就是三个集合都有这个元素，如果确定，设这个元素在里最左出现位置是，最右出现是，那么想让三...

2025-08-14

3 45

25暑期第九场

A 树形dp 观察可以删点，加点，问把一个二叉树变成avl的最少操作次数？ avl的要求就是左右子树都是avl树，且左右子树高度差不超过1. 注意到这是个递归定义，可以考虑树形dp，计算出一个点的两个子树变成avl树的最小代价，然后再用这两个一个变成avl的子树，和当前点拼起来，就能计算当前点为根...

2025-08-13

3 40

25暑期第六场

C 计数 dp优化对一个长度为n的排列跑单调栈，最后栈中剩下的元素个数为，注意到一个排列增加一个元素，对剩余元素个数的影响时很好分析的，如果给一个长度n的排列增加一个元素n+1，只有在n+1插入到排列的结尾时，单调栈中剩余元素个数才会增加，其余位置元素个数都不变。增加一个元素，变化可以求，很适...

2025-08-13

0 26

2025暑期第四场

B BFS 思维网格图上从起点到终点，只能往上下右走，人有一个视野，超出范围的看不到。问是否存在一个死胡同，会误导人走进来等价于是否存在一个路径，人没走进来时无法确定是不是死路，只有等走进来了才能发现是死路（由于不能往左走，此时已经晚了，游戏失败）首先需要找到所有死路的点，这可以通过找到所有能...

2025-07-31

1 32

2025暑期第五场

J 二分多源BFS 切比雪夫距离 01矩阵，最多把一个0变成1，然后每个1每一秒会把曼哈顿距离为1的相邻0变成1，问变成全1的最小时间？注意到肯定是越早越困难，越晚越容易，答案具有单调性，可以二分变成全1的时间。从多个源点出发的染色，故check里考虑多源bfs，发现我们从所有1出发bfs，只...

2025-07-30

3 34

2025暑期第三场

D 思维可以把长度a的连续1变成0，可以把长度a+1的连续0变成1，问最多能得到多少1？只要有一段长度a的1，我们把他们变成0，然后和两侧的0，肯定可以构成一个长度至少a+1的连续0，然后我们可以把他们再变成1，重复这个操作可以把所有0都变成1 如果开始没有长度a的1，但是有长度a+1的0，可以...

2025-07-23

5 33

2025暑期第二场

A 计数DP 1表示看到白天，0表示看到晚上，-1表示看到不确定。给个序列，问所有把-1变成0或1的方案中，白天天数的和？首先如果只是求方案数是好求的，但是这里每个方案都有贡献，要求的是所有方案的贡献和。这种一般就维护两个dp数组，一个是贡献和，一个是方案数，方案数正常转移，什么时候能产生贡献了，...

2025-07-23

2 44

2025暑期第一场

2025暑期第一场 G 模拟数学给两个01串，问分别从两个位置开始的子串，有多少个子区间完全相同？注意到这是01串/手玩，可以推出，对于每段相等的最长子区间，长度的话，对答案贡献是 #include <bits/stdc++.h> #define rep(i, a, b) for(...

2025-07-16

4 48